Mängder och logik

En mängd är en samling saker utan ordning och utan dubbletter. {1, 2, 3} är samma mängd som {3, 1, 2}.

Operation	Symbol	Betyder	Exempel
Union	$A \cup B$	allt som finns i minst en	$\{1,2\} \cup \{2,3\} = \{1,2,3\}$
Snitt	$A \cap B$	det som finns i båda	$\{1,2\} \cap \{2,3\} = \{2\}$
Differens	$A \setminus B$	i A men inte i B	$\{1,2\} \setminus \{2,3\} = \{1\}$
Tillhör	$x \in A$	x är med i A	$2 \in \{1,2\}$
Delmängd	$A \subseteq B$	allt i A finns i B	$\{1\} \subseteq \{1,2\}$

Logiken är samma sak fast för påståenden:

	Symbol	Sant när
OCH	$\land$	båda är sanna
ELLER	$\lor$	minst en är sann (inte «antingen eller»)
INTE	$\neg$	påståendet är falskt
MEDFÖR	$\Rightarrow$	om det första är sant måste det andra vara det

Den vanligaste missuppfattningen: matematiskt ELLER är inkluderande. «Kaffe eller te» i matematiken tillåter båda.

Implikation är den svåraste. $P \Rightarrow Q$ är falsk endast när $P$ är sann och $Q$ falsk:

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

De två sista raderna förvånar: «om månen är av ost så är 2+2=5» är sann, eftersom förutsättningen är falsk. Ett löfte som aldrig utlöses bryts inte.

De Morgans lagar — används konstant i både logik och kod:

$\neg(P \land Q) \equiv \neg P \lor \neg Q, \qquad \neg(P \lor Q) \equiv \neg P \land \neg Q$

I Python: not (a and b) är samma sak som (not a) or (not b). Att negera en sammansatt villkorsats vänder också konnektivet — det är den vanligaste buggen när man förenklar en if-sats.

Kvantorer gör det möjligt att skriva definitioner:

Symbol	Uttal	Betyder
$\forall$	«för alla»	gäller varje element
$\exists$	«det finns»	minst ett element uppfyller det

Definitionen av en delmängd blir då: $A \subseteq B \iff \forall x\,(x \in A \Rightarrow x \in B)$.

Negation av kvantorer vänder dem: $\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$. Motsatsen till «alla svanar är vita» är inte «inga svanar är vita» utan «det finns en svan som inte är vit». Det är exakt varför ett enda motexempel räcker för att falsifiera ett påstående — och varför testning fungerar.

A = {1, 2, 3, 4}
B = {3, 4, 5}

print(A | B)            # {1, 2, 3, 4, 5}   union
print(A & B)            # {3, 4}            snitt
print(A - B)            # {1, 2}            differens
print(A ^ B)            # {1, 2, 5}         symmetrisk differens (i exakt en)
print(3 in A, {1, 2} <= A)          # True True  (tillhör, delmängd)

# De Morgan i praktiken
for a in (True, False):
    for b in (True, False):
        assert (not (a and b)) == ((not a) or (not b))
        assert (not (a or b)) == ((not a) and (not b))
print("De Morgan håller")

# Kvantorer: all() är ∀, any() är ∃
tal = [2, 4, 6, 8]
print(all(x % 2 == 0 for x in tal))     # True   ∀x: x är jämnt
print(any(x > 7 for x in tal))          # True   ∃x: x > 7

# Negation vänder kvantorn — motexemplet
print(not all(x > 3 for x in tal), next(x for x in tal if not x > 3))   # True 2

# Mängder används på riktigt hela tiden i dataarbete
traning = {"a1", "a2", "a3", "a4"}
test    = {"a4", "a5"}
lackage = traning & test
print(f"läckage: {lackage or 'inget'}")     # läckage: {'a4'}

Sista exemplet är inte påhittat: att kontrollera traning & test är den snabbaste kontrollen mot dataläckage som finns, och den tar en rad.