Answer to Question #198636 in Discrete Mathematics for Shadleigh

Question

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

Answer 1

Let us prove that $( 𝑝∨𝑞)∧(𝑝→𝑟)∧( 𝑞→𝑠)→𝑟∨𝑠$ is a tautology using proof by contraposition. Suppose that the formula is not a tautology. Then there exists $(p_0,q_0,r_0,s_0)\in\{T,F\}^4$ such that $|( 𝑝_0∨𝑞_0)∧(𝑝_0→𝑟_0)∧( 𝑞_0→𝑠_0)→𝑟_0∨𝑠_0|=F.$ The definition of implication implies that $|( 𝑝_0∨𝑞_0)∧(𝑝_0→𝑟_0)∧( 𝑞_0→𝑠_0)|=T$ and $|𝑟_0∨𝑠_0|=F$.

The definitions of conjunction and disjunction imply that $| 𝑝_0∨𝑞_0|=|𝑝_0→𝑟_0|=|𝑞_0→𝑠_0|=T$ and $|𝑟_0|=|𝑠_0|=F.$ It follows from $|𝑝_0|→F=|𝑞_0|→F=T$ that $|p_0|=|q_0|=F.$ Consequently, $|p_0\lor q_0|=F\lor F=F$ and we have a contradiction with $|p_0\lor q_0|=T.$ Therefore, our assumption is not true, and we conclude that the formula $( 𝑝∨𝑞)∧(𝑝→𝑟)∧( 𝑞→𝑠)→𝑟∨𝑠$ is a tautology.