Kontraposition

Kontraposition er en metode, hvor man i stedet for at bevise et udsagn direkte, viser den logisk ækvivalente sætning.

Hvis vi vil bevise en påstand af typen "hvis A, så B", kan vi i stedet bevise "hvis ikke B, så ikke A". Da de to udsagn er logisk ens, er beviset gyldigt.

Metoden er nyttig, når det er vanskeligt at gå direkte fra A til B, men lettere at argumentere baglæns fra ikke-B til ikke-A.

Kontraposition giver dermed en alternativ vej til at nå det samme resultat.

Fremgangsmåde

Et bevis ved kontraposition kan opdeles i tre trin:

1. Skriv udsagnet "hvis A, så B" om til "hvis ikke B, så ikke A".
2. Antag, at konklusionen B ikke gælder.
3. Vis logisk, at dette medfører, at forudsætningen A heller ikke kan gælde.

Eksempel 1

Vi vil bevise: Hvis $ \large n^2 $ er ulige, så er $ \large n $ ulige. Direkte kan dette være svært, men ved kontraposition bliver det:

Hvis $ \large n $ er lige, så er $ \large n^2 $ lige.

Skriv $ \large n = 2a $. Da får vi:

$$ \large n^2 = (2a)^2 = 4a^2 = 2(2a^2) $$

Altså er $ \large n^2 $ lige. Dermed er kontrapositionen vist, og den oprindelige påstand er bevist.

Eksempel 2

Vi vil bevise: Hvis et helt tal $ \large n $ er deleligt med 6, så er det deleligt med 3. Kontrapositionen lyder:

Hvis $ \large n $ ikke er deleligt med 3, så er $ \large n $ ikke deleligt med 6.

Antag, at $ \large n $ ikke er deleligt med 3. Det betyder, at $ \large n = 3q + r $ med rest $ \large r = 1 $ eller $ \large r = 2 $. I begge tilfælde er $ \large n $ ikke deleligt med 6, for et tal skal mindst være deleligt med 3 for at kunne være deleligt med 6. Dermed er udsagnet bevist ved kontraposition.

Eksempel 3

Vi vil bevise: Hvis en brøk $ \large \frac{a}{b} $ er forkortet til enkleste form, så er $ \large a $ og $ \large b $ ikke begge delelige med det samme primtal. Kontrapositionen lyder:

Hvis $ \large a $ og $ \large b $ er delelige med det samme primtal, så er brøken $ \large \frac{a}{b} $ ikke i enkleste form.

Antag, at både $ \large a $ og $ \large b $ er delelige med et primtal $ \large p $. Da kan vi skrive:

$$ \large a = p \cdot m \quad \text{og} \quad b = p \cdot n $$

Brøken bliver da:

$$ \large \frac{a}{b} = \frac{p \cdot m}{p \cdot n} = \frac{m}{n} $$

Dermed kan brøken forkortes med $ \large p $, hvilket viser, at den oprindelige brøk ikke var i enkleste form. Kontrapositionen er dermed vist, og den oprindelige påstand er bevist.

Beviser ved kontraposition er ofte kortere og mere overskuelige end direkte beviser, når man arbejder med talteoretiske egenskaber og divisibilitet. Teknikken giver en anden vinkel på et problem, men resultatet er logisk fuldstændig det samme.