Proof of distributivity of implication over implication

840 Views Asked by At

The Wikipedia page on the distributive property claims one should be able to distribute implication over implication (Distribution of implication):

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

I verified it using a truth table, but I am unable to prove it algebraically. Here's what I have so far:

$$ \begin{align} P \rightarrow (Q \rightarrow R) &\equiv P \rightarrow (\lnot Q \lor R) \tag{Material Implication} \\ &\equiv \lnot P \lor (\lnot Q \lor R) \tag{Material Implication} \\ &\equiv (\lnot P \lor \lnot P) \lor (\lnot Q \lor R) \tag{Idempotence} \\ &\equiv (\lnot P \lor \lnot Q) \lor (\lnot P \lor R) \tag{Associativity} \\ &\equiv \lnot (P \land Q) \lor (\lnot P \lor R) \tag{DeMorgan's} \\ &\equiv \lnot (P \land Q) \lor (P \rightarrow R) \tag{Material Implication} \\ &\equiv (P \land Q) \rightarrow (P \rightarrow R) \tag{Material Implication} \\ \end{align} $$

I don't know the correct way to state the Idempotence step, but I'm using $P \equiv P \lor P$. I'm trying to avoid using Distribution of disjunction over disjunction, also advertised on the same Wikipedia page, but the effect is the same.

Have I made any mistakes? How do I proceed from here?

1

There are 1 best solutions below

1
On BEST ANSWER

It's probably easier to start with the right hand side:

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

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

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

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

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

$\neg Q \lor \neg P \lor R \equiv$

$\neg P \lor \neg Q \lor R \equiv$

$P \to (Q \to R)$