05 Bevis, formodninger og moteksempler

Question 1

bevis

Answer 1

Et bevis (eng: 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.

Question 2

formodning

Answer 2

En formodning (eng: conjecture) er en påstand som vi tror, eller har god grunn til å tro, er sann, men som vi ikke har bevist eller motbevist.

Question 3

direkte bevis

Answer 3

Et direkte bevis (eng: 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.

Question 4

kontrapositivt bevis

Answer 4

Et kontrapositivt bevis (eng: contrapositive proof) for en påstand på formen “hvis F, så G”, er et logisk gyldig resonnement som begynner med antakelsen om at G er usann, som konkluderer med at F er usann.

Den kontrapositive av formelen (F → G) er formelen (¬G → ¬F).

Question 5

motsigelsesbevis

Answer 5

Et motsigelsesbevis (eng: proof by contradiction) for en påstand er et bevis som begynner med antakelsen om at påstanden er usann og som viser hvordan denne antakelsen fører til en motsigelse.