Logik och bevisföring

Kurs: M0065M

---

Logiken ger ett exakt språk för “om … så” och “om och endast om”. Vi behöver det för två saker i analysen: för att läsa och skriva bevis, och för att räkna ekvationer rätt. Varje steg i en ekvationslösning är en implikation eller en ekvivalens, och skillnaden mellan dem avgör om vi får falska rötter eller tappar riktiga.

Idén

En utsaga är ett påstående som är antingen sant eller falskt, men inte båda. Logiska symboler binder ihop utsagor, och en bevismetod är ett säkert sätt att gå från det vi vet ($P$) till det vi vill visa ($Q$).

---

1. Logiska symboler

Symbol	Betydelse
$\wedge$	och
$\vee$	eller
$\neg$	icke
$\Rightarrow$	medför
$⟺$	om och endast om
$\forall$	för alla
$\exists$	det finns

En utsaga som innehåller en variabel, som $x^2-4x+3=0$, kallas öppen: den är sann för vissa $x$ och falsk för andra. Uttrycket $x^2-4x+3$ utan likhetstecken är ingen utsaga alls.

Sanningsvärden. $P\vee Q$ är sann när minst en av $P$ och $Q$ är sann (inkluderande eller). $P\Rightarrow Q$ är falsk bara i ett fall: när $P$ är sann och $Q$ falsk.

$P$	$Q$	$P\wedge Q$	$P\vee Q$	$P\Rightarrow Q$	$P⟺Q$
S	S	S	S	S	S
S	F	F	S	F	F
F	S	F	S	S	F
F	F	F	F	S	S

Gäller både $P\Rightarrow Q$ och $Q\Rightarrow P$ skriver vi $P⟺Q$. Exempelvis gäller $x=3\Rightarrow x^2=9$, men inte omvändningen, eftersom även $x=-3$ ger $x^2=9$.

---

2. Logik vid ekvationslösning

Varje omskrivning av en ekvation är en implikation. Är alla steg ekvivalenser har vi exakt rätt lösningsmängd; är något steg bara en implikation $\Rightarrow$ kan falska rötter smyga sig in, och de måste prövas bort.

• Faktorisera, dela inte. Ur $x^3-x^2=2x$ får vi $x(x^2-x-2)=0⟺x(x+1)(x-2)=0⟺x\in \{0,-1,2\}$. Delar vi i stället med $x$ tappar vi roten $x=0$.
• Kvadrering ger bara $\Rightarrow$. $a=b\Rightarrow a^2=b^2$, men inte omvänt. Efter kvadrering måste varje rot prövas i den ursprungliga ekvationen.

Exempel — En rotekvation

Vi löser $\sqrt{x+1}-\sqrt{4-x}=1$.

Lösning

Flytta och kvadrera. $\sqrt{x+1}=1+\sqrt{4-x}$ ger efter kvadrering

$$x+1=1+2\sqrt{4-x}+(4-x)⟺2x-4=2\sqrt{4-x}⟺x-2=\sqrt{4-x}.$$

Kvadrera igen (bara $\Rightarrow$): $(x-2{)}^2=4-x⟺x^2-3x=0⟺x(x-3)=0$, så $x=0$ eller $x=3$.

Pröva. $x=0$: $\sqrt{1}-\sqrt{4}=-1\ne 1$, falsk rot. $x=3$: $\sqrt{4}-\sqrt{1}=1$, stämmer.

$$\boxed{x=3}$$

Den falska roten kommer från kvadreringen: $x=0$ löser $-(x-2)=\sqrt{4-x}$, inte $x-2=\sqrt{4-x}$.

Stämmer med det handskrivna lösningsförslaget.

---

3. Vanliga bevismetoder

• Direkt bevis: antag $P$, härled $Q$.
• Motsägelsebevis: antag $\neg Q$, härled motsägelse.
• Kontrapositiv: visa $\neg Q\Rightarrow \neg P$.
• Induktion: se Matematisk induktion.
• Motexempel: för att visa att ett påstående “för alla $x$ gäller …” är falskt räcker det med ett enda $x$ där det inte gäller.

Direkta bevis om heltal bygger ofta på att ett jämnt tal kan skrivas $n=2k$ och ett udda $n=2k+1$, med $k$ heltal.

Kontrapositionen är det logiska skälet till att indirekta bevis fungerar:

$$\boxed{(P\Rightarrow Q)⟺(\neg Q\Rightarrow \neg P)}$$

Exempel: “om $n^2$ är jämnt så är $n$ jämnt” är svårt att visa direkt. Kontrapositivt blir det “om $n$ är udda så är $n^2$ udda”, och det följer av $(2k+1{)}^2=2(2k^2+2k)+1$.

Härledning: kontrapositionen är ekvivalent med implikationen

Ställ upp sanningstabellen för båda:

$P$	$Q$	$P\Rightarrow Q$	$\neg Q$	$\neg P$	$\neg Q\Rightarrow \neg P$
S	S	S	F	F	S
S	F	F	S	F	F
F	S	S	F	S	S
F	F	S	S	S	S

Kolumnerna för $P\Rightarrow Q$ och $\neg Q\Rightarrow \neg P$ är lika på varje rad, så utsagorna är ekvivalenta. Omvändningen $Q\Rightarrow P$ har däremot kolumnen S, S, F, S och är inte ekvivalent med $P\Rightarrow Q$.

Härledning: det finns oändligt många primtal (motsägelsebevis)

