Proof by Contradiction/Variant 1

Theorem

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

Proof

By the tableau method of natural deduction:

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$p \vdash \left({q \land \neg q}\right)$	Premise	(None)
2		2	$p$	Assumption	(None)
3		1, 2	$q \land \neg q$	Sequent Introduction	1, 2	by hypothesis
4		1, 2	$q$	Rule of Simplification: $\land \mathcal E_1$	3
5		1, 2	$\neg q$	Rule of Simplification: $\land \mathcal E_2$	3
6		1, 2	$\bot$	Principle of Non-Contradiction: $\neg \mathcal E$	4, 5
7		1	$\neg p$	Proof by Contradiction: $\neg \mathcal I$	2 – 6	Assumption 2 has been discharged

$\blacksquare$

Sources

• 1965: E.J. Lemmon: Beginning Logic ... (previous) ... (next): $\S 1.3$: Conjunction and Disjunction