Matematisk bevisföring

{{ 'ml-heading-theory' | message }}

Inom matematiken är logik läran om hur man drar korrekta slutsatser givet vissa premisser. Matematiska bevis är typexempel på hur logik tillämpas — här är varje steg tydligt och välmotiverat, bl.a. genom användning av korrekta definitioner och påståenden. Dessa kan vara axiom, dvs. grundläggande matematiska sanningar, eller bevisade satser. För att föra resonemang på ett kompakt sätt används logiksymboler.

Symbol Innebörd Exempel
\Rightarrow Implikation P1_1: Figuren är en kvadrat
P2_2: Figuren är en fyrhörning
P1_1 \Rightarrow P2_2
\Leftrightarrow Ekvivalens P1_1: Figuren är en kvadrat
P3_3: Figuren har fyra rätvinkliga hörn
och lika långa sidor
P1_1 \Leftrightarrow P3_3
¬\neg Negation P1_1: Figuren är en kvadrat
¬\negP1_1: Figuren är inte en kvadrat
\bot Motsägelse P4_4: Figuren har 44 hörn
P5_5: Figuren är en triangel
(P4_4 och P5_5) \Rightarrow\bot
Uppgift

Masumi och Povilas ska ha ett bevis-battle, och Masumi har bestämt sig för att visa att 11 är lika med 2.2. Povilas blir inte särskilt imponerad och kontrar med att han kan visa att a2a^2 är ett jämnt tal om aa är ett jämnt tal. Här är deras bevis.

BevisSkillLogik.svg

Har de gjort rätt?

Lösning

Vi undersöker ett bevis i taget.

Exempel

Masumis bevis

Masumi påstår sig ha bevisat att 1=2.1=2. Detta verkar inte särskilt troligt, så hon har nog gjort fel någonstans. Vi undersöker ett steg i taget. På första raden anger hon att a=b, a=b, aa och bb är alltså samma tal. På andra och tredje raden multiplicerar hon med aa respektive subtraherar med b2.b^2. Detta går bra eftersom man alltid kan multiplicera och subtrahera båda led med vilket tal som helst utan att göra likheten ogiltig. a2=aba2b2=abb2\begin{aligned} a^2&=ab\\ a^2-b^2&=ab-b^2 \end{aligned} Hon väljer sedan att utveckla vänsterledet med konjugatregeln samt bryta ut bb ur högerledet. Detta går också bra — det är ju bara omskrivningar. (ab)(a+b)=b(ab)\begin{aligned} (a-b)(a+b)=b(a-b)\\ \end{aligned}

Så här långt är alltså det matematiska resonemanget korrekt. Från rad 44 till rad 55 händer dock något ogiltigt: Masumi dividerar båda led med (ab).(a-b). Detta kanske inte verkar konstigt vid första anblick men eftersom aa och bb är samma tal dividerar Masumi med 00 när hon dividerar med (ab).(a-b). Nolldivision är inte tillåtet så detta steg är inte giltigt!

Bevisfel.svg

Stegen som kommer efteråt är rätt men det spelar ingen roll: Om ett steg i beviset är fel är hela beviset fel. Vi kan alltså konstatera att Masumis bevis inte stämmer.

Exempel

Povilas bevis

Povilas verkar ha utgått från att jämna tal är delbara med 22 och brukar skrivas på formen a=2n, a=2n, där nn är ett heltal. Han har dock inte definierat vad nn står för i sitt bevis, vilket han borde ha gjort. Stegen därefter är inga konstigheter: Båda led upphöjs till 22 och högerledet utvecklas med potenslagarna. Han påstår sedan att 2n2 r ett heltal.a¨ 2n^2\text{ är ett heltal.} Detta är sant om nn är ett heltal, eftersom produkten av flera heltal också är ett heltal. Han borde dock ha motiverat detta tydligare eftersom man inte bara kan gissa att det är på det sättet. Han skriver till sist om 2n22n^2 som m,m, vilket är klokt eftersom det då är lätt att se att högerledet är ett jämnt tal: a2=2m. a^2=2m. Povilas bevis är alltså rätt om man antar att n:n\text{:}et i hans bevis är ett heltal. Vid bevisföring är det dock extremt viktigt att man anger vad olika okända faktiskt står för, annars är beviset oanvändbart. Povilas skulle kunna förbättra sitt bevis genom att utveckla det ungefär såhär.

