# How do i prove that $(p \vee q) \wedge (\neg p \vee r) \rightarrow (q \vee r)$ is a tautology without using the truth table?

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

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

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.
\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}
• 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! (: Commented Jan 7, 2020 at 18:05