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#
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#
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.
Aspekt#
Algoritmer
Regler