# Prove this proposition is a tautology: [(p ∨ q) ∧ (p → r) ∧ (q → r)] → r Did I make an error?

Any help is greatly appreciated

[(p ∨ q) ∧ (p → r) ∧ (q → r)] → r ≡

¬[(p ∨ q) ∧ (¬p ∨ r) ∧ (¬q ∨ r)] ∨ r ≡

¬(p ∨ q) ∨ ¬(¬p ∨ r) ∨ ¬(¬q ∨ r) ∨ r ≡ //especially concerned about this step

¬(p ∨ q) ∨ (¬¬p ∧ ¬r) ∨ (¬¬q ∧ ¬r) ∨ r ≡

¬(p ∨ q) ∨ (p ∧ ¬r) ∨ (q ∧ ¬r) ∨ r ≡

¬(p ∨ q) ∨ {(¬r ∧ p) ∨ (¬r ∧ q)} ∨ r ≡

¬(p ∨ q) ∨ {¬r ∧ (p ∨ q)} ∨ r ≡

¬(p ∨ q) ∨ r ∨ {¬r ∧ (p ∨ q)} ≡

¬(p ∨ q) ∨ {(r ∨¬r) ∧ (r ∨(p ∨ q))} ≡

¬(p ∨ q) ∨ {T ∧ (r ∨(p ∨ q))} ≡

¬(p ∨ q) ∨ (r ∨(p ∨ q)) ≡ //also very concerned about last couple steps

¬(p ∨ q) ∨ r ∨ (p ∨ q) ≡

¬(p ∨ q) ∨ (p ∨ q) ∨ r ≡

T ∨ r ≡

T

• – Shaun Jan 25 at 19:03
• Why don't you look the MathJax tutorial? Are you going to copy the symbols every single time in future? I edited your post and you said you would do what @Shaun suggested yesterday. Nobody will read your work untill you edit it because it literally hurts. Just listen what people advise you to do. – ms._VerkhovtsevaKatya Jan 25 at 22:39
• @VerkhovtsevaKatya how would this be any more readable with the MathJax? I am looking into the Math Jax tutorial, but its a lot to take in, and for the time being it is faster to do it this way. – brettF Jan 25 at 23:01
• What you just changed it to is not very helpful to be honest. It looks exactly the same but no spaces. Instead of taking the time to edit my proof into this new format/font, it would be much more helpful if you just looked at my proof and told me if you see any errors. I am trying to learn how to write a proof-not some mathjax thing – brettF Jan 25 at 23:04
• You have to use MathJax because it is the only way you can search for possibly already answered questions, i.e. avoiding duplicates. Your proof is, all in all, correct, but a complete cliche. You cannot learn how to prove sth, but how to think. Learning MathJax is a matter of literacy in this community. – ms._VerkhovtsevaKatya Jan 25 at 23:18

To address your actual question, the proof you have given is correct. Good job! Could it be better? Sure. The fact that you are "very concerned" about two of the steps indicates to me that you really need to understand why those steps are valid. Is it something about distributivity or associativity combined with DeMorgan? Regardless, do your best to bridge those gaps because your proof is correct--but make sure you understand why. That said, I will present another way of trying to go about it.

Start by letting (the reason why will become clear in a second) $$\Phi\equiv(\neg p\lor r)\land(\neg q\lor r)\tag{1}.$$ And note that $$\neg(p\lor q)\lor r\equiv(\neg p\land\neg q)\lor r\equiv (\neg p\lor r)\land(\neg q\lor r)\equiv\Phi.\tag{2}$$ Now see if you can follow this reasoning: \begin{align} [(p\lor q)\land(p\to r)\land(q\to r)]\to r &\equiv \neg[(p\lor q)\land(\neg p\lor r)\land(\neg q\lor r)]\lor r\\[0.5em] &\equiv \neg(p\lor q)\lor\neg[(\neg p\lor r)\land(\neg q\lor r)]\lor r\\[0.5em] &\equiv \Phi\lor\neg\Phi\\[0.5em] &\equiv \mathbf{T}. \end{align}

We have $$p\lor q$$, $$p\to r$$, and $$q\to r$$. Now assume $$\lnot r$$. It follows that $$\lnot q \land\lnot p$$, that is $$\lnot(p\lor q)$$, contradicting $$p\lor q$$.

From your $$2^{\text{nd}}$$ line: $$(p\lor q)\land(\neg p\lor r)\land(\neg q\lor r)$$ Distribution:

$$(\neg p\lor r)\land(\neg q\lor r)\equiv(\neg p\land\neg q)\lor r\equiv\neg (p\lor q)\lor r$$

We obtain: $$\neg[(p\lor q)\land r]\lor r\equiv\neg(p\lor q)\lor\neg r\lor r\equiv\neg(p\lor q)\lor 1\equiv 1$$ The edited more detailed version with explanation: $$[(p\lor q)\land (p\implies r)\land(q\implies r)]\implies r$$ You've done the following part correctly: $$\equiv\neg[(p\lor q)\land(\neg p\lor r)\land(\neg q\lor r)]\lor r$$ We agree on that. I'll repeat the above: $$(\neg p\lor r)\land(\neg q\lor r)\equiv(\neg p\land\neg q)\lor r\equiv\neg(p\lor q)\lor r$$ Let's return: $$\neg[(p\lor q)\land(\neg(p\lor q)\lor r)]\lor r\equiv$$

$$\neg[((p\lor q)\land\neg(p\lor q))\lor((p\lor q)\land r)]\lor r\equiv$$ $$\neg[0\lor(p\lor q)\land r]\lor r\equiv\neg[(p\lor q)\land r]\lor r$$

Finally: $$\neg(p\lor q)\lor\neg r\lor r\equiv\neg(p\lor q)\lor 1\equiv 1$$

• I am having trouble understanding. Is there and error in my proof? how is this related? – brettF Jan 25 at 23:14
• Use the distribution law in the very beginning. – ms._VerkhovtsevaKatya Jan 25 at 23:25
• this still isn't applicable. you've edited it several times, but your approach still seems invalid – brettF Jan 25 at 23:29
• @brettF, is it clear now? – ms._VerkhovtsevaKatya Jan 26 at 0:08
• I added the colour – ms._VerkhovtsevaKatya Jan 26 at 0:13