Nyttbevis.svg
Visa lösning Visa lösning
Begrepp

Bevismetoder

Många bevis går ut på att visa att ett påstående, P, leder till ett annat påstående, Q. Man kan t.ex. visa att P: Talen a och b r uddaa¨leder tillQ: Produkten ab r udda,a¨\begin{aligned} &\text{P: Talen }a\text{ och }b\text{ är udda}\\ &\qquad\qquad\text{leder till}\\ &\text{Q: Produkten }a\cdot b\text{ är udda,} \end{aligned} för två heltal aa och b.b. Detta kan skrivas som implikationen P \Rightarrow Q, som säger att om talen aa och bb är udda så är produkten aba \cdot b udda. Det finns många olika bevismetoder och beroende på hur man har valt att formulera sitt problem kan en viss metod vara mer eller mindre lämplig.

Begrepp

Direkt och indirekt bevis

Det mest intuitiva är antagligen att följa implikationen PQP \Rightarrow Q och

utgå från att P är sant och visa att Q följer av det.

Detta kallas för ett direkt bevis. Ibland kan det dock vara enklare att gå åt det motsatta hållet och använda ett så kallat indirekt bevis. Då visar man istället implikationen ¬¬P,\neg\text{Q }\Rightarrow\neg\text{P,} alltså att

utgå från att Q inte är sant och visa att P då inte heller kan vara det.

För exemplet ovan visar man då att om produkten aba \cdot b är jämn måste minst ett av talen aa och bb vara jämnt. Detta är ekvivalent med ett direkt bevis och visar alltså precis samma sak.

Begrepp

Motsägelsebevis

En tredje bevismetod är motsägelsebevis. Man antar då motsatsen till det man vill bevisa och visar att detta leder till en motsägelse. Om man t.ex. vill bevisa påståendet

R: Kvadraten av ett jämnt tal är delbar med 44
skulle man anta motsatsen
¬\negR: Kvadraten av ett jämnt tal är inte delbar med 4.4.

Sedan visar man att detta leder till en motsägelse, t.ex. att 1=21 = 2 eller att jämna tal både är och inte är delbara med 2.2. Så länge resonemanget som leder fram till motsägelsen är korrekt kan man dra slutsatsen att ¬\negR är falskt, vilket betyder att det ursprungliga påståendet R måste vara sant. För implikationer på formen PQ,P \Rightarrow Q, kan motsatsen

¬(PQ)\neg(\text{P} \Rightarrow \text{Q}) \; skrivas som \; P och ¬\negQ.
Då antar man alltså att både påståendet P och motsatsen till påståendet Q är sanna och undersöker sedan eventuella motsägelser som detta leder till. För påståendena P och Q ovan skulle man då anta att talen aa och bb är udda samt att produkten aba\cdot b är jämn.
Uppgift

Tula säger att ett heltal är jämnt om dess kvadrat är jämn. Visa detta med ett indirekt bevis.

