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.

start of proof

That's what I have so far... It seems like a bad approach. I've tried others and end up in the same spot.

share|improve this question
1  
@Danikar: using a truth-table is not the method that the OP needs to use to prove the equivalence. –  amWhy Jan 16 '13 at 23:02
    
I don't mean to be a bother, but what textbook is this particular problem from? –  Mack Feb 13 '13 at 22:16
1  
@Eli it's this one amazon.com/gp/aw/d/0073383090 –  papercuts Feb 14 '13 at 1:46

3 Answers 3

up vote 8 down vote accepted

What you've done in the first few steps is all correct. I'll start where you left off. We need to use a lot of distribution. And it gets messier before it gets clearer!

To prove $$[(p \rightarrow q) \land (q\rightarrow r)] \rightarrow (p\rightarrow r) \equiv T$$ $$\vdots$$ $$\vdots$$

$$\equiv (p\land \lnot q) \lor (q \land \lnot r) \lor (\lnot p \lor r)\tag{picking up...}$$ $$\equiv [[(p\land \lnot q) \lor q] \land [(p \land \lnot q) \lor \lnot r]] \lor (\lnot p \lor r)\quad \tag{distributivity x 2}$$

$$\equiv [[(p\lor q) \land (\lnot q \lor q)] \land [(p\lor \lnot r)\land (\lnot q \lor \lnot r)]] \lor(\lnot p \lor r)\quad \quad\quad \quad\tag{distributivity x 2}$$

$$\equiv [(p \lor q) \land T \land (p \lor \lnot r) \land (\lnot q \lor \lnot r)] \lor (\lnot p \lor r)\quad \tag{$\lnot q \lor q \equiv T$}$$

$$\equiv [(p \lor q) \land (p \lor \lnot r) \land (\lnot q \lor \lnot r)] \lor (\lnot p \lor r)\quad \quad \quad \quad \tag{$(p \lor q) \land T \equiv (p \lor q)$} $$


Can you see how distribution (as discussed in an answer to your earlier question) helps here? We've eliminated one expression ($\lnot q \lor q \equiv T$), and if you proceed with expanding out, using distribution, on the expression to the left (in brackets), you will be able to eliminate other terms...ending with a final evaluation of $T$.

Why don't you work on it a bit to see what you arrive at, and post a follow up question in a comment below, or as an edit to this question if you run into problems.


Edit: continued from where we left off...

To prove:

$$[(p \rightarrow q) \land (q\rightarrow r)] \rightarrow (p\rightarrow r) \equiv T$$ $$\vdots$$ $$\vdots$$

$$\equiv [(p \lor q) \land (p \lor \lnot r) \land (\lnot q \lor \lnot r)] \lor (\lnot p \lor r)\quad \quad \quad \quad \tag{$(p \lor q) \land T \equiv (p \lor q)$} $$ $$\equiv [(p \lor q) \land (\lnot q \lor \lnot r) \land (p\lor \lnot r)] \lor (\lnot p \lor r)\quad\quad\quad\quad \tag{Commutative property}$$

$$\equiv[[(p \lor q) \land \lnot q] \lor [(p \lor q) \land \lnot r] \land (p \lor \lnot r)] \lor (\lnot p \lor r)\quad\quad\quad\quad \tag{distributivity x 2}$$

$$\equiv[[(p\land \lnot q) \lor (q \land \lnot q) \lor (p \land \lnot r) \lor (q \land \lnot r)] \land (p \land \lnot r)] \lor (\lnot p \lor r) \quad\quad\quad\quad\quad \tag{distributivity}$$

$$\equiv [[(p \land \lnot q) \lor F \lor (p\land \lnot r) \lor (q \land \lnot r)] \land (p \land \lnot r)] \lor (\lnot p \lor r)\quad\quad\quad\quad\quad\quad\tag{$q \land \lnot q \equiv F$}$$

$$\equiv [[(p \land \lnot q) \lor \color{red}{\bf{(p\land \lnot r)}}\lor (q \land \lnot r)] \land \color{red}{\bf{(p \land \lnot r)}}] \lor (\lnot p \lor r) \quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad \tag{$(p \land \lnot r) \lor F \equiv p \land \lnot r)$}$$

$$\equiv \color{red}{\bf{(p \land \lnot r)}} \lor (\lnot p \lor r)\quad\quad\quad\quad \tag{?}$$

$$\equiv (\lnot \lnot p \land \lnot r) \lor (\lnot p \lor r)\quad\quad\quad\quad\tag{Double negation}$$

$$\equiv \lnot( \lnot p \lor r) \lor (\lnot p \lor r) \quad\quad\quad \tag{DeMorgan's Law}$$

$$\quad \equiv T \quad\quad\quad\quad \tag{$\lnot a \lor a \equiv T$}$$

Hence, $$[(p \rightarrow q) \land (q\rightarrow r)] \rightarrow (p\rightarrow r) \equiv T$$


Task: What remains is for you to justify/understand why the step followed by "$\,(?)\,$" holds.


share|improve this answer
    
i.imgur.com/8exCR.png It's just getting worse... –  papercuts Jan 16 '13 at 4:08
1  
I'll take a look at it...I got to a F (false) "or" term, and dropped it as well...but I'm going to need to get a little sleep. I'll look at it more carefully when I wake up. I think we can trim back a little on the work...but I'm proud of your effort! I'll get back to you! –  amWhy Jan 16 '13 at 4:23
    
Thanks, you're awesome. Applying the distributive across 4 terms helped me with a different problem as well so double thanks ! –  papercuts Jan 16 '13 at 4:38
    
This seems like a lot of work compared to a proof by contradiction. –  Code-Guru Jan 16 '13 at 23:10
    
papercuts - You're welcome! Let me know if you have any questions. –  amWhy Jan 17 '13 at 0:42

Let's assume that (1)$[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r)$ is false for some assignment of $p$, $q$, and $r$. From the truth table for implication, this means that (2)$(p \rightarrow q) \land (q \rightarrow r)$ must be true while (3)$p \rightarrow r$ is false. From (2) we see that (4)$p \rightarrow q$ and (5)$(q \rightarrow r)$ must be true and from (3) we have (6)$p$ must be true while (7)$r$ is false. So from (4) and (6), $q$ must be true. But now we have a contradiction with (5) and (7). Therefore no assigment of $p$, $q$, and $r$ which will make the original statement false.

share|improve this answer

Here is yet another proof: \begin{align} & ((p \rightarrow q) \land (q \rightarrow r)) \rightarrow (p \rightarrow r) \\ \equiv & \;\;\;\;\;\text{"expand all occurrences of $\;\rightarrow\;$"} \\ & \lnot((\lnot p \lor q) \land (\lnot q \lor r)) \lor \lnot p \lor r \\ \equiv & \;\;\;\;\;\text{"in the first disjunct we may assume the negation of the others ($\;\lnot p\;$ and $\;r\;$)"} \\ & \lnot((\text{false} \lor q) \land (\lnot q \lor \text{false})) \lor \lnot p \lor r \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & \lnot(q \land \lnot q) \lor \lnot p \lor r \\ \equiv & \;\;\;\;\;\text{"excluded middle"} \\ & \lnot \text{false} \lor \lnot p \lor r \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & \text{true} \\ \end{align}

share|improve this answer

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.