# Proof of distributivity of implication over implication

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?

• One error in your calculation is the $\not\equiv$ at the very end. You could check the desired result by comparing truth tables, or you could compute that both sides are equivalent to $(P\land Q)\to R$. Another alternative is to compute the disjunctive or conjunctive normal forms of both sides of the desired equivalence; both of them are $(\neg P)\lor(\neg Q)\lor R$. Jul 22, 2019 at 1:31
• @AndreasBlass You're right, I certainly haven't proven that they are not equivalent. I'll remove that line. Thanks for the advice on normal forms. Jul 22, 2019 at 1:45
• Incidentally, the equivalence holds constructively, so (assuming you have a rich enough set of rules/axioms) there is a proof that doesn't use material implication or de Morgan's law neither of which are constructive equivalences. In particular, there's a proof that only uses rules and axioms involving $\to$ and no other connectives. Jul 22, 2019 at 18:35

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

• Looks good, thanks! I think my keeping unnecessary parentheses around were preventing me from seeing opportunities to rearrange stuff! Jul 22, 2019 at 3:03