9.3 Kontrapositiv og kontradiksjon

Kontrapositiv bevisføring og bevis ved selvmotsigelse, inkludert sqrt(2) og primtall.

50 min

10 oppgaver

KontrapositivKontradiksjonIrrasjonale tallPrimtall

Du leser den tradisjonelle versjonen

Din fremgang i kapitlet

0 / 10 oppgaver

Kapitlets plass i kurset

Bygger på

9.1Direkte bevis og moteksempler

Kontrapositiv og kontradiksjon

I kapittel 9.1 lærte du direkte bevis, og i 9.2 bevis ved induksjon. Noen ganger er det vanskelig eller umulig å bevise en påstand direkte. Da kan vi bruke to kraftige indirekte bevismetoder:

- Kontrapositiv: I stedet for å bevise «dersom $P$ , så $Q$ », beviser vi den logisk ekvivalente påstanden «dersom ikke $Q$ , så ikke $P$ ».
- Kontradiksjon (selvmotsigelse): Vi antar at påstanden er usann, og utleder en selvmotsigelse. Da må påstanden være sann.

Disse metodene er spesielt nyttige for å bevise eksistensresultater og egenskaper ved irrasjonale tall.

Kontrapositiv

P \Rightarrow Q

✏️Eksempel 1: Kontrapositiv bevisfoering

Bevis: Dersom $n^2$ er odde, så er $n$ odde (der $n$ er et heltall).

Bevis (kontrapositiv):

Vi beviser kontrapositivet: «Dersom $n$ er partall, så er $n^2$ partall.»

La $n$ være partall. Da finnes det et heltall $k$ slik at $n = 2k$ .

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

Siden $2k^2$ er et heltall, er $n^2$ partall. $\square$

Vi har vist at $\neg Q \Rightarrow \neg P$ , som er ekvivalent med $P \Rightarrow Q$ .

📝Oppgave 1

Kontrapositiv bevisfoering.

Skriv kontrapositivet til: «Dersom $n$ er delelig med 6, så er $n$ delelig med 3.»

Bevis ved kontrapositiv: Dersom $n^2$ er delelig med 3, så er $n$ delelig med 3.

Bevis ved kontradiksjon (selvmotsigelse)

P

✏️Eksempel 2: sqrt(2) er irrasjonell

Bevis at $\sqrt{2}$ er et irrasjonelt tall.

Bevis (ved kontradiksjon):

Anta at $\sqrt{2}$ er rasjonell. Da kan vi skrive $\displaystyle \sqrt{2} = \frac{a}{b}$ der $a$ og $b$ er heltall med $b \neq 0$ og brøken er maksimalt forkortet (dvs. $\gcd(a, b) = 1$ ).

Kvadrer begge sider:
$2 = \frac{a^2}{b^2} \quad \Rightarrow \quad a^2 = 2b^2$

Altså er $a^2$ partall. Fra Eksempel 1 (kontrapositiv) vet vi at dette betyr at $a$ er partall. Skriv $a = 2k$ :

$4k^2 = 2b^2 \quad \Rightarrow \quad b^2 = 2k^2$

Altså er $b^2$ partall, som betyr at $b$ også er partall.

Men hvis både $a$ og $b$ er partall, er brøken $\displaystyle \frac{a}{b}$ ikke maksimalt forkortet. Dette motsier antagelsen.

Altså er $\sqrt{2}$ irrasjonell. $\square$

📝Oppgave 2

Irrasjonale tall.

Bevis at $\sqrt{3}$ er irrasjonell. (Hint: Du trenger først å vise at $n^2$ delelig med 3 medforer at $n$ er delelig med 3.)

Bevis at $\sqrt{2} + \sqrt{3}$ er irrasjonell. (Hint: Anta at summen er rasjonell og vis at dette fører til at $\sqrt{2}$ er rasjonell.)

📜Euklids teorem: Det finnes uendelig mange primtall

Teorem (Euklid, ca. 300 f.Kr.): Det finnes uendelig mange primtall.

Bevis (ved kontradiksjon):

Anta at det finnes endelig mange primtall: $p_1, p_2, \ldots, p_n$ .

Konstruer tallet:
$N = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1$

Da er $N > 1$ , så $N$ har minst en primfaktor $p$ . Men $N$ gir rest 1 ved divisjon med hvert av primtallene $p_1, p_2, \ldots, p_n$ . Altså er $p$ et primtall som ikke er blant $p_1, \ldots, p_n$ .

Dette motsier antagelsen om at listen inneholder alle primtall.

Altså finnes det uendelig mange primtall. $\square$

📝Oppgave 3

Primtall og Euklids bevis.

I Euklids bevis: Hvis vi starter med primtallene $p_1 = 2, p_2 = 3, p_3 = 5$ , hva er $N$ ? Er $N$ selv et primtall?

Gjenta med $p_1 = 2, p_2 = 3, p_3 = 5, p_4 = 7$ . Er $N$ et primtall?

Gjenta med $p_1 = 2, p_2 = 3, p_3 = 5, p_4 = 7, p_5 = 11, p_6 = 13$ . Er $N$ et primtall? Hvis ikke, faktoriser.

Løs oppgaven Tren

Oppsummering

I dette kapittelet har du lært to indirekte bevismetoder:

- Kontrapositiv: For å bevise $P \Rightarrow Q$ , bevis $\neg Q \Rightarrow \neg P$ i stedet.
- Kontradiksjon: Anta at påstanden er usann, og utled en selvmotsigelse.

Når bruker du hvilken metode?

Metode	Når
Direkte bevis	Naturlig vei fra antagelse til konklusjon
Kontrapositiv	Enklere å starte fra negasjonen av konklusjonen
Kontradiksjon	Påstanden handler om «umulighet» eller «ikke-eksistens»
Induksjon	Påstand om alle naturlige tall

Beviset for at

\sqrt{2}

er irrasjonell og Euklids bevis er to av de mest kjente eksemplene i matematikkens historie.

📝Oppgave 4

Avanserte bevis.

Bevis ved kontradiksjon at det ikke finnes noe største partall.

Bevis ved kontrapositiv: For heltall $a$ og $b$ , dersom $ab$ er odde, så er både $a$ og $b$ odde.

Bevis at $\log_2 3$ er irrasjonell.

📝Oppgave 5

Hvilken bevismetode er mest hensiktsmessig for å vise at $\sqrt{5}$ er irrasjonell?

Repetisjonsoppgaver

Din fremgang

0deloppgaver0 / 5 oppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.