0
$\begingroup$

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

$\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.
    Commented Jan 7, 2020 at 15:37
  • 2
    $\begingroup$ Use Material Implication : $A \to B$ is equiv to $\lnot A \lor B$. $\endgroup$ Commented Jan 7, 2020 at 15:42

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

\begin{align} (p \lor q) \land (\neg p \lor r) \to (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 \end{align}

$\endgroup$
3
  • 1
    $\begingroup$ Thank you very much, all of the parentheses was getting me slightly confused but cleared it up. $\endgroup$ Commented 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$
    – PinkyWay
    Commented Jan 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$
    – PinkyWay
    Commented Jan 7, 2020 at 18:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .