Kapittel 5: Bevis, formodninger og moteksempler

Bevis

Et bevis (proof) for en påstand fra en mengde gitte antakelser er en rekke logiske slutninger som viser hvordan vi kommer fra antakelsene til påstanden.
For hvert steg må konklusjonen være en logisk konsekvens av antakelsene.
Hvis vi har en bevis, så har vi en garanti at noe er sann.
Hva som kan bevises, avhenger direkte fra hva vi antar.

En formodning (conjecture) er en påstand som vi tror, eller har god grunn til å tro, er sann, men som vi ikke har bevist eller motbevist.
Eksempler er Goldbachs formodning (ethvert partall større enn to kan uttrykkes som summen av to primtall)...
... og Collatz' formodning (vi definerer en talesekvens; hvis det siste tallet er et partall, så neste tall er en halvpart av det; hvis det siste tallet er et oddetall, så ganger vi det med tre og plusser med en og legger det til som et neste tall; vi ender alltid med 1).

Et direkte bevis (direct proof) for en påstand på formen "hvis $F$, så $G$" er et logisk gyldig resonnement som begynner med antakelsen om at $F$ er sann, og som ender med konklusjonen om at $G$ er sann.
- Bare brukes med implikasjoner (hvis $\rightarrow$ så-setninger)
- Eksempel
- Vi bruker ikke "$\lnot$" eller "usann" i eksempler, fordi det er kun ett tilfellet hvor en påstand på formen $(F \rightarrow G)$ blir usann, og det er når $F$ er sann, og $G$ er usann. Vi må anta at $F$ er sann - ellers gjør beviset ingen mening.

En eksistenspåstand (existential statement) er en påstand som sier at noe eksisterer.
Vi beviser eksistenspåstander ved å helt enkelt finne objektet som gjør påstanden sann. Slike bevis kalles eksistensbevis (existential proof).

Bevis ved tilfeller (proof by cases), eller bevis ved uttømmelse (proof by exhaustion). Her deles et bevis i mindre deler, som til sammen dekker det vi skal bevise, og hver enkelt del blir bevist hver for seg.
Typisk brukes når vi har noe disjunktivt ($\lor$-formler) eller konjunktivt ($\land$-formler).