2024-09-04

Logik

Ytterligare operationer

Operator	Notation	Förklaring	Övning
Exklusivt eller	$P \oplus Q$	XOR	$(P \lor Q) \land \neg (P \land Q)$
Implikativa	$P \to Q$	$P$ implicerar/medför $Q$	$(P \land Q) \lor \neg P$
Ekvivalens	$P \leftrightarrow Q$	$P$ om och endast om $Q$	$(P \land Q) \lor (\neg P \land \neg Q)$

Sanningstabell

$P$	$Q$	$P \oplus Q$	$P \to Q$	$P \leftrightarrow Q$
1	1	0	1	1
1	0	1	0	0
0	1	1	1	0
0	0	0	1	1

Prioriteringsregler

Parenteser
$\neg$
Allt annat

Tautologier

En sammansatt utsaga, beroende på utsagor $P_{1}, …, P_{n}$ sådan att den alltid är sann, oberoende av sanningsvärden för, kallas för tautologi.

Exempel

P \lor \neg P

(P \land (P \to Q)) \to Q

Implikation och ekvivalens

Vi säger att $P$ implicerar $Q$ logiskt om $P \to Q$ är en tautologi.

Notation: $P ⟹ Q$

Vi säger att $P$ är logiskt ekvivalent med $Q$ om $P \leftrightarrow Q$ är en tautologi.

Notation: $P ⟺ Q$

Exempel

\neg (P \lor Q) ⟺ \neg P \lor \neg Q

$P$	$Q$	$P \lor Q$	$\neg (P \land Q)$	$\neg P \land \neg Q$
1	1	1	0	0
1	0	1	0	0
0	1	1	0	0
0	0	0	1	1

P \to Q ⟺ \neg Q \to \neg P

$P \to Q$ ej logiskt ekvivalent med $Q \to P$
Samma sak för $P \to Q$ och $\neg P \to \neg Q$

Argument & Bevis

Logiskt argument

Ett logiskt argument består av ett antal ingående utsagor (hypoteser) $H_{1}, …, H_{n}$ (som i sin tur byggs upp av utsagor $P_{1}, …, P_{m}$ ) och en slutsats $C$ .

Ett logiskt argument är giltigt om $C$ är sann så snart alla hypoteser är sanna.
// Ett giltigt logiskt argument är giltigt om $(H_{1} \land H_{2} \land … \land H_{n}) \to C$ är en tautologi.

Notation 1:

$H_{1}$
$H_{2}$
$⋮$
$H_{n}$
—
C

Matematiska bevis

Vill gå från axiom till slutsatser (matematiska satser/teorem)
Typiskt: Startar från tidigare etablerade satser.

Specialfall: Motsägelsebevis

Ett sätt att visa en slutsats $P$ är att anta att $P$ är falskt (dvs $\neg P$ ) och bevisa en uppenbart falskt utsaga $Q$ . Använder logiska relationen:

\neg P \to Q ⟺ \neg Q \to P

Exempel

Sats: Det finns inga heltal $a, b$ , sådana att $\sqrt{2} = \frac{a}{b}$

Bevis: Antag att satsen är falsk, dvs det finns heltal $a, b$ så att $\sqrt{2} = \frac{a}{b}$ . Kan anta att största gemensamma nämnare för $a, b$ är $1$ .

\sqrt{2} = \frac{a}{b} ⟹ 2 = \frac{a^{2}}{b^{2}} ⟹ 2 b^{2} = a^{2}

$a$ måste vara ett jämnt tal.

⟹ det finns ett heltal m så att a = 2 m

⟹ a^{2} = (2 m)^{2} = 4 m^{2}

Sätt in ovan $2 b^{2} = 4 m^{2}$

⟹ b^{2} = 2 m^{2}

b ett jämnt tal ⟹ det finns ett heltal n så att b = 2 n

⟹ \sqrt{2} = \frac{a}{b} = \frac{2 m}{2 n} = \frac{m}{n}

⟹ a, b har ej största gemensamma nämnare 1 ⟹ antagandet falskt

⟹ finns ej heltal a, b så \sqrt{2} = \frac{a}{b}

Kvantifiera/kvantorer

Antag att $P (x)$ är ett predikat. Definierar kvantorerna
$\forall$ (allkvantorn) och $\exists$ (existenskvantorn)

$\forall x : P (x)$ utsaga som är sann om $P (x)$ är sann för alla $x$ .

$\exists x : P (x)$ utsaga som är sann om det finns minst ett $x$ för vilket $P (x)$ är sann.

Exempel

För alla heltal $x$ gäller $x \leq 5$

$P (x) : x \leq 5$
$u : alla heltal$
$\forall x \in Z : P (x)$

"Det finns ett land i världen som ligger i Europa."

$x ett land i världen, u : alla länder$
$P (x) : x ligger i Europa$
$\exists x \in u : P (x)$