Kontrapositivt bevis

En veldig nyttig 

$P\Rightarrow Q$

ekvivalent med

$\mathrm{ikke}Q\Rightarrow \mathrm{ikke}P$

Siden de to utrykkene er ekvivalente, holder enten ingen eller begge. Dermed kan vi bevise det andre uttrykket for å bevise det første. Når vi gjør dette, kaller vi det et kontrapositivt bevis.

Eksempel 1:

Vis at hvis $n$ er et heltall og $n^2$ er et oddetall, så er $n$ også et oddetall.

Bevis:

La påstandene $P$ og $Q$ være som følger:

P="$n^2$ er et oddetall"

Q="$n$ er et oddetall".

Påstanden vi skal vise blir da $P\Rightarrow Q$. Vi vil bruke et kontrapositivt bevis, så vi vil heller vise: $\mathrm{ikke}Q\Rightarrow \mathrm{ikke}P$.

$\mathrm{ikke}Q$ er det motsatte av $Q$, altså at $n$ ikke er et oddetall. Da er $n$ et partall.

$\mathrm{ikke}P$ er det motsatte av $P$, altså at $n^2$ ikke er et oddetall. Da er $n^2$ et partall.

Anta at $n$ er et partall.

Da finnes det et heltall $k$ slik at $n=2k$.

$n^2={\left(2k\right)}^2=4k^2$.

Og vi ser at dette kan deles på $2$, og dermed er også $n^2$ et partall.

Dette beviser $\mathrm{ikke}Q\Rightarrow \mathrm{ikke}P$ og dermed også $P\Rightarrow Q$.

Sagt med ord: Vi viste at hvis $n$ er et partall er $n^2$ et partall, og da vet vi også at hvis $n^2$ er et oddetall må $n$ være et oddetall.