Assistance in completing the proof: (P → Q)∧(Q → R) is equivalent to (P → R)∧ [(P ↔ Q) ∨ (R ↔ Q)] using logical equivalencies

Solution 1:

Here are some useful but elementary equivalence principles:

Complement

$$P \lor \neg P \Leftrightarrow \top$$

$$P \land \neg P \Leftrightarrow \bot$$

Annihilation

$$P \lor \top \Leftrightarrow \top$$

$$P \land \bot \Leftrightarrow \bot$$

Identity

$$P \land \top \Leftrightarrow P$$

$$P \lor \bot \Leftrightarrow P$$

Idempotence

$$P \lor P = P$$

$$P \land P = P$$

Also, as you noticed, the whole big right terms does indeed not get you anywhere ... you need to work in the left term $\neg P \lor R$

So, starting a few lines from before you get 'stuck' (because indeed, you're just going in loops at that point) (and also throwing in some necessary parentheses):

$(\neg P \lor R) \land [\color{red}((\neg P \lor Q) \land (P \lor \neg Q)\color{red}) \lor \color{red}((\neg R \lor Q) \land (R \lor \neg Q)\color{red})] =$

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

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

(dropping unncessary parentheses)

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

OK, now two handy laws are:

Absorption

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

Reduction

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

Applying these, we get:

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

OK, and now 'unDistribute' the $\neg P $ and the $R$:

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

and now you can distribute the $\neg Q$ and the $Q$:

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

(dropping unncessary parentheses)

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

And now you can use those simplification laws from the start of my post:

(Complement:)

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

(Annihilation:)

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

(Identity:)

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

(Distribution:)

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

(Commutation:)

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

(Idempotence:)

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

(Distribution 2*2*2:)

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

(Complement:)

$=(\neg P \lor R) \land (\neg P \lor \neg Q \lor R) \land (\neg P \lor Q) \land (\neg P \lor \top) \land (\neg P \lor R) \land (\neg Q \lor R) \land (R \lor \neg P \lor Q) \land (R \lor \top)$

(Annihilation:)

$=(\neg P \lor R) \land (\neg P \lor \neg Q \lor R) \land (\neg P \lor Q) \land \top \land (\neg P \lor R) \land (\neg Q \lor R) \land (R \lor \neg P \lor Q) \land \top$

(Identity:)

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

(two Absorptions and an Idempotence:)

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

Phew! Almost there ....

Now, use:

Adjacency

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

Applied to where we were:

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

(Adjacency:)

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

(Two Absorptions)

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

.. and finally we're there! Sheesh!