I am looking to for a way to prove that the statement $(p \vee q) \wedge (\neg p \vee r) \rightarrow (q \vee r)$ is a tautology. I am unable to use the truth table or the rules of inference for this. I can only solve this by using Laws and Theorems such as De Morgans Law and Distributive Law. Any help would be greatly appreciated. Thank you
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Welcome to math.SE! You will probably get a better answer if you provide a more complete list of laws and theorems you are allowed to use, especially the ones relating to the connectives $\neg$ and $\rightarrow$. $\endgroup$– Z. A. K.Jan 7, 2020 at 15:37
-
2$\begingroup$ Use Material Implication : $A \to B$ is equiv to $\lnot A \lor B$. $\endgroup$– Mauro ALLEGRANZAJan 7, 2020 at 15:42
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Assume $\lnot(q \vee r)$ and reach a contradiction. You may have to make a second level assumption once of $p$ and once of $\lnot p$ and reach a contradiction from each one.
answered Jan 7, 2020 at 15:41
$\begingroup$
$\endgroup$
3
$\;\;\;\;\;\;(p \lor q) \land (\neg p \lor r) \implies (q \lor r)\equiv\neg\{[(p \lor q) \wedge (\neg p \lor r)] \land \neg(q \lor r)\}\\\equiv\neg[(p\lor q)\land(\neg p\lor r)\land(\neg q\land\neg r)]\equiv\neg[(p\lor q)\land\neg p\land\neg q\land\neg r]\equiv\neg[(p\lor q)\land\neg(p\lor q)\land \neg r)]\equiv\neg0\equiv1$
-
1$\begingroup$ Thank you very much, all of the parentheses was getting me slightly confused but cleared it up. $\endgroup$ Jan 7, 2020 at 16:50
-
$\begingroup$ @ConorWykes, I'll put brackets on some places. You're welcome, you can accept answers you find helpful. $\endgroup$– PinkyWayJan 7, 2020 at 17:51
-
$\begingroup$ Intersections with negated terms are always false. When you think of $\neg(P\implies Q)\equiv P\land\neg Q$ remember truth can never imply a lie. Therefore XOR is the negation of equivalence & negation of one implication is enough for equivalence to be false: $P\iff Q\equiv (P\implies Q)\land(Q\implies P)$ Therefore:$$\neg(P\iff Q)\equiv\neg[(P\implies Q)\land(Q\implies P)]$$ $$\equiv\neg(P\implies Q)\lor\neg(Q\implies P)$$ $$\equiv(P\land\neg Q)\lor (Q\land\neg P)$$ Keep that in mind & never learn by heart! (: $\endgroup$– PinkyWayJan 7, 2020 at 18:05