Regel: Uttømming#

Forutsetninger og læringsmål#

Dette er en av de viktige reglene i bevis.

Du skal kunne

  • forstå bevis med uttømming

  • lage bevis med uttømming

  • undervise

Introduksjon#

Om man skal bevise en påstand for mange (f.eks. alle) tilfeller (f.eks. alle naturlige tall) kan man

  • dele tilfellene opp i flere grupper (f.eks. partall og oddetall)

  • bevise påstanden for én og én gruppe (f.eks. for partall for seg og oddetall for seg)

  • bevise at alle tilfellene faller inn under en av gruppene Da har man bevist at påstanden gjelder for alle gruppene.

Referanser#

Eksempler#

n·m er oddetall → n er oddetall ∧ m er oddetall#

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.

Perfekt terning#

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.

Representasjoner#

Venn-diagram#

Man kan se for seg de forskjellige tilfellene som punkter og gruppene som områder, omtrent som Venn-diagram over grupper.

Sannhetsverditabell#

Hver linje i en sannhetstabell er en gruppe. Se tabell litt lengre oppe.