Answer to Question #309512 in Discrete Mathematics for Shoaib

Question

1.1 Determine whether ( 𝑝∨𝑞)∧(𝑝→𝑟)∧( 𝑞→𝑠)→𝑟∨𝑠 is a Tautology or a contradiction

And give steps please

Answer 1

Proof by contradiction

Suppose the formula is not a tautology.

Then there exist $(p_0,q_0,r_0,s_0 )∈(T,F)^4$ such that

$|(p_0⋁q_o)⋀(p_0→r_0)∧(q_0→s_0)→r_0∨s_0 |=F$ .

The definition of implication implies that

$|(p_0⋁q_o)⋀(p_0→r_0)∧(q_0→s_0)|=T$ and $|r_0∨s_0 |=F$

The definition of conjunction and disjunction imply that

$|p_0⋁q_o|=|p_0→r_0|=|(q_0→s_0)|=T$ and $|r_0|=|s_0 |=F$

It follows from $|p_0 |→F=|q_0 |→F=T$ that $|p_0 |=|q_0 |=F$

Consequently $|p_0∨q_0 |=F∨F=F$ and we have a contradiction with $|p_0∨q_0 |=T$

Therefore, our assumption is not true, and we conclude that the statement is a TAUTOLOGY