2
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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$. $\endgroup$ Jul 22, 2019 at 1:31
  • $\begingroup$ @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. $\endgroup$
    – neurozero
    Jul 22, 2019 at 1:45
  • $\begingroup$ 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. $\endgroup$ Jul 22, 2019 at 18:35

1 Answer 1

3
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .