6.6 Bevis og matematisk argumentasjon | Matematikk R2

Analysere og utvikle matematiske bevis.

60 min

14 oppgaver

BevisArgumentasjonLogikkMatematisk resonnement

Din fremgang i kapitlet

0 / 14 oppgaver

Hva er et matematisk bevis?

Et matematisk bevis er en logisk argumentasjonsrekke som viser at en pastand (et teorem eller en setning) er sann. I motsetning til naturvitenskapelige fag, hvor vi tester hypoteser gjennom eksperimenter, bruker matematikken logiske slutninger til a utlede sannheter fra aksepterte premisser.

Et godt bevis kjennetegnes ved:
- Presisjon: Hver pastand er klart formulert
- Logisk sammenheng: Hvert steg følger logisk fra det forrige
- Fullstendighet: Ingen steg mangler i argumentasjonen
- Gyldige slutninger: Kun aksepterte logiske regler brukes

I dette kapitlet skal vi lare om de tre viktigste bevismetodene: direkte bevis, motsigelsesbevis og induksjonsbevis.

Teorem og bevis

Et teorem (eller en setning) er en matematisk pastand som kan bevises a vare sann. Et bevis er en logisk argumentasjon som viser at et teorem er sant, basert pa: - Aksiomer : Grunnleggende sannheter vi aksepterer uten bevis - Definisjoner : Presise beskrivelser av matematiske begreper - Tidligere beviste teoremer : Resultater vi allerede har vist er sanne

Direkte bevis

Et direkte bevis starter med kjente sannheter (premisser) og bruker logiske slutninger for a na frem til konklusjonen. Dette er den mest intuitive bevisformen.

Struktur for direkte bevis:
1. Anta at premissene er sanne
2. Utfor logiske operasjoner og slutninger
3. Konkluder med det vi onsker a vise

Partall og oddetall

n

✏️Eksempel 1: Summen av to partall

Bevis at summen av to partall er et partall.

Bevis:

La $a$ og $b$ vare to partall.

Steg 1: Siden $a$ er et partall, finnes det et heltall $m$ slik at $a = 2m$ .

Steg 2: Siden $b$ er et partall, finnes det et heltall $n$ slik at $b = 2n$ .

Steg 3: Vi beregner summen:
$a + b = 2m + 2n = 2(m + n)$

Steg 4: Siden $m + n$ er et heltall (summen av to heltall er et heltall), og $a + b = 2(m + n)$ , er $a + b$ et partall per definisjon.

$\blacksquare$

✏️Eksempel 2: Produktet av to oddetall

Bevis at produktet av to oddetall er et oddetall.

Bevis:

La $a$ og $b$ vare to oddetall.

Steg 1: Siden $a$ er et oddetall, finnes det et heltall $m$ slik at $a = 2m + 1$ .

Steg 2: Siden $b$ er et oddetall, finnes det et heltall $n$ slik at $b = 2n + 1$ .

Steg 3: Vi beregner produktet:
$a \cdot b = (2m + 1)(2n + 1)$

Steg 4: Vi utvider:
$a \cdot b = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1$

Steg 5: La $k = 2mn + m + n$ . Da er $k$ et heltall, og vi har:
$a \cdot b = 2k + 1$

Dette er formen til et oddetall, sa $a \cdot b$ er et oddetall.

$\blacksquare$

✏️Eksempel 3: Kvadratet av et partall

Bevis at kvadratet av et partall er delelig med 4.

Bevis:

La $n$ vare et partall.

Steg 1: Siden $n$ er et partall, finnes det et heltall $k$ slik at $n = 2k$ .

Steg 2: Vi beregner $n^2$ :
$n^2 = (2k)^2 = 4k^2$

Steg 3: Siden $k^2$ er et heltall, og $n^2 = 4k^2 = 4 \cdot k^2$ , er $n^2$ delelig med 4.

$\blacksquare$

📝Oppgave 1

Bruk direkte bevis til a vise folgende pastander:

Summen av to oddetall er et partall.

Summen av et partall og et oddetall er et oddetall.

Produktet av et partall og et heltall er alltid et partall.

✏️Eksempel 4: Summen av tre pafolgende heltall

Bevis at summen av tre pafolgende heltall alltid er delelig med 3.

Bevis:

La de tre pafolgende heltallene vare $n$ , $n+1$ og $n+2$ .

Steg 1: Vi beregner summen:
$n + (n+1) + (n+2) = 3n + 3 = 3(n + 1)$

Steg 2: Siden $n + 1$ er et heltall, og summen kan skrives som $3 \cdot (n+1)$ , er summen delelig med 3.

$\blacksquare$

Motsigelsesbevis (bevis ved selvmotsigelse)

Et motsigelsesbevis (lat. reductio ad absurdum) fungerer ved at vi antar det motsatte av det vi onsker a bevise, og viser at denne antagelsen forer til en logisk selvmotsigelse.

Struktur for motsigelsesbevis:
1. Anta det motsatte av det vi onsker a bevise
2. Utled logiske konsekvenser fra denne antagelsen
3. Vis at konsekvensene forer til en selvmotsigelse
4. Konkluder at antagelsen var feil, og det motsatte (det vi ville bevise) ma vare sant

Denne metoden er spesielt nyttig nar det er vanskelig a bevise noe direkte.

✏️Eksempel 5: $\sqrt{2}$ er irrasjonal (klassisk bevis)

Bevis at $\sqrt{2}$ er et irrasjonalt tall, dvs. at det ikke kan skrives som en brok $\displaystyle \frac{p}{q}$ der $p$ og $q$ er heltall.

Bevis ved motsigelse:

Steg 1 (Antagelse): Anta at $\sqrt{2}$ er rasjonalt. Da kan vi skrive:
$\sqrt{2} = \frac{p}{q}$
der $p$ og $q$ er heltall uten felles faktorer (broken er maksimalt forkortet) og $q \neq 0$ .

Steg 2: Vi kvadrerer begge sider:
$2 = \frac{p^2}{q^2}$

Steg 3: Vi ganger med $q^2$ :
$2q^2 = p^2$

Steg 4: Siden $p^2 = 2q^2$ , er $p^2$ et partall. Men da ma ogsa $p$ vare et partall (for hvis $p$ var oddetall, ville $p^2$ ogsa vart oddetall).

Steg 5: Siden $p$ er et partall, kan vi skrive $p = 2k$ for et heltall $k$ . Vi setter inn:
$2q^2 = (2k)^2 = 4k^2$

Steg 6: Vi deler på 2:
$q^2 = 2k^2$

Steg 7: Siden $q^2 = 2k^2$ , er $q^2$ et partall, og derfor er ogsa $q$ et partall.

Steg 8 (Motsigelse): Bade $p$ og $q$ er partall, noe som betyr at de har felles faktor 2. Men vi antok at broken var maksimalt forkortet! Dette er en selvmotsigelse.

Konklusjon: Antagelsen om at $\sqrt{2}$ er rasjonalt ma vare feil. Derfor er $\sqrt{2}$ irrasjonalt.

$\blacksquare$

✏️Eksempel 6: Det finnes uendelig mange primtall (Euklids bevis)

Bevis at det finnes uendelig mange primtall.

Bevis ved motsigelse (Euklid, ca. 300 f.Kr.):

Steg 1 (Antagelse): Anta at det bare finnes endelig mange primtall. La disse vare $p_1, p_2, p_3, \ldots, p_n$ .

Steg 2: Betrakt tallet:
$N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1$

Dette er produktet av alle primtall pluss 1.

Steg 3: Vi undersoker om $N$ er delelig med noen av primtallene $p_1, p_2, \ldots, p_n$ :
- Nar vi deler $N$ på $p_1$ , far vi rest 1 (siden $N = p_1 \cdot (\text{noe}) + 1$ )
- Nar vi deler $N$ på $p_2$ , far vi rest 1
- Generelt: Nar vi deler $N$ på $p_i$ , far vi alltid rest 1

Altsa er $N$ ikke delelig med noen av primtallene $p_1, \ldots, p_n$ .

Steg 4: Men alle tall storre enn 1 har minst en primfaktor. Siden $N > 1$ og $N$ ikke er delelig med noen av $p_1, \ldots, p_n$ , ma $N$ enten:
- Vare et primtall selv (som ikke er i listen), eller
- Ha en primfaktor som ikke er i listen

Steg 5 (Motsigelse): Uansett har vi funnet et primtall som ikke er i listen var over alle primtall. Dette motsier antagelsen.

Konklusjon: Det finnes uendelig mange primtall.

$\blacksquare$

📝Oppgave 2

Bruk motsigelsesbevis:

Vis at $\sqrt{3}$ er irrasjonalt.

Vis at det ikke finnes noe største partall.

Vis at summen av et rasjonalt tall og et irrasjonalt tall er irrasjonalt.

✏️Eksempel 7: Det finnes ikke noe minste positivt rasjonalt tall

Bevis at det ikke finnes noe minste positivt rasjonalt tall.

Bevis ved motsigelse:

Steg 1 (Antagelse): Anta at det finnes et minste positivt rasjonalt tall $r$ .

Steg 2: Betrakt tallet $\displaystyle \frac{r}{2}$ .

Steg 3: Vi observerer at:
- $\displaystyle \frac{r}{2}$ er rasjonalt (kvotienten av to rasjonale tall er rasjonalt)
- $\displaystyle \frac{r}{2} > 0$ (halvparten av et positivt tall er positivt)
- $\displaystyle \frac{r}{2} < r$

Steg 4 (Motsigelse): Vi har funnet et positivt rasjonalt tall $\displaystyle \frac{r}{2}$ som er mindre enn $r$ . Men $r$ var antatt a vare det minste. Dette er en selvmotsigelse.

Konklusjon: Det finnes ikke noe minste positivt rasjonalt tall.

$\blacksquare$

Induksjonsbevis (matematisk induksjon)

Matematisk induksjon er en bevismetode som brukes til a bevise pastander som gjelder for alle naturlige tall (eller alle heltall fra et visst punkt).

Tenk på induksjon som en uendelig rekke med dominobrikker:
- Hvis vi vet at den forste brikken faller (basissteget)
- Og vi vet at nar en brikke faller, sa faller den neste (induksjonssteget)
- Da vil alle brikkene falle

📜Prinsippet om matematisk induksjon

La $P(n)$ vare en pastand som avhenger av et naturlig tall $n$ . For a bevise at $P(n)$ er sann for alle $n \geq n_0$ , viser vi:

1. Basissteg: $P(n_0)$ er sann.

2. Induksjonssteg: For alle $k \geq n_0$ : Hvis $P(k)$ er sann, så er $P(k+1)$ sann.

Da er $P(n)$ sann for alle $n \geq n_0$ .

I induksjonssteget kaller vi antagelsen " $P(k)$ er sann" for induksjonsantagelsen eller induksjonshypotesen. Det er viktig a vare tydelig på hva denne antagelsen er, og hvordan den brukes til a bevise $P(k+1)$ .

✏️Eksempel 8: Summen av de $n$ forste naturlige tallene

Bevis ved induksjon at for alle naturlige tall

n \geq 1

1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}

Bevis ved induksjon:

La $P(n)$ vare pastanden: $\displaystyle 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$

Basissteg ( $n = 1$ ):

Venstre side: $1$

Hoyre side: $\displaystyle \frac{1 \cdot 2}{2} = 1$

Siden venstre side = hoyre side, er $P(1)$ sann.

Induksjonssteg:

