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

Question

There is a proof in a previous thread that converts the two expressions (P → Q)∧(Q → R) and (P → R)∧ [(P ↔ Q) ∨ (R ↔ Q)] to a CNF-formula thereby proving their equivalencies.

I am approaching the proof from an entirely different proof technique and am stuck. Instead of using truth tables, or converting these two expressions to the same CNF/DNF-formulas I'd rather prove this by using logical equivalencies.

I am having trouble filling in the missing steps, as I get into a distributive property loop in my attempt to group and eliminate terms.

Can someone show me how to complete the proof that I started and help me fill in my missing steps?

Below is my proof attempt:

$(P \to R)\land [(P \def\liff{\leftrightarrow}\liff Q) \lor (R \liff Q)] =$

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

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

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

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

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

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

…steps...

$(\lnot P \lor Q) \land (\lnot R\to\lnot Q)=$

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

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

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

Q.E.D

I would like to see how to complete the "steps" part, as this is where my chain of distributive property loops begin that don't lead me closer to the conclusion. Could someone show me a complete proof?

Answer 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!

Answer 2

Your approach - which I continued in my first Answer - effectively puts the statements into their CNF ... which is what you were trying to avoid.

So, I figure I would give an Alternative answer, working with the whole conditionals, rather than breaking the statements down all the way to literals.

Now, this is going to require some equivalence principles involving conditionals. Notice that in my other answer I showed that

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

This equivalence is actually known to be the Consensus Theorem, which also has a conditional form:

Conditional Consensus

$$(P \rightarrow R) \land (P \rightarrow Q) \land (Q \rightarrow R) = (P \rightarrow Q) \land (Q \rightarrow R)$$

OK, that's the key equivalence I'll be using, but I want one more, which is:

Conditional Tautology

$$(P \rightarrow Q) \lor (Q \rightarrow R) = \top$$

OK, with that, here goes:

$(P \rightarrow R) \land ((P \leftrightarrow Q) \lor (Q \leftrightarrow R))=$

(Work out biconditional as two conditionals:)

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

(DIstribution of $P \rightarrow R$:)

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

(Consensus Conditional form!)

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

(Undistribution of three terms in common:)

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

(conditional Consensus and Conditional Tautology:)

$((P \rightarrow Q) \land (Q \rightarrow R)) \land \top=$

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

Ah, much better!