Conjunction implies Disjunction of Conjunctions with Complements
Jump to navigation
Jump to search
Theorem
- $p \land q \vdash \left({p \land r}\right) \lor \left({q \land \neg r}\right)$
Proof
By the tableau method of natural deduction:
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $p \land q$ | Premise | (None) | ||
| 2 | $r \lor \neg r$ | Law of Excluded Middle | (None) | |||
| 3 | 1 | $p$ | Rule of Simplification: $\land \EE_1$ | 1 | ||
| 4 | 1 | $q$ | Rule of Simplification: $\land \EE_2$ | 1 | ||
| 5 | 5 | $r$ | Assumption | (None) | ||
| 6 | 1, 5 | $p \land r$ | Rule of Conjunction: $\land \II$ | 1, 5 | ||
| 7 | 1, 5 | $\left({p \land r}\right) \lor \left({q \land \neg r}\right)$ | Rule of Addition: $\lor \II_1$ | 6 | ||
| 8 | 8 | $\neg r$ | Assumption | (None) | ||
| 9 | 1, 8 | $q \land \neg r$ | Rule of Conjunction: $\land \II$ | 4, 8 | ||
| 10 | 1, 8 | $\left({p \land r}\right) \lor \left({q \land \neg r}\right)$ | Rule of Addition: $\lor \II_2$ | 9 | ||
| 11 | 1 | $\left({p \land r}\right) \lor \left(q \land \neg r\right)$ | Proof by Cases: $\text{PBC}$ | 2, 5 – 7, 8 – 10 | Assumptions 5 and 8 have been discharged |
$\blacksquare$