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. :)

  • $\begingroup$ The \vee ($\vee$) \neg ($\neg$) \wedge ($\wedge$) and \rightarrow ($\rightarrow$) commands might be good to learn :) $\endgroup$ – Zubzub Nov 14 '17 at 14:10
  • $\begingroup$ @Zubzub Didn't know that, thanks! :) $\endgroup$ – André Yuhai Nov 14 '17 at 14:30
  • $\begingroup$ 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). $\endgroup$ – 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} $$

  • $\begingroup$ 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. $\endgroup$ – André Yuhai Nov 14 '17 at 15:20
  • $\begingroup$ @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. $\endgroup$ – skyking Nov 14 '17 at 15:30
  • $\begingroup$ Now, everything is clear. I appreciate your help, thank you! :) $\endgroup$ – 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$.

  • $\begingroup$ 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. :) $\endgroup$ – André Yuhai Nov 14 '17 at 16:50
  • $\begingroup$ @PorFavorDama - you are welcome :-) $\endgroup$ – 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?

  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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 :) $\endgroup$ – André Yuhai Nov 14 '17 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.