Bewijs door contrapositie

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

als $A$ dan $B$,

door het bewijzen van de omgekeerde stelling

als niet $B$ dan niet $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

• $A\Rightarrow B\equiv \mathrm{\neg }A\vee B\equiv \mathrm{\neg }B\Rightarrow \mathrm{\neg }A$

$A\Rightarrow B,\mathrm{\neg }A\vee B$ en $\mathrm{\neg }B\Rightarrow \mathrm{\neg }A$ hebben dezelfde waarheidstabel.

• De volgende stelling kan met contrapositie worden bewezen:

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

Bewijs daartoe de gelijkwaardige stelling:

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

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