# Prove “$(p \lor q) \land (\neg p \lor r)) \rightarrow (q \lor r)$” is a tautology

I've been studying Discrete Mathematics from Kenneth Rosen's book. In that book, there is this "$(p \vee q) \land (\neg p \vee r)) \rightarrow (q \vee r)$" proposition if we can say so.

The book wants me to prove that this proposition is a tautology. I've searched on the Internet and also on here but couldn't figure out how to prove this without a truth table. There is another asked question but that is so confusing and is not really illustrative.

Would you help me to prove this, please? Thank you in advance. :)

• The \vee ($\vee$) \neg ($\neg$) \wedge ($\wedge$) and \rightarrow ($\rightarrow$) commands might be good to learn :) – Zubzub Nov 14 '17 at 14:10
• @Zubzub Didn't know that, thanks! :) – André Yuhai Nov 14 '17 at 14:30
• Also note that it's preferred to put the entire expression/formula in a MathJAX environment. Instead of "vee" and "wedge" you can also use "lor" and "land" (which may be easier to remember). – skyking Nov 14 '17 at 14:46

By using the fact that $\phi \rightarrow \psi$ is equivalent to $\neg\phi\lor\psi$ you get the expression to be equivalent to.

$$((\neg q\rightarrow p)\land (p\rightarrow r))\rightarrow (\neg q\rightarrow r)$$

Then it's obvious...

Another way is to use distributive laws:

\begin{align}(p\lor q)\land(\neg p \lor r) & \leftrightarrow (p\land\neg p) \lor (p\land r) \lor (q\land \neg p)\lor (q\land p) \\ &\leftrightarrow (p\land r) \lor (q\land \neg p)\lor (q\land p) \\ &\rightarrow (p\land q) \lor (p\land r) \lor (q\land \neg p)\lor (q\land p) \\ &\leftrightarrow (p\lor \neg p)\land (q\lor r) \\ &\leftrightarrow (q\lor r) \end{align}

Or if you know the consensus theorem:

\begin{align} (p\lor q)\land(\neg p\lor r) & \leftrightarrow (p\lor q)\land(\neg p\lor r) \land(q\lor r) \\ & \rightarrow (q\lor r) \end{align}

• Thank you so much! This is what I was looking for. But I've another question if you excuse my ignorance. I am totally lost on the distributive way at the third line. Can you please explain where did $p \land q$ come from on the third line? Since the others are just from the previous line. – André Yuhai Nov 14 '17 at 15:20
• @PorFavorDama Note that this step is just an implication, it's because $\phi\rightarrow \psi\lor\phi$ so we can add any term we want after the implication arrow - here $p\land q$ is chosen in order to allow the reverse distirbutive law. In reality I used distributive law to go from the first row down to the second and from the last row up to the third and saw that $p\land q$ was the term that was differing and then joined these part with the implication. – skyking Nov 14 '17 at 15:30
• Now, everything is clear. I appreciate your help, thank you! :) – André Yuhai Nov 14 '17 at 15:38

Another proof, mimicking Rosen's EXERCISE 8, page 30.

1) Remove $\to$ with the equivalence: $A \to B$ and $\lnot A \lor B$ to get:

$¬[(p∨q)∧(¬p∨r)] ∨ (q∨r)$.

2) Apply De Morgan to get:

$[¬(p∨q)∨¬(¬p∨r)] ∨ (q∨r)$.

3) Apply De Morgan again:

$[(¬p∧¬q)∨(p∧¬r)] ∨ (q∨r)$.

4) Apply Associativity and Commutativity to get:

$[(¬p∧¬q)∨(q∨r)] ∨ (p∧¬r)$.

5) Now apply Distributivity to the left part:

$[(¬p∨(q∨r))∧(¬q∨(q∨r))] ∨ (p∧¬r)$.

But $(¬q∨(q∨r)) \equiv ((¬q∨q)∨r) \equiv (T \lor r) \equiv T$ and thus $[(¬p∨(q∨r))∧(¬q∨(q∨r))] \equiv (¬p∨(q∨r)) ∧ T \equiv (¬p∨(q∨r))$.

In conclusion, we have:

6) $(¬p∨(q∨r)) ∨ (p∧¬r)$.

Now we use Distributivity again to get:

7) $(p∨¬p∨q∨r) ∧ (¬p∨q∨r∨¬r)$.

But $(p∨¬p∨q∨r) \equiv (¬p∨p)∨(q∨r) \equiv T ∨ (q∨r) \equiv T$.

And the same for $(¬p∨q)∨(r∨¬r) \equiv T$.

In conclusion:

$T ∧ T \equiv T$.

• I had tried this but I was always stuck in some step. I couldn't rewrite it to apply reverse distributive law. Thank you so much for showing me the way. :) – André Yuhai Nov 14 '17 at 16:50
• @PorFavorDama - you are welcome :-) – Mauro ALLEGRANZA Nov 14 '17 at 16:52

Note that the proposition is false only when $q$ and $r$ are both false. (Why?)

When this takes place, can you show that the LHS is also false?

• Because ORing two false propositions gives us a false. On the LHS it would also be false because we have p and its compliment and that makes our proposition false $\rightarrow$ false , which is true. – André Yuhai Nov 14 '17 at 14:34

I would start by supposing that the statement is false.

What does this mean? Well we have an implication, and the implication $A\implies B$ is false if and only if $v(A)=T$ and $v(B)=F$.

So your statement is false if and only if the left side of the implication is true, and the right side $q \vee r$ is false.

Now if $q \vee r$ is false, then both $q$ and $r$ are themselves false.

From here, see what $q$ and $r$ being false means for the left hand side.

I hope this helps.

• Yes, that is also what Rohan meant, I guess. But I was looking for a way to prove this using distributive laws and stuff. Thanks anyway :) – André Yuhai Nov 14 '17 at 15:16