# Algebraic Solution to Prove Tautology

I need an algebraic solution to show this is a tautology:

$\displaystyle [(p\lor q) \land (p \rightarrow r) \land (q \rightarrow r)] \rightarrow r$.

Thanks

-
And what do you mean by "algebraic solution"? – Arturo Magidin Oct 8 '11 at 20:45
Have you tried completing the square? (I jest) – The Chaz 2.0 Oct 9 '11 at 2:08

## 2 Answers

$a\rightarrow b \equiv \neg(a)\lor b$, so what you have is equivalent to $$\neg\left[(p\lor q) \land [\neg p \lor r] \land [\neg q\lor r]\right] \lor r$$ By De Morgan's Law, this is equivalent to: $$\neg(p\lor q) \lor \neg(\neg p\lor r) \lor \neg(\neg q\lor r) \lor r$$ which in turn is equivalent to: $$(\neg p\land \neg q) \lor (p\land \neg r) \lor (q\land \neg r) \lor r$$ which is the same as $$(\neg p\land \neg q)\lor\Bigl( ( p\land \neg r)\lor (q\land \neg r)\Bigr) \lor r$$ which in turn is the same as $$(\neg p\land \neg q)\lor\Bigl( ( p \lor q)\land \neg r\Bigr)\lor r$$ which gives $$(\neg p\land \neg q)\lor\Biggl( \bigl(( p\lor q)\lor r\bigr)\land (\neg r\lor r)\Biggr)$$ which gives $$(\neg p\land \neg q) \lor \Biggl( \bigl( (p\lor q)\lor r\bigr) \land 1\Biggr)\equiv (\neg p\land \neg q) \lor \Bigl( (p\lor q)\lor r\Bigr)$$

Distributing, we get $$\Bigl( \neg p \lor p \lor q\lor r\Bigr) \land\Bigl( \neg q\lor p \lor q \lor r\Bigr)$$ Which is $$\Bigl( 1\lor q \lor r\Bigr) \land \Bigl( p\lor 1 \lor r\Bigr) \equiv 1\land 1 \equiv 1.$$

-
 This is one of the instances where a "formal proof" actually decreases the credibility of the statement. – Christian Blatter Oct 9 '11 at 20:03 @ChristianBlatter: I honestly don't understand that comment. While I agree that the manipulations above are not intuitive, and do not really tell one "why" one should expect the original formula to be tautology, I do not see how the proof can decrease the "credibility" of "the formula is a tautology". I can see that it doesn't really explain it, and it may not make it more "credible" to someone who is doubtful to begin with, but I simply cannot imagine how it can "decrease the credibility". We'll just have to agree to disagree on that. – Arturo Magidin Oct 9 '11 at 20:20

You said that you needed an "algebraic" solution to see that it is a tautology, but I would argue that one can simply see directly that it is a tautology. What your expression asserts is that if you know that $p$ or $q$ hold, and each of them implies $r$, then you know $r$. But this is clear. What good does any algebraic commputation add to the clarity of this?

-
 Well, simply because that's the question. – John Oct 9 '11 at 19:40 Well, let my criticism stand as a criticism of the question, then. – JDH Dec 18 '11 at 8:49