Induksjonsantagelse: Anta at $P(k)$ er sann for en vilkarlig $k \geq 1$ , dvs.:
$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$

A vise: $P(k+1)$ er sann, dvs.:
$1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}$

Bevis:
$1 + 2 + 3 + \cdots + k + (k+1) = \underbrace{\frac{k(k+1)}{2}}_{\text{induksjonsantagelsen}} + (k+1)$

$= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{k(k+1) + 2(k+1)}{2}$

$= \frac{(k+1)(k + 2)}{2}$

Dette er nettopp $P(k+1)$ .

Konklusjon: Ved induksjonsprinsippet er $P(n)$ sann for alle $n \geq 1$ .

$\blacksquare$

✏️Eksempel 9: Summen av de $n$ forste oddetallene

Bevis ved induksjon at for alle

n \geq 1

1 + 3 + 5 + \cdots + (2n-1) = n^2

Bevis ved induksjon:

La $P(n)$ vare pastanden: $1 + 3 + 5 + \cdots + (2n-1) = n^2$

Basissteg ( $n = 1$ ):

Venstre side: $1$

Hoyre side: $1^2 = 1$

$P(1)$ er sann.

Induksjonssteg:

Induksjonsantagelse: Anta $P(k)$ : $1 + 3 + 5 + \cdots + (2k-1) = k^2$

A vise: $P(k+1)$ : $1 + 3 + 5 + \cdots + (2k-1) + (2(k+1)-1) = (k+1)^2$

Bevis:
$1 + 3 + 5 + \cdots + (2k-1) + (2k+1) = k^2 + (2k+1)$

$= k^2 + 2k + 1 = (k+1)^2$

Konklusjon: Ved induksjonsprinsippet er $P(n)$ sann for alle $n \geq 1$ .

$\blacksquare$

✏️Eksempel 10: Delelighetsbevis

Bevis ved induksjon at $n^3 - n$ er delelig med 6 for alle naturlige tall $n \geq 1$ .

Bevis ved induksjon:

La $P(n)$ vare pastanden: $6 \mid (n^3 - n)$ (6 deler $n^3 - n$ )

Basissteg ( $n = 1$ ):

$1^3 - 1 = 0 = 6 \cdot 0$

Siden 0 er delelig med 6, er $P(1)$ sann.

Induksjonssteg:

Induksjonsantagelse: Anta at $P(k)$ er sann, dvs. $k^3 - k = 6m$ for et heltall $m$ .

A vise: $P(k+1)$ : $(k+1)^3 - (k+1)$ er delelig med 6.

Bevis:
$(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1$
$= k^3 + 3k^2 + 2k$
$= (k^3 - k) + 3k^2 + 3k$
$= (k^3 - k) + 3k(k + 1)$

Na bruker vi at:
- $(k^3 - k) = 6m$ (induksjonsantagelsen)
- $k(k+1)$ er produktet av to pafolgende tall, sa ett av dem er partall. Dermed er $k(k+1)$ delelig med 2, og $3k(k+1)$ er delelig med 6.

Altsa er $(k+1)^3 - (k+1) = 6m + 6 \cdot (\text{heltall})$ , som er delelig med 6.

$\blacksquare$

📝Oppgave 3

Bevis ved induksjon:

1 + 2 + 4 + 8 + \cdots + 2^{n-1} = 2^n - 1

for alle

n \geq 1

\displaystyle 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}

for alle

n \geq 1

n^2 + n

er alltid et partall for alle

n \geq 1

✏️Eksempel 11: Formelen for geometrisk rekke

Bevis ved induksjon at for

r \neq 1

1 + r + r^2 + \cdots + r^n = \frac{r^{n+1} - 1}{r - 1}

Bevis ved induksjon:

La $P(n)$ vare formelen ovenfor.

Basissteg ( $n = 0$ ):

VS: $r^0 = 1$

HS: $\displaystyle \frac{r^1 - 1}{r - 1} = \frac{r - 1}{r - 1} = 1$

