Conjunction of Disjunction with Negation is Conjunction with Negation

From ProofWiki
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:

$p \land \neg q \vdash \left({p \lor q}\right) \land \neg q$
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:

$\left({p \lor q}\right) \land \neg q \vdash p \land \neg q$
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$