Antag motsatsen: det finns bara ändligt många primtal $p_1<p_2<\cdots <p_n$. Bilda

$$m=1+p_1{p}_2\cdots p_n.$$

Eftersom $m>p_n$ kan $m$ inte vara ett primtal, så $m$ är delbart med något primtal, säg $p_i$. Då är även $m-p_1{p}_2\cdots p_n=1$ delbart med $p_i$, vilket är omöjligt eftersom $p_i>1$. Antagandet var alltså falskt. (Euklides.)

---

4. Negation av kvantifierade utsagor

$$\neg (\forall x:P(x))⟺\exists x:\neg P(x)$$

och på samma sätt

$$\neg (\exists x:P(x))⟺\forall x:\neg P(x).$$

Negationen av “och” blir “eller” och tvärtom (de Morgans lagar): $\neg (P\wedge Q)⟺\neg P\vee \neg Q$ och $\neg (P\vee Q)⟺\neg P\wedge \neg Q$.

Vanliga fel

• $⟺$ där bara $\Rightarrow$ gäller. Efter kvadrering eller multiplikation med ett uttryck som kan vara noll är steget bara en implikation; rötterna måste prövas.
• Dela med en faktor som kan vara noll. $x^3=x^2$ delat med $x^2$ ger $x=1$ och tappar $x=0$.
• Förväxla omvändning och kontraposition. $Q\Rightarrow P$ följer inte av $P\Rightarrow Q$; det gör däremot $\neg Q\Rightarrow \neg P$.
• Fel negation. Negationen av “minst 30” är “högst 29”, inte “högst 30”; negationen av “för alla” är “det finns ett som inte”.

---

5. Lösta övningar

Testuppgift 1.3 — Negationer

Vi formulerar negationen till utsagorna a) Minst 30 personer är närvarande. b) Högst 30 personer är närvarande. c) Högst 5 personer är frånvarande. d) Minst 5 personer är frånvarande. e) 5 personer är närvarande.

Lösning

Negationen ska vara sann exakt när utsagan är falsk. “Minst $30$” betyder $n\ge 30$, och $\neg (n\ge 30)⟺n<30⟺n\le 29$ för heltal.

a) $\boxed{\text{Ho¨gst 29 personer a¨r na¨rvarande.}}$

b) $\neg (n\le 30)⟺n\ge 31$: $\boxed{\text{Minst 31 personer a¨r na¨rvarande.}}$

c) $\boxed{\text{Minst 6 personer a¨r fra˚nvarande.}}$

d) $\boxed{\text{Ho¨gst 4 personer a¨r fra˚nvarande.}}$

e) $\neg (n=5)⟺n\le 4\vee n\ge 6$: $\boxed{\text{Ho¨gst 4 eller minst 6 personer a¨r na¨rvarande.}}$

Facit: a) Högst 29 personer är närvarande. b) Minst 31 personer är närvarande. c) Minst 6 personer är frånvarande. d) Högst 4 personer är frånvarande. e) Högst 4 eller minst 6 personer är närvarande.

Testuppgift 1.7 — Ekvationer med falska rötter

Vi löser ekvationerna a) $x^3=x^2$ b) $x-\sqrt{4-2x}=2$ c) $\sqrt{x-1}\cdot \sqrt{x+1}=\sqrt{15}$.

Lösning

a) Faktorisera i stället för att dela: $x^3-x^2=0⟺x^2(x-1)=0$, så

$$\boxed{x_{1,2}=0,x_3=1}$$

($x=0$ är en dubbelrot.)

b) $x-2=\sqrt{4-2x}$. Kvadrering ger ($\Rightarrow$) $x^2-4x+4=4-2x⟺x(x-2)=0$, alltså $x=0$ eller $x=2$. Prövning: $x=0$ ger $0-\sqrt{4}=-2\ne 2$, falsk rot. $x=2$ ger $2-0=2$, stämmer.

$$\boxed{x=2}$$

c) Båda rötterna är definierade bara för $x\ge 1$. Där gäller $\sqrt{x-1}\sqrt{x+1}=\sqrt{x^2-1}$, och kvadrering ger $x^2-1=15$, alltså $x=\pm 4$. Men $x=-4$ ligger utanför definitionsmängden ($\sqrt{-5}$ finns inte), så

$$\boxed{x=4}$$

Facit: a) $x_{1,2}=0$, $x_3=1$ b) $x=2$ c) $x=4$.

Testuppgift 1.9 — Ett direkt bevis

Vi ger ett direkt bevis för satsen: “Om $n$ är udda så är $n^2+n$ jämnt.”

Lösning

Förutsättning. $n$ udda, alltså $n=2k+1$ för något heltal $k$.

Räkna.

$$n^2+n=(2k+1{)}^2+(2k+1)=(2k+1)(2k+1+1)=2(2k+1)(k+1).$$

Slutsats. $(2k+1)(k+1)$ är ett heltal, så $n^2+n$ är två gånger ett heltal:

$$\boxed{n^2+n=2(2k+1)(k+1)\text{a¨r ja¨mnt}}$$

(Påståendet gäller för övrigt alla heltal, eftersom $n^2+n=n(n+1)$ är en produkt av två på varandra följande tal.)

Facit: $n^2+n=(2k+1{)}^2+2k+1=(2k+1)(2k+1+1)=2(2k+1)(k+1)$.

---

Se även

• Mängdlära
• Matematisk induktion
• Polynom och faktorisering