Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

2 Answers 2

$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.$$

share|improve this answer
    
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?

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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