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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

Here's a more complete answer using equivalences only:

I reduce each of the two expressions as much as possible.

(All of these are equivalences. I'll freely use commutative/associative laws in what follows to disregard order and drop excess parentheses.)

1. $(P\rightarrow Q) \land (Q \rightarrow R)$

2. $(\lnot P \lor Q) \land (\lnot Q \lor R)$ (def. of $\rightarrow$)

3. $[\lnot P \land (\lnot Q \lor R)] \lor [Q \land (\lnot Q \lor R)]$ (distrib)

4. $(\lnot P \land \lnot Q) \lor (\lnot P \land R) \lor (Q \land R)$ (distrib & tautology [skipped some intermediates])

Now for the other side:

1. $(P \rightarrow R) \land [(P \leftrightarrow Q) \lor (Q \leftrightarrow R)]$

2. $(\lnot P \lor R) \land [(P \land Q) \lor (\lnot P \land \lnot Q) \lor (R \land Q) \lor (\lnot R \land \lnot Q)]$ (see the lemma below)

3. $(\lnot P \land P \land Q) \lor (\lnot P \land \lnot P \land Q) \lor (\lnot P \land R \land Q) \lor (\lnot P \land \lnot R \land \lnot Q) \lor (R \land P \land Q) \lor (R \land \lnot P \land \lnot Q) \lor (R \land R \land Q) \lor (R \land \lnot R \land \lnot Q)$ (distrib)

4. $(\lnot P \land Q) \lor (\lnot P \land R \land Q) \lor (\lnot P \land \lnot R \land \lnot Q) \lor (R \land P \land Q) \lor (R \land \lnot P \land \lnot Q) \lor (R \land Q)$ (tautology and idempotent)

5. $(R \land Q) \lor [(\lnot P \land R \land Q) \lor (\lnot P \land R \land \lnot Q)] \lor [(\lnot P \land \lnot Q \land R) \lor (\lnot P \land \lnot Q \land \lnot R)]$ (comm/assoc to rearrange, idempotent to duplicate $(\lnot P \land R \land \lnot Q)$ and absorption to get rid of $(R \land P \land Q)$)

6. $(R\land Q) \lor (\lnot P \land R) \lor (\lnot P \land \lnot Q)$ (distrib and tautology)

Now notice 4 at the top is the same as 6 on the bottom, by comm/assoc laws.

The Lemma noted above: $A \leftrightarrow B$ is equivalent to $(A\land B) \lor (\lnot A \land \lnot B)$. Showing this: It's $(A \rightarrow B) \land (B \rightarrow A)$ which is equivalent to $(\lnot A \lor B) \land (A \lor \lnot B)$ which, distributing twice, is equivalent to $(\lnot A \land A) \lor (\lnot A \land \lnot B) \lor (B \land A) \lor (B \land \lnot B)$ which is $(\lnot A \land \lnot B) \lor (B \land A)$ by tautology laws.

Answer 4

You can use implication's transitivity

(proof here:http://www.personal.psu.edu/tcr2/311w/iftransitive.pdf)

Just like: $$((P\implies Q)\wedge (Q\implies R))\iff(P\implies R)$$ We have:

$$(P\implies R)\wedge[(P\iff Q)\vee(Q\iff R)]\iff$$ $$(P\implies R)\wedge[(P\implies Q \wedge Q\implies P)\vee (Q\implies R\wedge R\implies Q)]\iff$$ $$((P\implies R \wedge P\implies Q\wedge Q\implies P)\vee(P\implies R\wedge Q\implies R\wedge R\implies Q))\iff$$ $$((Q\implies P\wedge P\implies R\wedge P\implies Q)\vee(Q\implies R\wedge P\implies R\wedge R\implies Q))\iff $$ $$((Q\implies R \wedge P\implies Q)\vee(Q\implies R\wedge P\implies Q))\iff(Q\implies R\wedge P\implies Q)$$ $$\iff(P\implies Q\wedge Q\implies R)\iff(P\implies R)$$ $$Q.E.D.$$