$P(0)$ er sann.

Induksjonssteg:

Induksjonsantagelse: $\displaystyle 1 + r + r^2 + \cdots + r^k = \frac{r^{k+1} - 1}{r - 1}$

A vise: $\displaystyle 1 + r + r^2 + \cdots + r^k + r^{k+1} = \frac{r^{k+2} - 1}{r - 1}$

Bevis:
$1 + r + \cdots + r^k + r^{k+1} = \frac{r^{k+1} - 1}{r - 1} + r^{k+1}$

$= \frac{r^{k+1} - 1 + r^{k+1}(r - 1)}{r - 1} = \frac{r^{k+1} - 1 + r^{k+2} - r^{k+1}}{r - 1}$

$= \frac{r^{k+2} - 1}{r - 1}$

$\blacksquare$

Analysere og forsta bevis

A lese og forsta matematiske bevis er en viktig ferdighet. Her er noen strategier:

1. Identifiser strukturen:
- Hva er premissene (det vi starter med)?
- Hva er konklusjonen (det vi vil bevise)?
- Hvilken bevismetode brukes?

2. Folg hvert steg:
- Er hvert steg logisk gyldig?
- Hvilke regler eller tidligere resultater brukes?
- Kan du forklare hvert steg med egne ord?

3. Se etter nodvendig bruk av premissene:
- Hvor brukes hver premiss?
- Kunne beviset fungert uten noen av premissene?

4. Vurder generalitet:
- Er beviset gyldig i alle tilfeller?
- Finnes det spesialtilfeller som ma behandles separat?

✏️Eksempel 12: Analysere et bevis

Analyser folgende bevis og identifiser eventuelle feil:

"Pastand: Alle hester har samme farge.

Bevis ved induksjon:

Basissteg: For $n = 1$ hest er pastanden triviell: En hest har samme farge som seg selv.

Induksjonssteg: Anta at enhver mengde med $k$ hester har samme farge. Betrakt en mengde med $k + 1$ hester: $H_1, H_2, \ldots, H_{k+1}$ .

Mengden $\{H_1, H_2, \ldots, H_k\}$ har $k$ hester, sa alle har samme farge (induksjonsantagelsen).

Mengden $\{H_2, H_3, \ldots, H_{k+1}\}$ har ogsa $k$ hester, sa alle har samme farge.

Siden $H_2$ er i begge mengder, har alle $k + 1$ hestene samme farge.

Konklusjon: Alle hester har samme farge. $\blacksquare$ "

Analyse av beviset:

Dette beviset inneholder en subtil feil i induksjonssteget.

Feilen: Induksjonssteget fungerer bare nar de to mengdene $\{H_1, \ldots, H_k\}$ og $\{H_2, \ldots, H_{k+1}\}$ har en felles hest.

Problemet oppstar ved $k = 1$ :
- Mengde 1: $\{H_1\}$ (1 hest)
- Mengde 2: $\{H_2\}$ (1 hest)
- Disse mengdene har ingen felles hester!

Dermed kan vi ikke konkludere at $H_1$ og $H_2$ har samme farge.

Lardommen: I induksjonsbevis ma vi vare forsiktige med a sjekke at argumentet faktisk fungerer for alle verdier av $k$ , spesielt for de forste verdiene. Her svikter argumentet ved overgangen fra $n = 1$ til $n = 2$ .

📝Oppgave 4

Analyser folgene bevis og identifiser feil:

"Pastand: $1 = 2$

Bevis: La $a = b$ . Da er $a^2 = ab$ . Altsa $a^2 - b^2 = ab - b^2$ , dvs. $(a-b)(a+b) = b(a-b)$ . Vi deler på $(a-b)$ og far $a + b = b$ . Siden $a = b$ , har vi $2b = b$ , altsa $2 = 1$ ."

Hva er feilen?

"Pastand: Alle positive heltall er like.

