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 am having trouble with a problem in the book I'm self-studying from. It says the following:

Show that $(P\to Q) \land (Q \to R) $ is equivalent to $(P \to R)$ $\land [(P \iff Q) \lor (R \iff Q)]$ by using logical connectives

I have dedicated so far a hefty amount of time on this problem, and now I'm asking you guys advice/hints or solution as to how to solve this problem. Here is one of the methods I used. Point any flaws that I made.

$(P\to Q) \land (Q \to R) $

(Conditional Law)

$(\neg P \lor Q) \land (\neg Q \lor R) \Rightarrow$

(Distributive Law)

$[(\neg P \land \neg Q)] \lor [Q \land (\neg Q \lor R)] \Rightarrow$

(Distributive Law)

$[(\neg P \land \neg Q) \lor (R \land \neg P)] \lor [(Q \land \neg Q) \lor (R \land Q)] \Rightarrow$

Contradiction

$[(\neg P \land \neg Q) \lor (R \land \neg P)] \lor [(Contradiction) \lor (R \land Q)] \Rightarrow$

(Contradiction Law)

$[(\neg P \land \neg Q) \lor (R \land \neg P)] \lor [ (R \land Q)] \Rightarrow$

Typically at around step five I get stuck or get confused because the problem gets messy. I know you could show it by using the truth-tables. However, the problem says use logical connectives. My questions are: Am I on the right track into solving this problem? Did I make any mistakes? What advice/hints would you give me in my path to solving this problem?

Edit Some of you guys want me to list the laws. Here they are:

DeMorgan's laws

$\neg(P \land Q) \equiv \neg P \lor \neg Q$

$\neg(P \lor Q) \equiv \neg P \land \neg Q$

Commutative laws

$P \lor Q \equiv Q \lor P$

$Q\lor P \equiv P \lor Q$

Associative Laws

$P \land (Q \land R) \equiv (P \land Q) \land R $

$(P \land Q) \land R \equiv P \land (Q \land R) $

Idempotent Laws

$P \land P \equiv P$

$P \lor P \equiv P$

Distributive Laws

$P \land (Q \lor R) \equiv (P \land Q ) \lor (P \land R)$

$P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$

Absorption Laws

$P \lor (P \land Q) \equiv P$

$P \land (P \lor Q) \equiv P$

Tautology Laws

$P \land (tautology) \equiv P$

$P \lor (tautology) \equiv (tautology)$

Contradiction Laws

$P \land (contradiction) \equiv (contradiction)$

$P \lor (contradiction) \equiv P$

Conditional laws

$P \to Q \equiv \neg P \lor Q$

$P \to Q \equiv \neg (P \land \neg Q)$

share|improve this question
1  
What does "by using logical connectives" mean? –  Peter Smith Sep 23 '13 at 20:07
    
@PeterSmith I guess the author means by using the laws that involves connectives like $\lor ,\land,\neg,\to$ . –  John Wilson Sep 23 '13 at 20:25
1  
(Out of interest, which book is this?) –  Peter Smith Sep 23 '13 at 20:26
    
@PeterSmith How to prove it by Velleman –  John Wilson Sep 23 '13 at 20:33
1  
@DougSpoonwood I think I understand your point. However, it's up to the reader to understand which conditional law is being used. The writer can only do so much in how he arrived from A to B. I do not want this be a very technical problem with a very technical solution. For instance , I don't want to be very technical that 1+1=2. I just want a solution from someone that is clear enough for me to understand. If it's not clear enough for me, I'll ask questions to gain a better picture. –  John Wilson Sep 25 '13 at 17:04

2 Answers 2

up vote 2 down vote accepted

What we would like to prove is a conjunction, so it suffices to prove each conjunct separately and then glue them together at the end. This problem would probably be easier and more intuitive using proof by contradiction, but after talking with the asker, I will provide a direct proof.

$$\begin{array}{lr} 1. & (P \rightarrow Q)\wedge(Q \rightarrow R) & \text{Premise} \\ 2. & P \rightarrow Q &\text{Simplification, 1}\\ 3. & Q \rightarrow R & \text{Simplification, 1}\\ 4. & \neg{P} \vee Q & \text{Conditional Law, 2}\\ 5. & \neg{Q} \vee R & \text{Conditional Law, 3}\\ 6. & Q \vee \neg{Q} & \text{Tautology} \\ 7. & \neg{P} \vee R & \text{Constructive Dilemma, 4,5,6}\\ 8. & P \rightarrow R & \text{Conditional Law, 7}\\ 9. & (P \rightarrow Q) \vee (Q \rightarrow R) &\text{Addition, 2}\\ 10. & (Q \rightarrow P) \vee (Q \rightarrow R) &\text{Addition, 3}\\ 11. & (P \rightarrow Q) \vee (R \rightarrow Q) &\text{Addition, 2}\\ 12. & Q \vee \neg{Q} & \text{Tautology}\\ 13. & (Q \vee \neg{Q}) \vee (P \vee \neg{R}) & \text{Addidition, 12}\\ 14. & (\neg{Q} \vee P) \vee (\neg{R} \vee Q) & \text{Associative Law, 13}\\ 15. & (Q \rightarrow P) \vee (R \rightarrow Q) & \text{Conditional Law, 14}\\ 16. & \big((P \rightarrow Q) \vee (Q \rightarrow R)\big)\wedge \big((Q \rightarrow P) \vee (Q \rightarrow R)\big) & \text{Conjunction, 9,10}\\ 17. & \big((P \rightarrow Q) \vee (R \rightarrow Q)\big)\wedge \big((Q \rightarrow P) \vee (R \rightarrow Q)\big) & \text{Conjunction, 11,15}\\ 18. & \big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee (Q \rightarrow R) & \text{Distributive Law, 16}\\ 19. & \big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee (R \rightarrow Q) & \text{Distributive Law, 17}\\ 20. & \Big(\big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee (Q \rightarrow R)\Big) \wedge & \\ &\Big(\big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee (R \rightarrow Q)\Big) & \text{Conjunction, 18,19}\\ 21. & \big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee \big((Q \rightarrow R) \wedge (R \rightarrow Q) \big) & \text{Distributive Law, 20}\\ 22. & (P \equiv Q) \vee (Q \equiv R) & \text{Definition of Biconditional, 21}\\ \therefore & (P \rightarrow R)\wedge \big((P \equiv Q) \vee (Q \equiv R)\big) & \text{Conjunction, 8,22} \end{array}$$

