Bewijs door contrapositie

Het bewijs door contrapositie is een methode om het wiskundige bewijs te geven van de stelling

als ${\displaystyle A}$ dan ${\displaystyle B}$,

door het bewijzen van de omgekeerde stelling

als niet ${\displaystyle B}$ dan niet ${\displaystyle A}$.

In de klassieke logica is de tweede stelling equivalent aan de eerste: een bewijs van de ene stelling is ook een bewijs voor de andere stelling.

Dat is in de intuïtionistische logica anders. Een bewijs dat 'als A dan B' betekent ook dat 'als niet B dan niet A' geldt, maar die redenering geldt in de andere richting niet.

Voorbeelden

• ${\displaystyle A\Rightarrow B\equiv \neg {A}\lor B\equiv \neg {B}\Rightarrow \neg {A}}$

${\displaystyle A\Rightarrow B,\ \neg {A}\lor B}$ en ${\displaystyle \neg {B}\Rightarrow \neg {A}}$ hebben dezelfde waarheidstabel.

• De volgende stelling kan met contrapositie worden bewezen:

Gegeven een positief geheel getal ${\displaystyle n}$. Als ${\displaystyle n}$ geen kwadraat is, is ${\displaystyle {\sqrt {n\ }}}$ irrationaal.

Bewijs daartoe de gelijkwaardige stelling:

Gegeven een positief geheel getal ${\displaystyle n}$. Als ${\displaystyle {\sqrt {n\ }}}$ een rationaal getal is, dan is ${\displaystyle n}$ een kwadraat.

Neem aan dat ${\displaystyle {\sqrt {n\ }}}$ rationaal is. Dan zijn er gehele getallen ${\displaystyle a}$ en ${\displaystyle b}$ zodat ${\displaystyle {\sqrt {n\ }}={\frac {a}{b}}}$ en ggd${\displaystyle (a,b)=1}$. Dan kan ${\displaystyle n={\frac {a^{2}}{b^{2}}}}$ niet verder worden vereenvoudigd en is ${\displaystyle b^{2}=1}$, omdat ${\displaystyle n}$ een geheel getal is. Dus is ${\displaystyle n=a^{2}}$. Daarmee is de omgekeerde, gelijkwaardige stelling bewezen en door contrapositie ook de stelling zelf.