Bevis: La $P(n)$ vare: Alle tall i mengden $\{1, 2, \ldots, n\}$ er like.
$P(1)$ er sann (kun ett tall).
Anta $P(k)$ : $1 = 2 = \cdots = k$ . Da er spesielt $k = 1$ , sa $k + 1 = 2 = 1$ . Altsa $P(k+1)$ er sann."

Hva er feilen?

Utvikle egne bevis

A skrive egne bevis er en ferdighet som utvikles med ovelse. Her er en steg-for-steg-tilnarming:

1. Forsta problemet:
- Hva er det eksakt vi skal bevise?
- Hva vet vi (premissene)?
- Skriv opp relevante definisjoner.

2. Velg bevismetode:
- Direkte bevis: Naturlig nar vi kan arbeide fremover fra premissene.
- Motsigelsesbevis: Nyttig nar pastanden er negativ ("det finnes ikke...") eller nar direkte bevis virker vanskelig.
- Induksjon: Nar pastanden gjelder for alle naturlige tall.

3. Skriv beviset:
- Vær presis og tydelig
- Begrunn hvert steg
- Marker tydelig start og slutt på beviset

4. Sjekk beviset:
- Er hvert steg logisk gyldig?
- Har du brukt alle nodvendige premisser?
- Fungerer beviset i alle tilfeller?

✏️Eksempel 13: Utvikle et bevis

Bevis at for alle reelle tall $a$ og $b$ : Hvis $a + b$ er rasjonalt og $a$ er rasjonalt, så er $b$ rasjonalt.

Steg 1: Forsta problemet
- Premisser:

a + b \in \mathbb{Q}

a \in \mathbb{Q}

- Konklusjon:

b \in \mathbb{Q}

- Definisjon: Et tall

r

er rasjonalt hvis

\displaystyle r = \frac{p}{q}

der

p, q \in \mathbb{Z}

q \neq 0

Steg 2: Velg bevismetode
Dette virker som et naturlig direkte bevis: Vi kan bruke at rasjonale tall er lukket under subtraksjon.

Steg 3: Skriv beviset

Bevis:

La $a$ og $a + b$ vare rasjonale tall.

Siden $a$ er rasjonalt, finnes heltall $p_1, q_1$ med $q_1 \neq 0$ slik at $\displaystyle a = \frac{p_1}{q_1}$ .

Siden $a + b$ er rasjonalt, finnes heltall $p_2, q_2$ med $q_2 \neq 0$ slik at $\displaystyle a + b = \frac{p_2}{q_2}$ .

Da er:
$b = (a + b) - a = \frac{p_2}{q_2} - \frac{p_1}{q_1} = \frac{p_2 q_1 - p_1 q_2}{q_1 q_2}$

Siden $p_2 q_1 - p_1 q_2$ og $q_1 q_2$ er heltall, og $q_1 q_2 \neq 0$ , er $b$ rasjonalt.

$\blacksquare$

Steg 4: Sjekk beviset
- Vi brukte begge premissene
- Hvert steg er begrunnet
- Det er ingen spesialtilfeller vi har oversett

✏️Eksempel 14: Bevis ved kontraposisjon

Bevis: Hvis $n^2$ er et partall, så er $n$ et partall.

Bevismetode: Vi bruker kontraposisjon. A bevise "Hvis

P

, sa

Q

" er logisk ekvivalent med a bevise "Hvis ikke

Q

, sa ikke

P

Kontraposisjon: Hvis $n$ er et oddetall, så er $n^2$ et oddetall.

Bevis:

Anta at $n$ er et oddetall. Da finnes et heltall $k$ slik at $n = 2k + 1$ .

Vi beregner $n^2$ :
$n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$

La $m = 2k^2 + 2k$ . Da er $m$ et heltall, og $n^2 = 2m + 1$ , som er formen til et oddetall.

Altsa er $n^2$ et oddetall.

Konklusjon: Ved kontraposisjon har vi vist at hvis $n^2$ er et partall, så er $n$ et partall.

