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

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

Answer 2

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