How to prove this distributive law using natural deduction

$(q \lor r)\wedge p\vdash(q\wedge p)\lor (r\wedge p)$ After making the first assumption and splitting it up using ∧-elimination, I get stuck. Can anyone help?

31.5k 11 11 gold badges 63 63 silver badges 123 123 bronze badges asked Feb 4, 2015 at 18:11 201 2 2 silver badges 10 10 bronze badges

$\begingroup$ Eliminate the conjunction, then do a proof by cases and in both cases infer $(q\wedge p)\lor (r\wedge p)$. $\endgroup$

Commented Feb 4, 2015 at 18:17

$\begingroup$ We have both $q \lor r$ and $p$. If $q$, then $q \land p$ so $(q\land p)\lor (r\land p)$. You can do something similar in the $r$ case. $\endgroup$

Commented Feb 4, 2015 at 18:18

1 Answer 1

$\begingroup$

In natural deduction, we will have something like the following deduction rule, $\lor$-elimination:

From $\Gamma, \phi \vdash \chi$ and $\Delta, \psi \vdash \chi$, infer $\Gamma, \Delta, \phi \lor \psi \vdash \chi$.

where $\phi, \psi, \chi$ are formulas, and $\Gamma, \Delta$ are sets of formulas. The name stems from the fact that in the last sequent, the antecedent contains a disjunction that the consequent doesn't.

In the present case, we are seeking to prove: $$q \lor r, p \vdash (q \land p) \lor (r \land p)$$

Can you see how to use $\lor$-elimination to achieve this?