Show that (P→Q) ∧ (Q→R) is equivalent to (P→R) ∧ [(P↔Q) ∨ (R↔Q)]

Question

I literally have no idea how to start this proof.

I get to (P→Q) ∧ (Q→R) = (¬P ∨ Q) ∧ (¬Q ∨ R) and then I get stuck.

Answer 1

One possibility is truth tables.

Another possibility is:

(1) Left to right: from $P\rightarrow Q$ and $Q\rightarrow R$, you immediately get $P\rightarrow R$. You also need one of $P\leftrightarrow Q$ or $P\leftrightarrow R$; and the only way for both of these to fail if for $P, Q, R$ to be $TFT$ or $FTF$, but neither of these cases is compatible with both of the conditionals on the left side.

(2) Right to left: You have $P\rightarrow R$, and (at least) one of $P\leftrightarrow Q$ or $R\leftrightarrow Q$. In the case of $P\leftrightarrow Q$, you get $Q\rightarrow R$ by substitution (into $P\rightarrow R$), and you get $P\rightarrow Q$; thus you get the left side. The other case, where you have $R\leftrightarrow Q$ is similar.

Answer 2

You are almost done. Use the logical equivalence of the conditional. "(P→Q)" and "(¬P ∨ Q)" are logically equivalent.

Answer 3

The easiest way is through Truth table method : an 8-rows truth table is quite easy to manage.

Without truth table, we have to do a tedious work using Conjunctive normal form, where :

a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.

In order to apply it, we need the most common Logical equivalences.

---

(LHS)

$(P→Q) ∧ (Q→R) \equiv (\lnot P \lor Q) \land (\lnot Q \lor R) \equiv $

We use Identity law for $\lor$ : $a \lor F \equiv a$ to expand both conjuncts with :

$$F := (R \land \lnot R)$$

and

$$F := (P \land \lnot P)$$

respectively, in order to "insert" the missing literals :

$\equiv [(\lnot P \lor Q) \lor (R \land \lnot R)] \land [(\lnot Q \lor R) \lor (P \land \lnot P)] \equiv $

and then we use distributivity :

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

---

(RHS)

$(P→R) ∧ [(P↔Q) ∨ (R↔Q)] \equiv$

$\equiv (\lnot P \lor R) \land [(P \land Q) \lor (\lnot P \land \lnot Q) \lor (R \land Q) \lor (\lnot R \land \lnot Q)] \equiv$

using the equivalences :

$$(a \rightarrow b) \equiv (\lnot a \lor b)$$

and :

$$(a \leftrightarrow b) \equiv (a \land b) \lor (\lnot a \land \lnot b)$$

Now we use distributivity to rewrite the terms inside the square brackets :

$\equiv (\lnot P \lor R) \land [((P \lor R) \land Q) \lor ((\lnot P \lor \lnot R) \land \lnot Q)] \equiv$

and then we distribute the left sub-formula :

$\equiv [(\lnot P \lor R) \land (P \lor R) \land Q] \lor [(\lnot P \lor R) \land (\lnot P \lor \lnot R) \land \lnot Q] \equiv$

$\equiv [((\lnot P \land P) \lor R) \land Q] \lor [(\lnot P \lor (R \land \lnot R)) \land \lnot Q] \equiv$

Now we use the Negation law : $a \land \lnot a \equiv F$ and again Identity law for $\lor$ to simplify :

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

Now we distribute again :

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

We omit the last clause, using Negation law and Identity law for $\land$ and insert again the missing literals :

$\equiv [(R \lor \lnot P) \lor (Q \land \lnot Q)] \land [(Q \lor \lnot P) \lor (R \land \lnot R)] \land [(R \lor \lnot Q) \lor (P \land \lnot P)] \equiv$

Now we distribute :

$\equiv [(R \lor \lnot P \lor Q) \land (R \lor \lnot P \lor \lnot Q)] \land [(Q \lor \lnot P \lor R) \land (Q \lor \lnot P \lor \lnot R)] \land [(R \lor \lnot Q \lor P) \land (R \lor \lnot Q \lor \lnot P)] \equiv$

and cancel the redundant clauses (3rd and 6th), by Idempotent laws :

$\equiv [(R \lor \lnot P \lor Q) \land (R \lor \lnot P \lor \lnot Q)] \land (Q \lor \lnot P \lor \lnot R)] \land [(R \lor \lnot Q \lor P)] \equiv$

and finally we rearrange the literals into the clauses to get :

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

---

Now we have to compare the final results of the transformations of both sides, and we can check that they are equal.

Thus, we conclude the proof of the equivalence :

$$(P→Q) ∧ (Q→R) \equiv (P→R) ∧ [(P↔Q) ∨ (R↔Q)]$$

Answer 4

One could also show this using natural deduction. That may not be the desired approach, but here is an example showing how that could be done.

Given the left hand side derive the right hand side. On lines 4-10 and 11-17 the two conditionals are written as disjunctions. $P\to R$ is derived on lines 18-21. The right hand side is negated on line 22 leaving a disjunction. From the left disjunct a contradiction is derived.

Next we will consider the right disjunct.

That completes the derivation of the right hand side from the left hand side.

The proof is completed by deriving the left hand side from the right hand side and then deriving the biconditional showing the equivalence of the left hand side and the right hand side.

---

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/