Als n² even is, dan is n even

Bewijs: voor elk geheel getal $n$ geldt: als $n^2$ even is, dan is $n$ even.

Schrijf de contrapositie op: Ontken beide delen en verwissel ze: "als $n$ niet even is, dan is $n^2$ niet even" = Als $n$ oneven is, dan is $n^2$ oneven

Neem de ontkende conclusie aan: Neem aan dat $n$ oneven is, dus $n = 2k + 1$ voor een geheel getal $k$ = $n = 2k + 1$

Kwadrateer en werk haakjes weg: $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1$ = $n^2 = 4k^2 + 4k + 1$

Schrijf het in de vorm 2m + 1: $n^2 = 2(2k^2 + 2k) + 1$, en $m = 2k^2 + 2k$ is een geheel getal = $n^2$ is oneven

Concludeer: We hebben "$n$ oneven $\Rightarrow$ $n^2$ oneven" bewezen, de contrapositie van de bewering = Als $n^2$ even is, dan is $n$ even

Answer: De contrapositie (als $n$ oneven is, dan is $n^2$ oneven) is waar, dus de oorspronkelijke bewering is waar. QED

Als n² oneven is, dan is n oneven

Bewijs: voor elk geheel getal $n$ geldt: als $n^2$ oneven is, dan is $n$ oneven.

Schrijf de contrapositie op: Niet oneven betekent even, zowel voor de conclusie als voor de aanname = Als $n$ even is, dan is $n^2$ even

Neem de ontkende conclusie aan: Neem aan dat $n$ even is, dus $n = 2k$ voor een geheel getal $k$ = $n = 2k$

Kwadrateer: $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$ = $n^2 = 2(2k^2)$

Concludeer: $2k^2$ is een geheel getal, dus $n^2$ is even: we zijn bij $\neg p$ uitgekomen = De contrapositie is bewezen

Answer: Omdat "$n$ even $\Rightarrow$ $n^2$ even" waar is, is "$n^2$ oneven $\Rightarrow$ $n$ oneven" ook waar. QED

Als xy oneven is, dan zijn x en y oneven

Bewijs: voor alle gehele getallen $x$ en $y$ geldt: als $xy$ oneven is, dan zijn $x$ en $y$ allebei oneven.

Ontken de conclusie zorgvuldig: De ontkenning van "$x$ is oneven en $y$ is oneven" is "$x$ is even of $y$ is even" (en wordt of) = $\neg q$: $x$ is even of $y$ is even

Schrijf de contrapositie op: Als $x$ even is of $y$ even is, dan is $xy$ niet oneven = Als $x$ of $y$ even is, dan is $xy$ even

Geval 1: x is even: $x = 2k$, dus $xy = 2ky = 2(ky)$, en $ky$ is een geheel getal = $xy$ is even

Geval 2: y is even: $y = 2j$, dus $xy = 2xj = 2(xj)$, en $xj$ is een geheel getal = $xy$ is even

Concludeer: In beide gevallen is $xy$ even, dus de contrapositie klopt = Als $xy$ oneven is, dan zijn $x$ en $y$ oneven

Answer: Elk geval van de ontkende conclusie leidt tot $xy$ even, dus de oorspronkelijke bewering is waar. QED

Als x + y ≥ 10, dan x ≥ 5 of y ≥ 5

Bewijs: voor alle reële getallen $x$ en $y$ geldt: als $x + y \geq 10$, dan is $x \geq 5$ of $y \geq 5$.

Ontken de conclusie: De ontkenning van "$x \geq 5$ of $y \geq 5$" is "$x < 5$ en $y < 5$" (of wordt en, $\geq$ wordt $<$) = $\neg q$: $x < 5$ en $y < 5$

Ontken de aanname: De ontkenning van $x + y \geq 10$ is $x + y < 10$ = $\neg p$: $x + y < 10$

Neem de ontkende conclusie aan: Neem aan: $x < 5$ en $y < 5$ = Twee ongelijkheden

Tel de ongelijkheden op: $x + y < 5 + 5 = 10$ = $x + y < 10$

Concludeer: Vanuit $\neg q$ zijn we bij $\neg p$ uitgekomen = De oorspronkelijke bewering is waar

Answer: Als $x < 5$ en $y < 5$, dan is $x + y < 10$. Dat is de contrapositie, dus $x + y \geq 10$ dwingt af dat $x \geq 5$ of $y \geq 5$. QED

De methode kiezen: n² - 6n + 5

Bewijs: voor elk geheel getal $n$ geldt: als $n^2 - 6n + 5$ even is, dan is $n$ oneven.

Probeer eerst de directe weg: Aannemen dat "$n^2 - 6n + 5$ even is" geeft een vergelijking $n^2 - 6n + 5 = 2m$ die weinig over $n$ zegt = Het directe bewijs is omslachtig

Schrijf de contrapositie op: Als $n$ even is, dan is $n^2 - 6n + 5$ oneven = $\neg q \to \neg p$

Neem n even aan en vul in: $n = 2k$, dus $n^2 - 6n + 5 = 4k^2 - 12k + 5$ = $4k^2 - 12k + 5$

