Bevis och motsägelsebevis
Som nämnts i avsnittet Vad är logik? bygger matematiken på definitioner, satser och bevis. I det här avsnittet kommer vi gå igenom några olika former av bevis och varför dessa är giltiga.
Bevis
Bevis brukar allt som oftast börja med ett antagande. Varför kan ett bevis börja med ett antagande om beviset ska visa att ett påstående alltid är sant? För att illustrera detta gör vi ett exempel.
Exempel
Sats: Om \(x\) är ett jämnt tal så är \(x^2\) delbart med 4.
Bevis: Antag att \(x\) är jämnt. Då kan vi skriva \(x=2k\) för något heltal \(k\) (detta är definitionen för ett jämnt tal). Vi får
$$x^2=(2k)^2=4k^2$$
Eftersom 4 är en faktor i \(x^2\) så är \(x^2\) delbart med 4. Vilket skulle visas.
Varför kan vi börja beviset med att anta att \(x\) är jämnt? Detta är för att satsen säger "Om påståendet \(P\) är sant, så kommer \(Q\) vara sant". I det här fallet är \(P\) påståendet "\(x\) är ett jämnt tal" och \(Q\) är "\(x^2\) är delbart med 4". Vi har alltså bevisat \(P\implies Q\).
\(P\implies Q\) kan uttalas på olika sätt: "\(P\) medför \(Q\)", "Om \(P\) så \(Q\)", "\(P\) implicerar \(Q\)" eller "\(P\) är tillräckligt för \(Q\)".
Vi hade även kunnat anta \(\neg Q\) och visa att det leder till \(\neg P\). Då hade beviset varit en variant av ett såkallat motsägelsebevis och vi hade visat att \(\neg Q\implies \neg P\). Vi kan visa att \(P\implies Q\) är ekvivalent med \(\neg Q\implies \neg P\) med hjälp av två sanningstabeller.
| \(P\) | \(Q\) | \(P\implies Q\) |
| s | s | s |
| s | f | f |
| f | s | s |
| f | f | s |
| \(\neg P\) | \(\neg Q\) | \(\neg Q\implies \neg P\) |
| f | f | s |
| f | s | f |
| s | f | s |
| s | s | s |
Som vi ser är den högra kolumnen i båda tabellerna lika, vilket visar att
$$(P\implies Q)\iff(\neg Q\implies \neg P)$$
Motsägelsebevis
Det finns många olika grenar inom logiken, till exempel klassisk logik. I den klassiska logiken är ett påstående \(P\) antingen sant, eller så är det falskt. Direkta bevis går ut på att visa att ett påstående \(P\) är sant genom logiska resonemang och argument, eller så motbevisar man påståendet, det vill säga man visar att \(\neg P\) är sant.
Till skillnad från direkta bevis är det ibland enklare att bevisa ett påstående med hjälp av ett motsägelsebevis. Motsägelsebevis kan se ut på lite olika sätt. Om vi till exempel vill visa att ett påstående \(P\) är sant, kan vi istället visa att \(\neg P\) leder till en omöjlighet. Detta kallas för ett motsägelsebevis och ibland för "Reductio ad absurdum" (latin, "återförande på det orimliga").
Ett av de mest kända motsägelsebevisen är beviset för följande sats.
Sats: \(\sqrt{2}\) är irrationellt.
Bevis: Antag att \(\sqrt{2}\) inte är irrationellt, det vill säga \(\sqrt{2}=\dfrac{a}{b}\), där \(a\) och \(b\) är heltal och \(b\neq 0\). Antag även att den största gemensamma delaren (SGD) för \(a\) och \(b\) är 1. Detta betyder att \(\dfrac{a}{b}\) är förkortat så långt som möjligt, hade det inte varit det är det bara för oss att förkorta det.
Kvadrering av båda sidor och lite omflyttning ger att
$$a^2=2b^2$$
vilket betyder att \(a^2\) är jämnt, vilket i sin tur innebär att \(a\) är jämnt (vilket går att visa med ett motsägelsebevis).
Detta innebär att det finns ett heltal \(a_1\) sådant att \(a=2a_1\). Stoppar vi in detta i ekvationen och förkortar får vi
$$2a_1^2=b^2$$
vilket betyder att \(b\) är jämnt. Alltså är både \(a\) och \(b\) jämna, vilket är en motsägelse till att \(\dfrac{a}{b}\) är förkortat så långt som möjligt. Alltså är vårt påstående att \(\sqrt{2}\) är rationellt falskt, vilket innebär att satsen är bevisad.
Övning
Skriv upp sanningstabellen för \(P\lor(Q\land R)\).
Tips: Den består av åtta rader.
Lösning
| \(P\) | \(Q\) | \(R\) | \(P\lor(Q\land R)\) |
| s | s | s | s |
| s | s | f | s |
| s | f | s | s |
| s | f | f | s |
| f | s | s | s |
| f | s | f | f |
| f | f | s | f |
| f | f | f | f |
Det kan vara bra att börja med att göra sanningstabellen för \(Q\land R\) för att sedan använda resultatet för att fylla i tabellen ovan.