Regel: Uttømming

Forutsetninger og læringsmål

Du skal kunne

• forstå bevis med uttømming

• lage bevis med uttømming

• undervise

Introduksjon

Man skal bevise en påstand for en mengde tilfeller. Man deler mengden tilfeller i grupper; så beviser man påstanden for én og én gruppe. Til sist beviser man at alle tilfeller faller innenfor en gruppe.

Referanser

Wikipedia: Proof by exhaustion https://www.nkhansen.com/tag/uttommende-bevis/

Eksempler

Table 11 Sannhetsverditabell

n	m	mn	Påstand
Odde	Odde	Odde	Stemmer
Odde	Par	Par	Stemmer
Par	Odde	Par	Stemmer
Par	Par	Par	Stemmer

Hvis to heltall n og m er slik at produktet mellom dem er odde, må både n og m være odde.

Vi kan dele tilfellene i fire grupper:

• Både n og m er odde: Vi kan si at nm kan skrives som $(2p+1)(2q+1)$, hvor $p$ og $q$ er hele tall. Dette er lik $4pq+2p+2q+1$, som er odde (dette kan selvfølgelig grunngis mer i detalj). Påstanden stemmer.

• Bare n er odde, m er partall: Vi kan si at nm kan skrives som $(2p+1)2q$, som er lik $4pq+2q$. Dette er partall. Påstanden stemmer.

• n er partall, m er odde: Vi kan si at nm kan skrives som $2p(2q+1)$, som er lik $4pq+2p$. Dette er partall; påstanden stemmer.

• Både n og m er partall: Produktet nm kan skrives $2p·2q$, som er lik $4pq$; dette er partall. Påstanden stemmer.

De fire gruppene dekker alle muligheter, siden både p og q må være enten partall eller oddetall.

Vi har vist at påstanden stemmer for alle gruppene; vi konkluderer dermed med at påstanden stemmer for alle tilfeller.

Representasjoner

Navn

Ord

“grupper”

Formelspråket

Venn-diagram

Sannhetsverditabell

Hver linje i en sannhetstabell er en gruppe.

Task

En «perfekt terning» kan skrives på formen n³, n ∈ ℕ. Bevis at en perfekt terning er delelig på 9, en over delelig på 9 eller en under delelig på 9.

Løsningsforslag

Naturlige tall kan deles i tre grupper:

• Tall som er delelig på 3: $3|n$ (tegnet | leses “er faktor i). For disse tallene kan vi altså skrive $n=3m$. En perfekt terning er altså $n³=27m³$, som er delelig på 3. For disse tallene er altså en perfekt terning delelig på 3.

• Tall som er en mindre enn et tall som kan deles på tre: $3|n+1$. For disse tallene kan vi altså skrive $n+1=3m$, altså $n=3m-1$. En perfekt terning er $n³=(3m-1)³$ $=27m³-27m²+9m-1=3(9m³-9m²+3m)-1$, som er en under noe som er delelig på 3. For disse tallene er altså en perfekt terning en under et tall som er delelig på 3.

• Tall som er en større enn et tall som kan deles på tre: $3|n-1$. Tilsvarende.

Alle naturlige tall er i en av gruppene. Det kan vi se for eksempel på tall-linja: Første gruppe er hver tredje naturlige tall, andre gruppe tallene under og tredje gruppe tallene over. Flere tall finens ikke; har vi et tall som er to over et tall delelig på tre er dette også en under neste tall delelig på tre.

Vi ser at alle tall faller i en av gruppene. Vi har bevist påstanden for alle gruppene. Derfor kan vi konkludere med at påstanden gjelder for alle gruppene.

Algoritmer

Lage regel fra egnet metafor

Lage regler fra inni-regler

Aspekt

• Algoritmer

• Regler

Datatyper

Læring

Men…