[Math] How to prove the distributive property without using truth tables

logicpropositional-calculus

I did it with using truth tables but I am inquisitive about how to proof the distributive property without using truth tables (i.e using the other rules of replacement or inference).

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

and

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

Best Answer

Here's a hint how you might start constructing a proof of the first biconditional in a standard natural deduction system.

You need to prove the two halves of the conditional separately. So, to go left to right, assume the antecedent $(P \land (Q \lor R))$ and aim for the consequent $(P \land (Q \lor R)) \to ((P \land Q) \lor (P \land R))$. Plainly you need to extract the two conjuncts $P$ and $(Q \lor R)$ from your assumption. And now obviously the only way forward is to use $\lor$-elimination.

So you now need to fill in the following schematic proof:

$\quad|\quad(P \land (Q \lor R)) \quad\quad\text{assumption}\\ \quad|\quad P \\ \quad|\quad(Q \lor R))\\ \quad|\quad|\quad Q \quad\quad\quad\quad\quad\text{ assumption}\\ \quad|\quad|\quad ...\\ \quad|\quad|\quad ((P \land Q) \lor (P \land R))\\ \quad|\quad|\quad --\\ \quad|\quad|\quad R\quad\quad\quad\quad\quad\text{ assumption}\\ \quad|\quad|\quad ...\\ \quad|\quad|\quad ((P \land Q) \lor (P \land R))\\ \quad|\quad ((P \land Q) \lor (P \land R))\quad\text{ by or-elimination, discharging assumptions}\ Q,\ R\\ \quad (P \land (Q \lor R)) \to ((P \land Q) \lor (P \land R)) \quad\text{by conditional proof}\\ $

Do you see understand this sort of proof strategy? Do you see how to fill in the gaps??

If you do, then you'll easily be able to produce similar proofs for the reverse conditional, and likewise for the two halves of your other biconditional.

If you don't, then have a look e.g. at Paul Teller's Formal Logic Primer, freely available online.

Related Question