# Conjunction of Disjunction with Negation is Conjunction with Negation

Jump to navigation
Jump to search

## Theorem

- $\left({p \lor q}\right) \land \neg q \dashv \vdash p \land \neg q$

## Proof

By the tableau method of natural deduction:

Line | Pool | Formula | Rule | Depends upon | Notes | |
---|---|---|---|---|---|---|

1 | 1 | $p \land \neg q$ | Premise | (None) | ||

2 | 1 | $p$ | Rule of Simplification: $\land \mathcal E_1$ | 1 | ||

3 | 1 | $p \lor q$ | Rule of Addition: $\lor \mathcal I_1$ | 2 | ||

4 | 1 | $\neg q$ | Rule of Simplification: $\land \mathcal E_2$ | 1 | ||

5 | 1 | $\left({p \lor q}\right) \land \neg q$ | Rule of Conjunction: $\land \mathcal I$ | 3, 4 |

$\blacksquare$

... and its converse:

By the tableau method of natural deduction:

Line | Pool | Formula | Rule | Depends upon | Notes | |
---|---|---|---|---|---|---|

1 | 1 | $\left({p \lor q}\right) \land \neg q$ | Premise | (None) | ||

2 | 1 | $\left({p \land \neg q}\right) \lor \left({q \land \neg q}\right)$ | Sequent Introduction | 1 | Conjunction Distributes over Disjunction | |

3 | 3 | $q \land \neg q$ | Assumption | (None) | ||

4 | 3 | $\bot$ | Principle of Non-Contradiction: $\neg \mathcal E$ | 3, 3 | ||

5 | $\neg \left ({q \land \neg q}\right)$ | Proof by Contradiction: $\neg \mathcal I$ | 3 – 4 | Assumption 3 has been discharged | ||

6 | 1 | $p \land \neg q$ | Sequent Introduction | 2, 5 | Disjunctive Syllogism |

$\blacksquare$