$\blacksquare$

📝Oppgave 5

Utvikle fullstendige bevis for folgende pastander. Velg passende bevismetode.

Hvis $n^2$ er delelig med 3, så er $n$ delelig med 3.

\sqrt{5}

er irrasjonalt.

For alle $n \geq 1$ : $1 \cdot 1! + 2 \cdot 2! + \cdots + n \cdot n! = (n+1)! - 1$

Logisk argumentasjon

Matematiske bevis bygger på formell logikk. Her er de viktigste logiske begrepene:

Logiske konnektiver:
- Konjunksjon ( $P \land Q$ ): " $P$ og $Q$ " - sann bare nar bade $P$ og $Q$ er sanne
- Disjunksjon ( $P \lor Q$ ): " $P$ eller $Q$ " - sann nar minst en av dem er sann
- Negasjon ( $\neg P$ ): "ikke $P$ " - sann nar $P$ er usann
- Implikasjon ( $P \Rightarrow Q$ ): "hvis $P$ , sa $Q$ " - usann bare nar $P$ er sann og $Q$ er usann
- Ekvivalens ( $P \Leftrightarrow Q$ ): " $P$ hvis og bare hvis $Q$ " - sann nar bade har samme sannhetsverdi

📜Viktige logiske ekvivalenser

1. Kontraposisjon:

(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P)

2. De Morgans lover:
$\neg(P \land Q) \Leftrightarrow (\neg P \lor \neg Q)$
$\neg(P \lor Q) \Leftrightarrow (\neg P \land \neg Q)$

3. Negasjon av implikasjon:
$\neg(P \Rightarrow Q) \Leftrightarrow (P \land \neg Q)$

✏️Eksempel 15: Bruk av logiske ekvivalenser

Skriv negasjonen av folgende pastander:

a) "Alle primtall storre enn 2 er oddetall."

b) "Det finnes et reelt tall $x$ slik at $x^2 < 0$ ."

c) "Hvis det regner, så er bakken vat."

Løsning:

a) Original: $\forall p > 2$ primtall: $p$ er oddetall.

Negasjon: Det finnes et primtall $p > 2$ som er partall.

(Merk: Negasjonen er usann, noe som bekrefter at originalen er sann.)

b) Original: $\exists x \in \mathbb{R}: x^2 < 0$

Negasjon: For alle reelle tall $x$ er $x^2 \geq 0$ .

(Negasjonen er sann, sa originalen er usann.)

c) Original: Regn $\Rightarrow$ Vat bakke

Negasjon: Det regner OG bakken er ikke vat.

(Bruker $\neg(P \Rightarrow Q) \Leftrightarrow (P \land \neg Q)$ )

✏️Eksempel 16: Bevis med kvantorer

Bevis at det finnes uendelig mange primtall på formen $4k + 3$ .

Bevis ved motsigelse:

Antagelse: Anta at det bare finnes endelig mange primtall på formen $4k + 3$ . La disse vare $p_1, p_2, \ldots, p_n$ .

Konstruksjon: Betrakt tallet:
$N = 4 \cdot p_1 \cdot p_2 \cdots p_n - 1 = 4(p_1 p_2 \cdots p_n) - 1$

Observasjon 1: $N$ er på formen $4m - 1 = 4(m-1) + 3$ , altsa på formen $4k + 3$ .

Observasjon 2: Ethvert oddetall er enten på formen $4k + 1$ eller $4k + 3$ .

Observasjon 3: Produktet av tall på formen $4k + 1$ er igjen på formen $4k + 1$ :
$(4a + 1)(4b + 1) = 16ab + 4a + 4b + 1 = 4(4ab + a + b) + 1$

Konklusjon fra observasjonene: Siden $N$ er på formen $4k + 3$ , ma $N$ ha minst en primfaktor på formen $4k + 3$ .

