Sets and logic

A set is a collection of things without an order and without duplicates. {1, 2, 3} is the same set as {3, 1, 2}.

Operation	Symbol	Means	Example
Union	$A \cup B$	everything that is in at least one	$\{1,2\} \cup \{2,3\} = \{1,2,3\}$
Intersection	$A \cap B$	what is in both	$\{1,2\} \cap \{2,3\} = \{2\}$
Difference	$A \setminus B$	in A but not in B	$\{1,2\} \setminus \{2,3\} = \{1\}$
Belongs to	$x \in A$	x is in A	$2 \in \{1,2\}$
Subset	$A \subseteq B$	everything in A is in B	$\{1\} \subseteq \{1,2\}$

Logic is the same thing but for statements:

	Symbol	True when
AND	$\land$	both are true
OR	$\lor$	at least one is true (not «either or»)
NOT	$\neg$	the statement is false
IMPLIES	$\Rightarrow$	if the first is true the second must be too

The most common misunderstanding: mathematical OR is inclusive. «Coffee or tea» in mathematics allows both.

Implication is the hardest one. $P \Rightarrow Q$ is false only when $P$ is true and $Q$ is false:

$P$	$Q$	$P \Rightarrow Q$
T	T	T
T	F	F
F	T	T
F	F	T

The last two rows surprise people: «if the moon is made of cheese then 2+2=5» is true, because the premise is false. A promise that is never triggered is not broken.

De Morgan's laws — used constantly in both logic and code:

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

In Python: not (a and b) is the same thing as (not a) or (not b). Negating a compound condition flips the connective too — that is the most common bug when simplifying an if statement.

Quantifiers make it possible to write definitions:

Symbol	Read as	Means
$\forall$	«for all»	holds for every element
$\exists$	«there exists»	at least one element satisfies it

The definition of a subset then becomes: $A \subseteq B \iff \forall x\,(x \in A \Rightarrow x \in B)$.

Negating a quantifier flips it: $\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$. The opposite of «all swans are white» is not «no swans are white» but «there is a swan that is not white». That is exactly why a single counterexample is enough to falsify a claim — and why testing works.

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

print(A | B)            # {1, 2, 3, 4, 5}   union
print(A & B)            # {3, 4}            intersection
print(A - B)            # {1, 2}            difference
print(A ^ B)            # {1, 2, 5}         symmetric difference (in exactly one)
print(3 in A, {1, 2} <= A)          # True True  (belongs to, subset)

# De Morgan in practice
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 holds")

# Quantifiers: all() is ∀, any() is ∃
numbers = [2, 4, 6, 8]
print(all(x % 2 == 0 for x in numbers))     # True   ∀x: x is even
print(any(x > 7 for x in numbers))          # True   ∃x: x > 7

# Negation flips the quantifier — the counterexample
print(not all(x > 3 for x in numbers), next(x for x in numbers if not x > 3))   # True 2

# Sets are used for real all the time in data work
train = {"a1", "a2", "a3", "a4"}
test  = {"a4", "a5"}
leakage = train & test
print(f"leakage: {leakage or 'none'}")      # leakage: {'a4'}

The last example is not made up: checking train & test is the fastest check against data leakage there is, and it takes one line.