Editing Proof by contradiction (section)

== Justification ==

In [[classical logic]] the principle may be justified by the examination of the [[truth table]] of the proposition ''¬¬P ⇒ P'', which demonstrates it to be a [[tautology (logic)|tautology]]:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:80px" | ''p''
! style="width:80px" | {{math|''¬p''}}
! style="width:80px" | {{math|''¬¬p''}}
! style="width:80px" | {{math|''¬¬p ⇒ p''}}
|-
! style="background:papayawhip" | T
! F
! T
! T
|-
! style="background:papayawhip" | F
! T
! F
! T
|}

Another way to justify the principle is to derive it from the [[law of the excluded middle]], as follows. We assume ''¬¬P'' and seek to prove ''P''. By the law of excluded middle ''P'' either holds or it does not:

# if ''P'' holds, then of course ''P'' holds.
# if ''¬P'' holds, then we derive falsehood by applying the [[law of noncontradiction]] to ''¬P'' and ''¬¬P'', after which the [[principle of explosion]] allows us to conclude ''P''.

In either case, we established ''P''. It turns out that, conversely, proof by contradiction can be used to derive the law of excluded middle.

In [[sequent calculus|classical sequent calculus LK]] proof by contradiction is derivable from the [[sequent calculus#Inference rules|inference rules]] for negation:

: <math>\cfrac{\cfrac{\cfrac{\ }{\Gamma, P \vdash P, \Delta} \; (I)}{\Gamma, \vdash \lnot P, P, \Delta} \; ({\lnot}R)}{\Gamma, \lnot\lnot P \vdash P, \Delta} \; ({\lnot}L)</math>