As desired.

share|improve this answer
    
I think when you moved from 13. to 14. you used both the associative property and the commutativie property of $\lor$. It didn't result in an invalidity though. I don't see how this enables us to move from 22. to 1. ("addition" clearly is NOT reversible... (p $\lor$ q) implies q is NOT an inference rule permitted here). So, unless I've missed something, I think you've only provided "half" of a solution. –  Doug Spoonwood Sep 26 '13 at 5:06
1  
@DougSpoonwood You're right about 13 to 14. I'm sure if you look hard enough there are several times where I combine some uses of associativity and commutativity with other rules. Its such a trivial step, I'm willing to sacrifice rigour for time/readability. About your second point, you're 100% correct. I only proved one direction of the equivalence, thanks for the heads up. I'll work on the other half today, which should be easier. I may do it using proof by contradiction since the asker asked about it in chat. –  Kevin Driscoll Sep 26 '13 at 21:31

I use Polish notation.

By distribution we have 1.

  1. KCprAEpqErq = AKCprEpqKCprErq.

Suppose KCprEpq. Then, by two conjunction eliminations we have Cpr and Epq. Suppose p. Then by detachment, we have r. Also, by detachment we have q (if we have "p" and "Epq", then "q" also). By conditional introduction, we have Cpq. Next suppose q. Since we have Epq also, we can then "reverse detach" p. Since we have p as well as Cpr, we can thus detach r. By conditional introduction, we have Cqr. Thus, by conjunction introduction we have KCpqCqr. So, KCprEpq yields KCpqCqr.

Now suppose KCprErq. Then, by two conjunction eliminations we have Cpr and Erq. Suppose p. Then since we have Cpr also, we can detach r. Since we have Erq also, we can detach q. Thus, Cpq. Next suppose q. Then since we have Erq, we can detach r. Thus, by conditional introduction we have Cqr. So, by conjunction introduction we obtain KCpqCqr.

Since both cases lead to KCpqCqr, AKCprEpqKCprErq implies KCpqCqr.

Suppose KCpqCqr. Then by two conjunction eliminations we have Cpq and Cqr. Suppose p. Suppose p again. Then since we have Cpq also, we obtain q. Since we have q and Cqr, we obtain r. Discharging the first p we obtain Cpr. Now we still have Cpq in play. So, by detachment and the first p supposed, we obtain q. There exists a law which says $\vdash$CpCqEpq. So, thus by two detachments we obtain Epq. By disjunction introduction we thus obtain AEpqErq. By conjunction introduction we then have KCprAEpqErq. Now discharging the first p we have CpKCprAEpqErq.

Suppose Np. We still have Cpq and Cqr. Since there exists a law which says CNpCpr, and we have Np, we get Cpr by detachment. Suppose Nq. There exists a law which says $\vdash$CNpCNqEpq. So, from that law, Np, and Nq we obtain Epq. By disjunction introduction we thus have AEpqErq. So, by conjunction introduction we have KCprAEpqErq. Discharging Nq, we have CNqKCprAEpqErq. Suppose q. Since we have Cqr, by detachment we have r. Since we a law which says $\vdash$CrCqErq, by two detachments we pass to Erq. By disjunction introduction we have AEpqErq. By conjunction introduction we then get KCprAEpqErq. Discharging q we have CqKCprAEpqErq. Now, we have AqNq. Consequently, via AqNq, CqKCprAEpqErq, and CNqKCprAEpqErq we obtain KCprAEpqErq by disjunction elimination under the scope of the hypothesis Np. Thus, discharging Np we obtain CNpKCprAEpqErq.

Now, we have ApNp, CpKCprAEpqErq, and CNpKCprAEpqErq. Thus, by disjunction elimination we obtain KCprAEpqEqr. We still have KCpqCqr in place, and thus by conditional introduction we obtain CKCpqCqrKCprAEpqEqr.

Since we had CKCprAEpqEqrKCpqCqr above, we now infer EKCpqCqrKCprAEpqEqr.

share|improve this answer
    
Wow! This is super confusing LOL! But it looks like you took a lot of time to write it. I never thought this could possible be a solution. I will look up the Polish Notation you linked. –  John Wilson Sep 26 '13 at 2:43
    
Why do you use Polish notation if the OP clearly doesn't? –  Pedro Tamaroff Sep 26 '13 at 2:49
    
@PedroTamaroff I find it easier to use in some respects (after having learned it). I found this problem fairly difficult for me at present. –  Doug Spoonwood Sep 26 '13 at 4:55

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.