Schrijf het in de vorm 2m + 1: $4k^2 - 12k + 5 = 2(2k^2 - 6k + 2) + 1$ = De uitdrukking is oneven

Controleer met een getal: $k = 5$, $n = 10$: $100 - 60 + 5 = 45 = 2 \cdot 22 + 1$ = Oneven, zoals voorspeld

Answer: Als $n$ even is, dan is $n^2 - 6n + 5$ oneven. Dat is de contrapositie, dus de oorspronkelijke bewering is waar. QED

Mistake: De omgekeerde bewijzen in plaats van de contrapositie: bij "als $n^2$ even is, dan is $n$ even" aannemen dat $n$ even is en laten zien dat $n^2$ even is

Why: Dan bewijs je $q \to p$, de omgekeerde bewering, en dat is een andere bewering. Een bewering en haar omgekeerde zijn niet equivalent.

Correct: Ontken beide delen en verwissel ze: neem aan dat $n$ oneven is ($\neg q$) en laat zien dat $n^2$ oneven is ($\neg p$).

Mistake: "$x$ en $y$ zijn oneven" ontkennen als "$x$ en $y$ zijn even"

Why: De conclusie is al onwaar zodra één van de getallen even is. "Allebei even" dekt maar een deel van de gevallen, dus het bewijs zou onvolledig zijn.

Correct: "Niet ($a$ en $b$)" is "niet $a$ of niet $b$": $x$ is even of $y$ is even. Bewijs daarna elk geval.

Mistake: $x \geq 5$ ontkennen als $x \leq 5$

Why: De waarde $x = 5$ voldoet aan zowel $x \geq 5$ als $x \leq 5$, dus $x \leq 5$ is niet het tegenovergestelde van $x \geq 5$.

Correct: De ontkenning van $x \geq 5$ is $x < 5$, en de ontkenning van $x > 5$ is $x \leq 5$.

Mistake: $\neg q$ aannemen en dan op zoek gaan naar "een of andere tegenspraak"

Why: Zo meng je twee methoden. Bij een bewijs via contrapositie is er geen tegenspraak: je hebt één duidelijk doel.

Correct: Neem $\neg q$ aan en werk door tot je precies bij $\neg p$ bent. Zoeken naar een willekeurige tegenspraak hoort bij het bewijs uit het ongerijmde.

Kwaliteitscontrole

Controleurs gebruiken contrapositie om gevallen uit te sluiten zonder elk artikel twee keer te wegen.

Regel: als een pak van 4 dozen minstens 2000 g weegt, dan weegt minstens één doos minstens 500 g. Contrapositie: als elke doos minder dan 500 g weegt, weegt het pak minder dan 2000 g.

Software testen

Programmeurs testen code met contrapositie: als de code correct is, geeft een test de juiste uitkomst, dus een foute uitkomst bewijst een bug.

Een functie moet $f(n) = 3n + 2$ berekenen. We hebben bewezen: als $f(n)$ oneven is, dan is $n$ oneven. Contrapositie: een even $n$ moet een even uitkomst geven.

Controlecijfers in codes

Veel codes gebruiken een eenvoudige regel om tikfouten te vinden. De contrapositie vertelt je wanneer een code zeker fout is.

Regel: als een code geldig is, dan is de som van de cijfers deelbaar door 9. Contrapositie: als de cijfersom niet deelbaar is door 9, is de code niet geldig.

Q: Waarom bewijst de contrapositie de oorspronkelijke bewering?

A: Omdat ze logisch equivalent zijn: in de waarheidstabel zijn $p \to q$ en $\neg q \to \neg p$ in precies dezelfde rij onwaar ($p$ waar, $q$ onwaar) en in alle andere rijen waar. Wie de ene bewijst, heeft ook de andere bewezen.

Q: Hoe weet ik wanneer ik contrapositie moet gebruiken in plaats van een direct bewijs?

A: Kijk naar de aanname. Als die lastig te gebruiken is (een bewering over $n^2$, een product, een som) terwijl de ontkende conclusie je een formule geeft ($n = 2k$, $n = 2k + 1$, $x < 5$ en $y < 5$), is contrapositie meestal korter.

Q: Wat is het verschil met een bewijs uit het ongerijmde?

A: Bij een bewijs uit het ongerijmde neem je $p$ en $\neg q$ aan en zoek je een of andere onmogelijke situatie. Bij een bewijs via contrapositie neem je alleen $\neg q$ aan en moet je precies bij $\neg p$ uitkomen. Elk bewijs via contrapositie kun je herschrijven als bewijs uit het ongerijmde, maar niet andersom.

Q: Als ik de contrapositie bewijs, is de omgekeerde bewering dan ook waar?

A: Niet vanzelf. De omgekeerde $q \to p$ is een aparte bewering. Zo zijn "als $n^2$ even is, dan is $n$ even" en de omgekeerde "als $n$ even is, dan is $n^2$ even" allebei waar, maar elk heeft een eigen bewijs nodig.