Lösning
Vi börjar med att formulera det Tula säger matematiskt och kallar heltalet för a.a. Tula säger då att om a2a^2 är jämnt så är aa är jämnt: a2  jmnta¨a  jmnt.a¨ a^2 \ \ \text{jämnt} \quad \Rightarrow \quad a \ \ \text{jämnt.} Vi ska visa detta med ett indirekt bevis och negerar därför båda påståendena och byter plats på dem. ¬(a  jmnta¨)¬(a2  jmnta¨) \neg\left(a \ \ \text{jämnt}\right) \quad \Rightarrow \quad \neg \left(a^2 \ \ \text{jämnt}\right) Negationen till att aa är jämnt är att det är udda och negationen till att a2a^2 är jämnt är att det är udda. Detta betyder att vi ska visa att a uddaa2 udda. a \text{ udda} \quad \Rightarrow \quad a^2 \text{ udda}. Detta påstående är helt ekvivalent med det som Tula säger. Eftersom jämna tal är delbara med 22 kan de alltid skrivas på formen 2k,2k, där kk är ett heltal. Efter varje jämnt tal kommer ett udda och det betyder att alla udda tal kan skrivas på formen 2k+1.2k+1. Vi låter aa vara 2k+12k+1 och kvadrerar det.
a=2k+1a=2k+1
a2=(2k+1)2a^2=(2k+1)^2
a2=(2k)2+22k1+12a^2=(2k)^2+2\cdot2k\cdot 1+1^2
a2=(2k)2+4k+1a^2=(2k)^2+4k+1
(ab)c=acbc \left(a b\right)^{c}=a^c b^c
a2=4k2+4k+1a^2=4k^2+4k+1
De två första termerna innehåller båda faktorn 2.2. Vi bryter ut den.
a2=4k2+4k+1a^2=4k^2+4k+1
Dela upp i faktorer
a2=22k2+22k+1a^2=2\cdot2k^2+2\cdot2k+1
a2=2(2k2+2k)+1a^2=2\left(2k^2+2k\right)+1
Uttrycket 2k2k är ett jämnt tal — det har vi redan konstaterat. 2k22k^2 är en produkt av heltal eftersom kk är ett heltal, och när man multiplicerar heltal får man ett heltal. 2k2+2k2k^2+2k är alltså en summa av heltal vilket betyder att det också är ett heltal. Vi kan kalla det m.m. a2=2(2k2+2k)+1=2m+1. a^2=2\left(2k^2+2k\right)+1=2m+1. Eftersom mm är ett heltal betyder det att 2m2m är jämnt, enligt definitionen av jämna tal. Efter ett jämnt tal kommer alltid ett udda tal så 2m+12m+1 är udda. Detta innebär alltså att a2a^2 är udda.
Q.E.D.
Exempel

Kommentar

I beviset antas att både summan av heltal och produkten av heltal är heltal. Detta är en egenskap hos heltalen som kallas slutenhet och som under vissa omständigheter anses vara ett axiom. Det brukar därför vara tillåtet att anta detta utan bevis.

Visa lösning Visa lösning
Begrepp

Jämförelse av bevis

Till sist sammanfattas de olika bevistyperna och hur de tolkas för påståendena P: Talen a och b r uddaa¨Q: Produkten ab r udda,a¨\begin{aligned} &\text{P: Talen } a \text{ och } b \text{ är udda} \\ &\text{Q: Produkten } a\cdot b \text{ är udda,} \end{aligned} där aa och bb är heltal. Tabellen visar vilken strategi som används i respektive metod, samt hur de tillämpas.

Bevis Strategi Tillämpning
Direkt PQ\text{P} \Rightarrow \text{Q} Anta att aa och bb är udda
och visa att aba\cdot b är udda
Indirekt ¬Q¬P\neg \text{Q} \Rightarrow \neg \text{P} Anta att produkten aba\cdot b är jämn
och visa att minst en av aa och bb
måste vara jämn
Motsägelse P och ¬\negQ \Rightarrow \bot Anta att aa och bb är udda
samt att produkten aba\cdot b är jämn
och visa att detta leder till en motsägelse

Uppgifter

{{ grade.displayTitle }}
{{ exercise.headTitle }}
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan
Test
{{ 'mldesktop-selftest-notests' | message }} {{ article.displayTitle }}!
{{ tests.error }}

{{ 'ml-heading-exercise' | message }} {{ focusmode.exercise.exerciseName }}

keyboard_backspace
{{ section.title }} keyboard_backspace {{ 'ml-btn-previous' | message }} {{ 'ml-btn-previous-exercise' | message }} {{ 'ml-btn-next-exercise' | message }} keyboard_backspace {{ 'ml-btn-next-exercise' | message }}