Motsigelse: Men $N$ er ikke delelig med noen av $p_1, \ldots, p_n$ (siden $N \equiv -1 \pmod{p_i}$ for alle $i$ ). Sa denne primfaktoren er ikke i listen var.

Konklusjon: Det finnes uendelig mange primtall på formen $4k + 3$ .

$\blacksquare$

📝Oppgave 6

Logisk argumentasjon:

Skriv negasjonen av: "For alle $\epsilon > 0$ finnes det en $\delta > 0$ slik at $|f(x) - L| < \epsilon$ nar $|x - a| < \delta$ ."

Bruk kontraposisjon til a bevise: Hvis $n^2$ er oddetall, så er $n$ oddetall.

Bruk De Morgans lover til a forenkle: $\neg((x > 0) \land (x < 10))$

Oppsummering

I dette kapitlet har vi lart om:

Direkte bevis:
- Start med premissene og arbeid logisk mot konklusjonen
- Bruk definisjoner og tidligere resultater

Motsigelsesbevis:
- Anta det motsatte av det du vil bevise
- Vis at dette forer til en selvmotsigelse
- Konkluder at originalen ma vare sann

Induksjonsbevis:
- Vis basissteget (vanligvis $n = 1$ eller $n = 0$ )
- Vis induksjonssteget: $P(k) \Rightarrow P(k+1)$
- Konkluder at pastanden gjelder for alle $n$

Logisk argumentasjon:
- Bruk formelle logiske regler
- Vær bevisst på kvantorer ( $\forall$ , $\exists$ ) og deres negasjoner
- Kontraposisjon er et kraftig verktøy

📝Oppgave 7

Klassifiser hvilken bevismetode som passer best:

"Summen av vinklene i en trekant er $180°$ "

"Det finnes ikke noe største primtall"

" $2^n > n$ for alle $n \geq 1$ "

"Produktet av to irrasjonale tall kan vare rasjonalt"

📝Oppgave 8

Bevis ved induksjon:

2^n > n^2

for alle

n \geq 5

n! > 2^n

for alle

n \geq 4

Fibonaccitallene: $F_1 + F_2 + \cdots + F_n = F_{n+2} - 1$ der $F_1 = F_2 = 1$

📝Oppgave 9

Direkte bevis:

Bevis at hvis $a$ deler $b$ og $b$ deler $c$ , sa deler $a$ $c$ .

Bevis at summen av to rasjonale tall er rasjonalt.

Bevis at diagonalen i et kvadrat med side 1 har lengde $\sqrt{2}$ .

📝Oppgave 10

Motsigelsesbevis:

Bevis at $\log_2 3$ er irrasjonalt.

Bevis at det ikke finnes heltall $a$ og $b$ slik at $6a + 9b = 1$ .

Bevis at $\sqrt{2} + \sqrt{3}$ er irrasjonalt.

📝Oppgave 11

Beviskritikk - finn feilen:

"Bevis: La $a = b = 1$ . Da er $a^2 - b^2 = a - b$ , dvs. $(a-b)(a+b) = a - b$ . Del på $(a-b)$ : $a + b = 1$ , dvs. $2 = 1$ ."

"Bevis ved induksjon at alle tall er like: $P(1)$ er trivielt sann. Anta $P(k)$ : alle tall opptil $k$ er like. For $P(k+1)$ : Vi har $1 = 2 = \ldots = k$ , og $2 = 3 = \ldots = k+1$ . Altsa $1 = k+1$ ."

📝Oppgave 12

Utfordringsoppgaver:

Bevis at $\sqrt{p}$ er irrasjonalt for alle primtall $p$ .

Bevis at det finnes irrasjonale tall $a$ og $b$ slik at $a^b$ er rasjonalt.

Bevis Bernoullis ulikhet ved induksjon: $(1 + x)^n \geq 1 + nx$ for alle $n \geq 1$ og $x > -1$ .

Ekstraoppgaver

Din fremgang

0 / 4 oppgaver