Logic is the language of precise reasoning. It underlies every if statement you write, digital circuits, database queries and mathematical proof.

#Propositions

A proposition is a declarative statement that is either true (T) or false (F), but not both.

We name propositions with letters p, q, r …

#Connectives

#Implication: the tricky one

"If you score above 90, you get an O grade." The promise is broken only when you score above 90 and do not get an O. If you score below 90, the promise says nothing — so the implication is true (vacuously).

Ways to say p → q in English: "if p, then q", "p implies q", "q if p", "p only if q", "p is sufficient for q", "q is necessary for p", "q whenever p".

From p → q we form three related statements:

"If it rains, the ground is wet." Contrapositive: "If the ground is not wet, it did not rain" — same meaning. Converse: "If the ground is wet, it rained" — not the same (a sprinkler could have wet it).

#Build any truth table

Type a formula and press Enter. Use ! or ~ for NOT, & for AND, | for OR, ^ for XOR, -> for implies and <-> for if and only if.

#Truth tables in code

With n variables a truth table has 2ⁿ rows. Python can generate it:

from itertools import product

def implies(a, b):
    return (not a) or b

print(f"{'p':5} {'q':5} {'r':5} | (p→q)∧(q→r) → (p→r)")
for p, q, r in product([True, False], repeat=3):
    value = implies(implies(p, q) and implies(q, r), implies(p, r))
    print(f"{p!s:5} {q!s:5} {r!s:5} | {value}")

p     q     r     | (p→q)∧(q→r) → (p→r)
True  True  True  | True
True  True  False | True
True  False True  | True
True  False False | True
False True  True  | True
False True  False | True
False False True  | True
False False False | True

Every row is True: this formula (the hypothetical syllogism) is a tautology.

#Tautology, contradiction, contingency

#Precedence

¬ binds tightest, then ∧, then ∨, then →, then ↔. So ¬p ∨ q ∧ r means (¬p) ∨ (q ∧ r). Use brackets when in doubt.

#Translating English

Let p = "it is raining", q = "I carry an umbrella", r = "I get wet".

Two formulas are logically equivalent, written P ≡ Q, if they have the same truth value in every row of the truth table — equivalently, if P ↔ Q is a tautology.

#The laws

Equivalences involving implication:

#Proving equivalences by the laws

Show ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q:

Check any equivalence instantly — compare both columns:

#Normal forms

Every formula can be rewritten in a standard shape:

• Disjunctive normal form (DNF): an OR of AND-terms — a "sum of products". Example: (p ∧ ¬q) ∨ (¬p ∧ q).
• Conjunctive normal form (CNF): an AND of OR-clauses — a "product of sums". Example: (p ∨ q) ∧ (¬p ∨ ¬q).

DNF from a truth table: for each row where the formula is T, write the AND of the literals that make that row (p if p is T, ¬p if p is F); OR them together.

CNF from a truth table: for each row where the formula is F, write the OR of the negated literals; AND them together.

from itertools import product

def formula(p, q, r):
    return (p or q) and not r             # the function we want in normal form

names = "pqr"
minterms, maxterms = [], []
for row in product([True, False], repeat=3):
    lits = [n if v else "¬" + n for n, v in zip(names, row)]
    if formula(*row):
        minterms.append("(" + " ∧ ".join(lits) + ")")
    else:
        maxterms.append("(" + " ∨ ".join("¬" + n if v else n for n, v in zip(names, row)) + ")")
print("DNF:", " ∨ ".join(minterms))
print("CNF:", " ∧ ".join(maxterms))

DNF: (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ q ∧ ¬r)
CNF: (¬p ∨ ¬q ∨ ¬r) ∧ (¬p ∨ q ∨ ¬r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ q ∨ ¬r) ∧ (p ∨ q ∨ r)

CNF matters in computer science because SAT solvers work on CNF formulas; DNF and CNF also correspond to sum-of-products and product-of-sums circuits in Boolean algebra.

#Functionally complete sets

{¬, ∧, ∨} can express every Boolean function. So can {¬, ∧} (by De Morgan), and so can NAND alone or NOR alone — which is why chips can be built from a single gate type.

Propositional logic cannot express "every student passed" or "some number is prime" in a useful way. Predicate logic adds variables, predicates and quantifiers.

#Predicates

A predicate P(x) is a statement with a variable; it becomes a proposition once x is given a value.

• P(x): "x > 3". Then P(5) is true and P(1) is false.
• Q(x, y): "x + y = 10". Q(4, 6) is true.

The set of values x may take is the domain (universe of discourse).

#Quantifiers

With domain = {1, 2, 3, 4}:

• ∀x (x > 0) — true.
• ∀x (x is even) — false (counterexample: 1).
• ∃x (x is even) — true (witness: 2).
• ∃x (x > 10) — false.

On a finite domain, ∀ is a big AND and ∃ is a big OR — exactly Python's all and any:

domain = range(1, 21)
print("∀x x² ≥ x:          ", all(x * x >= x for x in domain))
print("∃x x² = 49:         ", any(x * x == 49 for x in domain))
print("∀x ∃y y > x:        ", all(any(y > x for y in domain) for x in domain))   # false here: nothing in 1..20 exceeds 20
print("∃y ∀x y ≥ x:        ", any(all(y >= x for x in domain) for y in domain))
print("counterexample to 'all odd numbers are prime':", next(x for x in domain if x % 2 == 1 and x > 1 and any(x % d == 0 for d in range(2, x))))

∀x x² ≥ x:           True
∃x x² = 49:          True
∀x ∃y y > x:         False
∃y ∀x y ≥ x:         True
counterexample to 'all odd numbers are prime': 9

#Negating quantifiers (De Morgan for quantifiers)

"Not every student passed" = "some student did not pass". "There is no perfect algorithm" = "every algorithm is imperfect".

#Nested quantifiers

The order of different quantifiers matters:

• ∀x ∃y (y > x): "for every number there is a bigger one" — true for the integers.
• ∃y ∀x (y > x): "there is a number bigger than every number" — false for the integers.

Negate nested quantifiers by flipping each one and negating the inside: ¬∀x ∃y P(x, y) ≡ ∃x ∀y ¬P(x, y).

#Translating English

Let S(x): "x is a student", C(x): "x has a laptop", the domain being all people.

#Rules of inference for quantifiers

Classic argument: "All humans are mortal; Socrates is human; therefore Socrates is mortal" uses universal instantiation followed by modus ponens.

A proof is a chain of logically valid steps from accepted facts to a conclusion. Proofs are how we know an algorithm is correct for all inputs, not just the ones we tested.

#Rules of inference

#Direct proof

To prove p → q: assume p, then use definitions and known facts to reach q.

Theorem. If n is odd, then n² is odd. Proof. Suppose n is odd, so n = 2k + 1 for some integer k. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. ∎

#Proof by contrapositive

Prove ¬q → ¬p instead, which is equivalent to p → q. Use it when the negations are easier to work with.

Theorem. If n² is even, then n is even. Proof. Contrapositive: if n is odd, then n² is odd — proved above. ∎

#Proof by contradiction

Assume the statement is false and derive something impossible.

Theorem. √2 is irrational. Proof. Suppose √2 = a/b in lowest terms. Then 2b² = a², so a² is even, so a is even: a = 2c. Then 2b² = 4c², so b² = 2c² is even, so b is even. But then a and b share the factor 2, contradicting "lowest terms". ∎

Theorem (Euclid). There are infinitely many primes. Proof. Suppose there are finitely many: p₁, p₂, …, pₙ. Let N = p₁p₂…pₙ + 1. No pᵢ divides N (each leaves remainder 1), so N's prime factors are not in the list — a contradiction. ∎

#Proof by cases

Split into cases that cover every possibility and prove each one.

Theorem. n² + n is even for every integer n. Proof. If n is even, n² and n are both even, so their sum is even. If n is odd, n² and n are both odd, and odd + odd is even. ∎

#Counterexamples

To disprove a universal statement ∀x P(x), one counterexample is enough.

Claim: "n² + n + 41 is prime for every n ≥ 0." It holds for n = 0 … 39, but fails at n = 40. Testing many cases is evidence, never proof:

def is_prime(n):
    return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1))

for n in range(45):
    if not is_prime(n * n + n + 41):
        print(f"counterexample: n = {n}, n^2 + n + 41 = {n*n + n + 41} = 41 x {(n*n + n + 41) // 41}")
        break
else:
    print("no counterexample found")

counterexample: n = 40, n^2 + n + 41 = 1681 = 41 x 41

#Existence proofs

• Constructive: exhibit the object. "There is an integer that is the sum of two cubes in two ways": 1729 = 1³ + 12³ = 9³ + 10³.
• Non-constructive: show it must exist without naming it (often by contradiction or the pigeonhole principle).

#Which technique?

Mathematical induction proves that a statement P(n) is true for every integer n ≥ n₀. Think of an infinite line of dominoes:

1. Base case: prove P(n₀) — the first domino falls.
2. Inductive step: prove that if P(k) is true (the inductive hypothesis), then P(k + 1) is true — each domino knocks over the next.

Together they prove P(n) for all n ≥ n₀.

#Example 1: sum of the first n integers

Claim. 1 + 2 + … + n = n(n + 1)/2 for all n ≥ 1.

Base case (n = 1): left side 1, right side 1·2/2 = 1. ✓

Inductive step: assume 1 + 2 + … + k = k(k + 1)/2. Then

1 + 2 + … + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2,

which is the formula for n = k + 1. ∎

#Example 2: divisibility

Claim. 3 divides n³ − n for all n ≥ 0.

Base: n = 0 gives 0, divisible by 3. ✓

Step: assume 3 | k³ − k. Then (k + 1)³ − (k + 1) = k³ + 3k² + 3k + 1 − k − 1 = (k³ − k) + 3(k² + k). Both parts are divisible by 3. ∎

#Example 3: an inequality

Claim. 2ⁿ > n² for all n ≥ 5.

Base: 2⁵ = 32 > 25. ✓

Step: assume 2ᵏ > k² with k ≥ 5. Then 2ᵏ⁺¹ = 2·2ᵏ > 2k² = k² + k² > k² + 2k + 1 = (k + 1)², because k² > 2k + 1 when k ≥ 3. ∎

(The base case matters: the claim is false for n = 2, 3, 4.)

#Checking a formula is not proving it

Code can test a formula for many n — useful for catching a wrong formula before you try to prove it:

def check(name, lhs, rhs, upto=50):
    bad = [n for n in range(1, upto + 1) if lhs(n) != rhs(n)]
    print(f"{name}: {'holds' if not bad else 'FAILS at n = ' + str(bad[0])} for n = 1..{upto}")

check("sum of first n odd numbers = n^2", lambda n: sum(2 * i - 1 for i in range(1, n + 1)), lambda n: n * n)
check("sum of squares = n(n+1)(2n+1)/6", lambda n: sum(i * i for i in range(1, n + 1)), lambda n: n * (n + 1) * (2 * n + 1) // 6)
check("sum of cubes = (n(n+1)/2)^2", lambda n: sum(i ** 3 for i in range(1, n + 1)), lambda n: (n * (n + 1) // 2) ** 2)
check("2^n > n^2", lambda n: 2 ** n > n * n, lambda n: True)

sum of first n odd numbers = n^2: holds for n = 1..50
sum of squares = n(n+1)(2n+1)/6: holds for n = 1..50
sum of cubes = (n(n+1)/2)^2: holds for n = 1..50
2^n > n^2: FAILS at n = 2 for n = 1..50

The last check fails at n = 2 — which is why that claim starts at n = 5.

#Strong induction

In strong induction the inductive step may assume P(n₀), P(n₀ + 1), …, P(k) — all earlier cases — to prove P(k + 1). Use it when the next case depends on cases further back.

Claim. Every integer n ≥ 2 is a product of primes. Proof. Base: 2 is prime. Step: consider k + 1. If it is prime, done. Otherwise k + 1 = a·b with 2 ≤ a, b ≤ k; by the hypothesis both a and b are products of primes, so k + 1 is too. ∎

Claim. Every postage of 12 or more rupees can be made from 4- and 5-rupee stamps. Proof. Base cases 12 = 4+4+4, 13 = 4+4+5, 14 = 4+5+5, 15 = 5+5+5. Step: for k + 1 ≥ 16, take the solution for k − 3 (true by hypothesis) and add one 4-rupee stamp. ∎

#Induction and computer science

• Recursion is induction in code: the base case of a recursive function is the base case of the proof, and the recursive call relies on the "inductive hypothesis" that smaller inputs are handled correctly.
• Loop invariants (correctness proofs) are induction on the number of iterations.
• Structural induction proves properties of trees and lists: true for the empty structure, and preserved when building larger ones.

A set is an unordered collection of distinct objects called elements. Order and repetition do not matter: {1, 2, 3} = {3, 1, 2} = {1, 1, 2, 3}.

#Notation

#Subsets and the power set

• A ⊆ B (subset): every element of A is in B. Every set is a subset of itself, and ∅ ⊆ A for every A.
• A ⊂ B (proper subset): A ⊆ B and A ≠ B.
• A = B exactly when A ⊆ B and B ⊆ A — the standard way to prove two sets are equal.

The power set P(A) is the set of all subsets of A. If |A| = n, then |P(A)| = 2ⁿ (each element is either in a subset or not).

from itertools import combinations

A = {"a", "b", "c"}
power_set = [set(c) for r in range(len(A) + 1) for c in combinations(sorted(A), r)]
print(len(power_set), "subsets:")
print([sorted(s) for s in power_set])

8 subsets:
[[], ['a'], ['b'], ['c'], ['a', 'b'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]

#Set operations

Try your own sets:

#Set identities

They mirror the laws of logic — ∪ is like ∨, ∩ like ∧, complement like ¬:

U = set(range(1, 11))
A, B = {1, 2, 3, 4, 5}, {4, 5, 6, 7}
comp = lambda X: U - X
print("(A ∪ B)′ =", sorted(comp(A | B)))
print("A′ ∩ B′  =", sorted(comp(A) & comp(B)))
print("De Morgan holds:", comp(A | B) == comp(A) & comp(B), comp(A & B) == comp(A) | comp(B))
print("|A ∪ B| = |A| + |B| - |A ∩ B|:", len(A | B), "=", len(A), "+", len(B), "-", len(A & B))

(A ∪ B)′ = [8, 9, 10]
A′ ∩ B′  = [8, 9, 10]
De Morgan holds: True True
|A ∪ B| = |A| + |B| - |A ∩ B|: 7 = 5 + 4 - 2

#Cartesian product

The Cartesian product A × B is the set of all ordered pairs (a, b) with a ∈ A and b ∈ B. |A × B| = |A| · |B|.

from itertools import product
sizes = ["S", "M", "L"]
colours = ["red", "blue"]
pairs = list(product(sizes, colours))
print(len(pairs), pairs)

6 [('S', 'red'), ('S', 'blue'), ('M', 'red'), ('M', 'blue'), ('L', 'red'), ('L', 'blue')]

Order matters in pairs: (1, 2) ≠ (2, 1), so A × B ≠ B × A in general.

#Cardinality of unions

For two sets: |A ∪ B| = |A| + |B| − |A ∩ B| — the intersection was counted twice. This is the inclusion–exclusion principle, extended in Counting.

#Countable and uncountable

A set is countable if its elements can be listed as a sequence (a one-to-one match with ℕ). ℤ and ℚ are countable; Cantor's diagonal argument shows ℝ is uncountable — there are "more" real numbers than integers.

A relation R from set A to set B is a subset of A × B. If (a, b) ∈ R we write a R b: "a is related to b". A relation on A is a subset of A × A.

Example on A = {1, 2, 3, 4}: R = "divides" = {(a, b) : a | b}.

R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}

#Representations

Matrix: M[i][j] = 1 if (i, j) ∈ R.

Digraph: an arrow from a to b for each pair, with a loop at a for each (a, a).

#Properties of a relation on A

"Divides" is reflexive, antisymmetric and transitive, but not symmetric (1 | 2, but 2 ∤ 1).

def properties(A, R):
    return {
        "reflexive": all((a, a) in R for a in A),
        "symmetric": all((b, a) in R for (a, b) in R),
        "antisymmetric": all(a == b for (a, b) in R if (b, a) in R),
        "transitive": all((a, d) in R for (a, b) in R for (c, d) in R if b == c),
    }

A = {1, 2, 3, 4}
divides = {(a, b) for a in A for b in A if b % a == 0}
same_parity = {(a, b) for a in A for b in A if a % 2 == b % 2}
less_than = {(a, b) for a in A for b in A if a < b}
for name, R in [("divides", divides), ("same parity", same_parity), ("less than", less_than)]:
    print(f"{name:12}", properties(A, R))

divides      {'reflexive': True, 'symmetric': False, 'antisymmetric': True, 'transitive': True}
same parity  {'reflexive': True, 'symmetric': True, 'antisymmetric': False, 'transitive': True}
less than    {'reflexive': False, 'symmetric': False, 'antisymmetric': True, 'transitive': True}

#Equivalence relations

A relation that is reflexive, symmetric and transitive is an equivalence relation. It splits A into disjoint equivalence classes: [a] = {x : x R a}.

Example: congruence mod 3 on ℤ — a ≡ b (mod 3) when 3 | (a − b). Its classes are:

• [0] = {…, −3, 0, 3, 6, …}
• [1] = {…, −2, 1, 4, 7, …}
• [2] = {…, −1, 2, 5, 8, …}

The classes form a partition of the set: they are non-empty, pairwise disjoint, and together cover everything. Conversely, every partition defines an equivalence relation ("in the same block").

A = range(0, 12)
classes = {}
for x in A:
    classes.setdefault(x % 3, []).append(x)      # same remainder = same class
for r, members in classes.items():
    print(f"[{r}] = {members}")

[0] = [0, 3, 6, 9]
[1] = [1, 4, 7, 10]
[2] = [2, 5, 8, 11]

#Closures

The closure of R with respect to a property is the smallest relation containing R that has the property.

def transitive_closure(A, R):
    R = set(R)
    for k in A:                          # Warshall: allow k as an intermediate vertex
        for i in A:
            for j in A:
                if (i, k) in R and (k, j) in R:
                    R.add((i, j))
    return R

A = [1, 2, 3, 4]
R = {(1, 2), (2, 3), (3, 4)}
print(sorted(transitive_closure(A, R)))

[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

(The same triple loop computes shortest paths in Floyd–Warshall.)

A relation on A is a partial order if it is reflexive, antisymmetric and transitive. The pair (A, ≼) is a partially ordered set (poset).

Examples:

• (ℤ, ≤) — the usual order.
• (ℤ⁺, |) — divisibility.
• (P(S), ⊆) — subsets ordered by inclusion.

In a partial order, some pairs may be incomparable: neither 2 | 3 nor 3 | 2. If every pair is comparable, it is a total (linear) order — like ≤ on numbers.

#Hasse diagrams

A Hasse diagram draws a poset compactly:

1. Draw smaller elements lower, so arrows always point up (and are dropped).
2. Omit self-loops (reflexivity is assumed).
3. Omit edges implied by transitivity: draw a → b only if b covers a (nothing in between).

#Special elements

For a poset (A, ≼) and a subset S:

In the divisors of 12: least element 1, greatest element 12. For S = {4, 6}: upper bounds {12}, so lub = 12; lower bounds {1, 2}, so glb = 2. For divisibility, lub = LCM and glb = GCD.

from math import gcd

D = [d for d in range(1, 13) if 12 % d == 0]
leq = lambda a, b: b % a == 0                     # a divides b
def lub(x, y): return min(u for u in D if leq(x, u) and leq(y, u))    # smallest common multiple in D
def glb(x, y): return max(l for l in D if leq(l, x) and leq(l, y))    # largest common divisor in D

print("divisors of 12:", D)
print("lub(4, 6) =", lub(4, 6), "  lcm =", 4 * 6 // gcd(4, 6))
print("glb(4, 6) =", glb(4, 6), "  gcd =", gcd(4, 6))
print("covering pairs (Hasse edges):",
      [(a, b) for a in D for b in D if a != b and leq(a, b) and not any(c not in (a, b) and leq(a, c) and leq(c, b) for c in D)])

divisors of 12: [1, 2, 3, 4, 6, 12]
lub(4, 6) = 12   lcm = 12
glb(4, 6) = 2   gcd = 2
covering pairs (Hasse edges): [(1, 2), (1, 3), (2, 4), (2, 6), (3, 6), (4, 12), (6, 12)]

#Lattices

A poset is a lattice if every pair of elements has both a least upper bound and a greatest lower bound.

• (Divisors of n, |) is a lattice (join = lcm, meet = gcd).
• (P(S), ⊆) is a lattice (join = ∪, meet = ∩).
• A poset with two maximal elements and nothing above them is not a lattice.

#Topological sorting

Every finite poset can be extended to a total order that respects it: repeatedly remove a minimal element. This is exactly topological sorting of a DAG — see Graph Algorithms.

A function f : A → B assigns to each element of A exactly one element of B.

• A is the domain; B is the codomain.
• f(a) = b: b is the image of a; a is a pre-image of b.
• The range is the set of all images: {f(a) : a ∈ A} ⊆ B.

A relation fails to be a function if some element of A has no image or two images.

#Types of functions

def classify(f, A, B):
    images = [f(a) for a in A]
    injective = len(set(images)) == len(images)
    surjective = set(images) == set(B)
    return f"injective={injective}, surjective={surjective}, bijective={injective and surjective}"

A = range(-3, 4)
print("x+1 :", classify(lambda x: x + 1, A, range(-2, 5)))
print("x^2 :", classify(lambda x: x * x, A, range(0, 10)))
print("2x  :", classify(lambda x: 2 * x, A, range(-6, 7)))

x+1 : injective=True, surjective=True, bijective=True
x^2 : injective=False, surjective=False, bijective=False
2x  : injective=True, surjective=False, bijective=False

#Composition

(g ∘ f)(x) = g(f(x)) — apply f first, then g. Composition is associative but not commutative:

f = lambda x: x + 3
g = lambda x: 2 * x
print("(g∘f)(5) =", g(f(5)))     # 2 * (5 + 3) = 16
print("(f∘g)(5) =", f(g(5)))     # 2 * 5 + 3 = 13

(g∘f)(5) = 16
(f∘g)(5) = 13

#Inverse functions

A function has an inverse f⁻¹ if and only if it is a bijection. Then f⁻¹(b) = a exactly when f(a) = b, and f⁻¹(f(x)) = x. Example: f(x) = 3x + 2 on ℝ has f⁻¹(y) = (y − 2)/3.

#Floor and ceiling

• ⌊x⌋ (floor): the largest integer ≤ x. ⌊3.7⌋ = 3, ⌊−3.7⌋ = −4.
• ⌈x⌉ (ceiling): the smallest integer ≥ x. ⌈3.2⌉ = 4, ⌈−3.2⌉ = −3.

They appear constantly in algorithm analysis: a binary tree with n nodes has height at least ⌈log₂(n + 1)⌉ − 1; splitting n items into pages of 10 needs ⌈n/10⌉ pages.

#Counting functions

For finite sets with |A| = m and |B| = n:

#Pigeonhole connection

If m > n, no function A → B can be injective: some two elements of A must share an image. That is the pigeonhole principle.

Counting answers "how many?" — how many passwords, how many paths, how many comparisons an algorithm makes. Almost every counting problem is built from a few simple rules.

#The sum rule

If a task can be done in one of m ways or one of n ways, with no overlap, there are m + n ways.

A student picks one elective from 5 CS electives or 3 maths electives: 5 + 3 = 8 choices.

#The product rule

If a task is a sequence of steps with m ways for the first and n ways for the second, there are m × n ways.

#Counting with the complement

Often it is easier to count what you don't want and subtract:

How many 8-bit strings contain at least one 1? All strings minus the all-zero string: 2⁸ − 1 = 255.

from itertools import product

passwords = ["".join(p) for p in product("ab1", repeat=4)]
with_digit = [p for p in passwords if "1" in p]
print(len(passwords), "passwords of length 4 over {a, b, 1}")
print(len(with_digit), "contain the digit, and 3^4 - 2^4 =", 3**4 - 2**4)

81 passwords of length 4 over {a, b, 1}
65 contain the digit, and 3^4 - 2^4 = 65

#The pigeonhole principle

If n + 1 (or more) pigeons fly into n holes, some hole contains at least two pigeons.

It sounds obvious, but it proves surprising things:

• Among any 13 people, two share a birth month.
• In any group of 367 people, two share a birthday.
• A hash table with m slots and m + 1 keys must have a collision.
• Among any 6 integers, two have the same remainder mod 5 — so their difference is divisible by 5.

#Generalised pigeonhole principle

If N objects go into k boxes, some box contains at least ⌈N/k⌉ objects.

• 100 students, 12 months → some month has at least ⌈100/12⌉ = 9 birthdays.
• How many cards must you draw from a standard deck to guarantee 3 of the same suit? Need ⌈N/4⌉ ≥ 3, so N = 2 × 4 + 1 = 9.

from math import ceil

def guarantee(per_box, boxes):
    return (per_box - 1) * boxes + 1          # smallest N with ceil(N/boxes) >= per_box

print("cards to guarantee 3 of a suit:", guarantee(3, 4))
print("people to guarantee 2 share a birth month:", guarantee(2, 12))
print("students so that 5 share a grade (grades O, A+, A, B+, P, F):", guarantee(5, 6))
print("minimum in the fullest month for 100 birthdays:", ceil(100 / 12))

cards to guarantee 3 of a suit: 9
people to guarantee 2 share a birth month: 13
students so that 5 share a grade (grades O, A+, A, B+, P, F): 25
minimum in the fullest month for 100 birthdays: 9

#Tree diagrams

When later choices depend on earlier ones, draw a tree. Example: how many bit strings of length 4 have no two consecutive 1s? Branching only on allowed bits gives 8 leaves: 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010. (In general the count is a Fibonacci number — see Recurrence Relations.)

#Factorial

n! = n × (n − 1) × … × 2 × 1, with 0! = 1. n! is the number of ways to arrange n distinct objects in a row.

#Permutations: order matters

The number of ways to arrange r objects chosen from n distinct objects:

P(n, r) = n! / (n − r)!

Example: gold, silver and bronze among 10 runners: P(10, 3) = 10 × 9 × 8 = 720.

#Combinations: order does not matter

The number of ways to choose r objects from n, ignoring order:

C(n, r) = n! / (r! (n − r)!), also written ⁿCᵣ or (n choose r)

Example: choose a 3-person team from 10: C(10, 3) = 720 / 3! = 120. Each team was counted 3! = 6 times among the permutations.

Useful identities: C(n, r) = C(n, n − r); C(n, 0) = C(n, n) = 1; and Pascal's rule C(n, r) = C(n − 1, r − 1) + C(n − 1, r).

from math import comb, perm, factorial
from itertools import permutations, combinations

print("P(10, 3) =", perm(10, 3), " C(10, 3) =", comb(10, 3))
print("arrangements of ABC:", ["".join(p) for p in permutations("ABC")])
print("2-subsets of ABCD:  ", ["".join(c) for c in combinations("ABCD", 2)])
print("5-card poker hands: ", comb(52, 5))
print("C(n, r) == C(n, n-r):", comb(12, 5) == comb(12, 7))

P(10, 3) = 720  C(10, 3) = 120
arrangements of ABC: ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
2-subsets of ABCD:   ['AB', 'AC', 'AD', 'BC', 'BD', 'CD']
5-card poker hands:  2598960
C(n, r) == C(n, n-r): True

#Which formula?

#Arrangements with identical objects

The number of distinct arrangements of n objects where n₁ are alike, n₂ are alike, …:

n! / (n₁! n₂! … nₖ!)

"MISSISSIPPI" has 11 letters: M×1, I×4, S×4, P×2 → 11! / (1! 4! 4! 2!) = 34,650.

from math import factorial
from collections import Counter

def arrangements(word):
    result = factorial(len(word))
    for count in Counter(word).values():
        result //= factorial(count)
    return result

for w in ["BOOK", "BANANA", "MISSISSIPPI", "KALVIUM"]:
    print(f"{w}: {arrangements(w)}")

BOOK: 12
BANANA: 60
MISSISSIPPI: 34650
KALVIUM: 5040

#Circular permutations

Arranging n people around a round table, where rotations count as the same: (n − 1)!. If clockwise and anticlockwise are also the same (a necklace): (n − 1)!/2.

#Stars and bars

The number of ways to put r identical items into n distinct boxes (or the number of non-negative integer solutions of x₁ + … + xₙ = r) is

C(n + r − 1, r)

Example: distribute 10 identical chocolates among 4 children: C(13, 10) = 286. If each child must get at least one, give one each first, then distribute 6: C(9, 6) = 84.

from math import comb
from itertools import product

r, n = 10, 4
brute = sum(1 for xs in product(range(r + 1), repeat=n) if sum(xs) == r)
print("brute force:", brute, " formula C(n+r-1, r):", comb(n + r - 1, r))

brute force: 286  formula C(n+r-1, r): 286

#Inclusion–exclusion

When sets overlap, adding their sizes counts the overlaps more than once. Correct for it:

|A ∪ B| = |A| + |B| − |A ∩ B|

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

In general: add the single sets, subtract all pairwise intersections, add all triple intersections, and so on with alternating signs.

#Example: divisibility

How many integers from 1 to 1000 are divisible by 2, 3 or 5?

N = 1000
direct = sum(1 for n in range(1, N + 1) if n % 2 == 0 or n % 3 == 0 or n % 5 == 0)
formula = (N//2 + N//3 + N//5) - (N//6 + N//10 + N//15) + N//30
print("count directly:", direct, " inclusion-exclusion:", formula)
print("not divisible by 2, 3 or 5:", N - formula)

count directly: 734  inclusion-exclusion: 734
not divisible by 2, 3 or 5: 266

#Derangements

A derangement is a permutation where no element stays in its original position — n letters put into n envelopes so that every letter is in the wrong one. By inclusion–exclusion:

Dₙ = n! (1 − 1/1! + 1/2! − 1/3! + … + (−1)ⁿ/n!)

from math import factorial
from itertools import permutations

def derangements(n):
    return round(factorial(n) * sum((-1) ** k / factorial(k) for k in range(n + 1)))

for n in range(1, 8):
    brute = sum(1 for p in permutations(range(n)) if all(p[i] != i for i in range(n)))
    print(f"D{n} = {derangements(n)} (brute force {brute}), fraction {derangements(n) / factorial(n):.4f}")

D1 = 0 (brute force 0), fraction 0.0000
D2 = 1 (brute force 1), fraction 0.5000
D3 = 2 (brute force 2), fraction 0.3333
D4 = 9 (brute force 9), fraction 0.3750
D5 = 44 (brute force 44), fraction 0.3667
D6 = 265 (brute force 265), fraction 0.3681
D7 = 1854 (brute force 1854), fraction 0.3679

The fraction of permutations that are derangements approaches 1/e ≈ 0.3679.

#The binomial theorem

(x + y)ⁿ = Σₖ₌₀ⁿ C(n, k) xⁿ⁻ᵏ yᵏ

The coefficients C(n, k) are the binomial coefficients — the rows of Pascal's triangle, where each entry is the sum of the two above it.

from math import comb

for n in range(7):
    print(" " * (2 * (6 - n)) + "".join(f"{comb(n, k):4}" for k in range(n + 1)))

n = 4
terms = [f"{comb(n, k)}x^{n-k}y^{k}" for k in range(n + 1)]
print("(x + y)^4 =", " + ".join(terms))

               1
             1   1
           1   2   1
         1   3   3   1
       1   4   6   4   1
     1   5  10  10   5   1
   1   6  15  20  15   6   1
(x + y)^4 = 1x^4y^0 + 4x^3y^1 + 6x^2y^2 + 4x^1y^3 + 1x^0y^4

Consequences:

• Setting x = y = 1: Σ C(n, k) = 2ⁿ (the number of subsets).
• Setting x = 1, y = −1: Σ (−1)ᵏ C(n, k) = 0.
• The coefficient of x³y⁵ in (x + y)⁸ is C(8, 5) = 56.
• The coefficient of x⁴ in (2x − 3)⁶ is C(6, 2) · 2⁴ · (−3)² = 15 · 16 · 9 = 2160.

A recurrence relation defines each term of a sequence using earlier terms, together with initial conditions.

• aₙ = aₙ₋₁ + 3, a₀ = 2 → 2, 5, 8, 11, … (arithmetic)
• aₙ = 2aₙ₋₁, a₀ = 1 → 1, 2, 4, 8, … (geometric)
• Fₙ = Fₙ₋₁ + Fₙ₋₂, F₀ = 0, F₁ = 1 → Fibonacci

#Modelling with recurrences

#Linear homogeneous recurrences with constant coefficients

Form: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + … + cₖaₙ₋ₖ.

Method for degree 2 (aₙ = c₁aₙ₋₁ + c₂aₙ₋₂):

1. Write the characteristic equation: r² − c₁r − c₂ = 0.
2. Find its roots.
   • Distinct roots r₁, r₂: aₙ = α·r₁ⁿ + β·r₂ⁿ.
   • Repeated root r: aₙ = (α + βn)·rⁿ.
3. Use the initial conditions to find α and β.

#Example 1: distinct roots

aₙ = aₙ₋₁ + 2aₙ₋₂, a₀ = 2, a₁ = 7.

Characteristic equation r² − r − 2 = 0 → (r − 2)(r + 1) = 0 → r = 2, −1. So aₙ = α·2ⁿ + β(−1)ⁿ.

a₀: α + β = 2. a₁: 2α − β = 7. Adding: 3α = 9 → α = 3, β = −1.

aₙ = 3·2ⁿ − (−1)ⁿ.

#Example 2: repeated root

aₙ = 6aₙ₋₁ − 9aₙ₋₂, a₀ = 1, a₁ = 6.

r² − 6r + 9 = 0 → (r − 3)² = 0 → r = 3 (double). So aₙ = (α + βn)3ⁿ.

a₀ = α = 1. a₁ = (1 + β)·3 = 6 → β = 1. aₙ = (1 + n)·3ⁿ.

#Example 3: Fibonacci (Binet's formula)

r² − r − 1 = 0 → r = (1 ± √5)/2. With F₀ = 0, F₁ = 1:

Fₙ = (φⁿ − ψⁿ)/√5, where φ = (1 + √5)/2 ≈ 1.618 and ψ = (1 − √5)/2

So Fibonacci numbers grow like φⁿ — which is why naive recursive Fibonacci is exponential.

from math import sqrt

def by_recurrence(n, a0, a1, c1, c2):
    a, b = a0, a1
    for _ in range(n):
        a, b = b, c1 * b + c2 * a
    return a

phi, psi = (1 + sqrt(5)) / 2, (1 - sqrt(5)) / 2
print("n   rec1  3*2^n-(-1)^n   rec2  (1+n)3^n   fib  Binet")
for n in range(8):
    r1 = by_recurrence(n, 2, 7, 1, 2)
    r2 = by_recurrence(n, 1, 6, 6, -9)
    f = by_recurrence(n, 0, 1, 1, 1)
    print(f"{n:<3} {r1:<5} {3 * 2**n - (-1)**n:<13} {r2:<5} {(1 + n) * 3**n:<9} {f:<4} {round((phi**n - psi**n) / sqrt(5))}")

n   rec1  3*2^n-(-1)^n   rec2  (1+n)3^n   fib  Binet
0   2     2             1     1         0    0
1   7     7             6     6         1    1
2   11    11            27    27        1    1
3   25    25            108   108       2    2
4   47    47            405   405       3    3
5   97    97            1458  1458      5    5
6   191   191           5103  5103      8    8
7   385   385           17496 17496     13   13

#Non-homogeneous recurrences

For aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + F(n), the solution is (homogeneous solution) + (one particular solution). For Tower of Hanoi, Hₙ = 2Hₙ₋₁ + 1 has homogeneous part α·2ⁿ and particular solution −1; with H₁ = 1, Hₙ = 2ⁿ − 1.

#Divide-and-conquer recurrences

Recurrences like T(n) = aT(n/b) + f(n) come from recursive algorithms. They are solved with the Master Theorem — see Solving Recurrences in Algorithms.

A graph G = (V, E) has a set of vertices V and a set of edges E, each joining two vertices. Graph theory began in 1736 when Leonhard Euler proved that nobody could walk across all seven bridges of Königsberg exactly once.

#Kinds of graphs

#Degree and the handshake lemma

The degree deg(v) is the number of edges at v (a loop counts twice). In every undirected graph:

Σ deg(v) = 2|E|

So the number of odd-degree vertices is always even. In a directed graph, Σ in-degree = Σ out-degree = |E|.

#Special graphs

A graph is bipartite if and only if it has no odd-length cycle — checkable by 2-colouring with BFS.

#Isomorphism

Two graphs are isomorphic if there is a bijection between their vertices that preserves adjacency — they are the same graph drawn differently. Isomorphic graphs share every invariant: number of vertices and edges, degree sequence, number of cycles of each length, connectedness. Different invariants prove two graphs are not isomorphic; equal invariants do not prove that they are.

#Paths, circuits and connectivity

• A path is a sequence of edges from one vertex to another; a circuit (cycle) returns to its start.
• A graph is connected if every pair of vertices has a path between them.
• A cut vertex (articulation point) or bridge is a vertex or edge whose removal disconnects the graph.

#Euler paths and circuits

An Euler circuit uses every edge exactly once and returns to the start; an Euler path uses every edge once without returning.

A connected graph has an Euler circuit iff every vertex has even degree. It has an Euler path (but no circuit) iff it has exactly two odd-degree vertices — the path starts at one and ends at the other.

Königsberg had four land masses with degrees 5, 3, 3, 3 — four odd vertices, so no Euler path exists.

from collections import Counter

def euler_status(edges):
    deg = Counter()
    for u, v in edges:
        deg[u] += 1
        deg[v] += 1
    odd = [v for v in deg if deg[v] % 2]
    if not odd:
        return "Euler circuit exists"
    if len(odd) == 2:
        return f"Euler path from {odd[0]} to {odd[1]}"
    return f"neither ({len(odd)} odd vertices)"

konigsberg = [("A","B"), ("A","B"), ("A","C"), ("A","C"), ("A","D"), ("B","D"), ("C","D")]
house = [(1,2), (2,3), (3,4), (4,1), (1,5), (2,5), (1,3), (2,4)]
square = [(1,2), (2,3), (3,4), (4,1)]
for name, g in [("Konigsberg", konigsberg), ("envelope house", house), ("square", square)]:
    print(f"{name:15} {euler_status(g)}")

Konigsberg      neither (4 odd vertices)
envelope house  Euler path from 3 to 4
square          Euler circuit exists

#Hamilton paths and circuits

A Hamilton circuit visits every vertex exactly once and returns to the start. Unlike the Euler case, no simple test is known — deciding whether one exists is NP-complete. Sufficient conditions exist: Dirac's theorem says a simple graph with n ≥ 3 vertices where every vertex has degree ≥ n/2 has a Hamilton circuit.

#Planar graphs

A graph is planar if it can be drawn without edges crossing. For a connected planar graph, Euler's formula holds:

V − E + F = 2 (F = number of faces, including the outer one)

Consequence: a connected simple planar graph with V ≥ 3 has E ≤ 3V − 6. K₅ has E = 10 > 3·5 − 6 = 9, so K₅ is not planar. By Kuratowski's theorem, a graph is planar iff it contains no subdivision of K₅ or K₃,₃.

#Graph colouring

A proper colouring gives adjacent vertices different colours; the minimum number of colours is the chromatic number χ(G).

• χ(Kₙ) = n; χ(Cₙ) = 2 if n is even, 3 if odd; χ of a bipartite graph = 2.
• Four colour theorem (1976, proved with a computer): every planar graph has χ ≤ 4.
• Applications: exam timetabling (subjects sharing a student cannot share a slot), register allocation in compilers, frequency assignment.

A tree is a connected, acyclic undirected graph. Trees are the most important graphs in computer science: file systems, parse trees, decision trees, search trees, heaps, tries.

#Equivalent characterisations

For a graph T with n vertices, these are all equivalent — any one of them makes T a tree:

1. T is connected and has no cycles.
2. There is a unique simple path between every pair of vertices.
3. T is connected and has exactly n − 1 edges.
4. T has no cycles and has exactly n − 1 edges.
5. T is connected, but removing any edge disconnects it (every edge is a bridge).
6. T has no cycles, but adding any edge creates exactly one cycle.

A graph with no cycles that may be disconnected is a forest — a collection of trees. A forest with n vertices and c components has n − c edges.

#Rooted and m-ary trees

Choosing one vertex as the root gives every edge a direction away from it, with the usual parent, child, leaf, level and height terms (see Trees & Binary Trees in Data Structures).

An m-ary tree gives each internal vertex at most m children; a full m-ary tree gives each internal vertex exactly m children.

An m-ary tree of height h has at most mʰ leaves, so a tree with l leaves has height at least ⌈log_m l⌉.

def full_mary(m, internal):
    n = m * internal + 1
    leaves = (m - 1) * internal + 1
    return n, leaves

# A knockout chess tournament: each match (internal vertex) has 2 players (children)
players = 64
matches = (players - 1) // (2 - 1)
print(f"{players} players need {matches} matches")
print("full ternary tree with 10 internal vertices (vertices, leaves):", full_mary(3, 10))

# Chain letter: each person sends to 4 others; 100 people never send (leaves)
m, l = 4, 100
print(f"people involved: {(m * l - 1) // (m - 1)}, senders: {(l - 1) // (m - 1)}")

64 players need 63 matches
full ternary tree with 10 internal vertices (vertices, leaves): (31, 21)
people involved: 133, senders: 33

#Spanning trees

A spanning tree of a connected graph G is a subgraph that is a tree and includes every vertex of G. Every connected graph has one (delete cycle edges until none are left); BFS and DFS each produce one. With weights, the cheapest is the minimum spanning tree — Kruskal and Prim.

Cayley's formula: the complete graph Kₙ has nⁿ⁻² different spanning trees (equivalently, there are nⁿ⁻² labelled trees on n vertices). K₄ has 4² = 16.

from itertools import combinations

def is_tree(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return False          # a cycle
        parent[ru] = rv
    return len(edges) == n - 1    # n - 1 edges and no cycle: connected tree

for n in range(2, 6):
    all_edges = list(combinations(range(n), 2))
    count = sum(1 for es in combinations(all_edges, n - 1) if is_tree(n, es))
    print(f"K{n}: {count} spanning trees, Cayley n^(n-2) = {n ** (n - 2)}")

K2: 1 spanning trees, Cayley n^(n-2) = 1
K3: 3 spanning trees, Cayley n^(n-2) = 3
K4: 16 spanning trees, Cayley n^(n-2) = 16
K5: 125 spanning trees, Cayley n^(n-2) = 125

#Prefix codes and decision trees

• Binary trees whose leaves are symbols give prefix codes — the basis of Huffman coding.
• A decision tree for sorting n items has n! leaves, so its height (worst-case comparisons) is at least log₂(n!) = Ω(n log n) — the proof that comparison sorting cannot beat O(n log n).

Number theory studies the integers. Once called the "purest" mathematics, it now secures every HTTPS connection and UPI payment through cryptography.

#Divisibility

a divides b (written a | b) if b = a·k for some integer k. Examples: 3 | 12, 7 ∤ 12.

Division algorithm: for integers a and d > 0, there are unique q and r with a = d·q + r and 0 ≤ r < d. Here q = a div d and r = a mod d.

#Primes

A prime is an integer p > 1 whose only positive divisors are 1 and p. Every integer > 1 is either prime or composite.

Fundamental theorem of arithmetic: every integer > 1 can be written as a product of primes in exactly one way (up to order): 360 = 2³ · 3² · 5.

There are infinitely many primes (Euclid's proof is in the proofs lesson). To test n, try divisors up to √n; to list all primes up to n, use the Sieve of Eratosthenes:

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):   # cross off multiples of p
                is_prime[multiple] = False
    return [i for i, ok in enumerate(is_prime) if ok]

def factorise(n):
    factors, d = {}, 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

print(sieve(60))
for n in (360, 1001, 97, 2026):
    print(n, "=", " · ".join(f"{p}^{e}" if e > 1 else str(p) for p, e in factorise(n).items()))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
360 = 2^3 · 3^2 · 5
1001 = 7 · 11 · 13
97 = 97
2026 = 2 · 1013

#GCD and LCM

• gcd(a, b): the largest integer dividing both. gcd(84, 36) = 12.
• lcm(a, b): the smallest positive integer divisible by both. lcm(4, 6) = 12.
• gcd(a, b) · lcm(a, b) = a · b.
• a and b are coprime (relatively prime) if gcd(a, b) = 1.

Euclid's algorithm: gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = a. It takes O(log min(a, b)) steps.

Bézout's identity: there exist integers s, t with gcd(a, b) = s·a + t·b. The extended Euclidean algorithm finds them.

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, s, t = extended_gcd(b, a % b)
    return g, t, s - (a // b) * t

a, b = 252, 198
x, y = a, b
while y:
    print(f"gcd({x}, {y})", end=" = ")
    x, y = y, x % y
print(f"gcd({x}, 0) = {x}")
g, s, t = extended_gcd(a, b)
print(f"Bezout: {g} = {s}*{a} + {t}*{b}")
print("lcm =", a * b // g)

gcd(252, 198) = gcd(198, 54) = gcd(54, 36) = gcd(36, 18) = gcd(18, 0) = 18
Bezout: 18 = 4*252 + -5*198
lcm = 2772

#Modular arithmetic

a ≡ b (mod m) — "a is congruent to b modulo m" — means m | (a − b): a and b leave the same remainder when divided by m. Clock arithmetic is mod 12; days of the week are mod 7.

Congruences can be added and multiplied: if a ≡ b and c ≡ d (mod m), then a + c ≡ b + d and a·c ≡ b·d (mod m). So you can reduce at every step:

(a + b) mod m = ((a mod m) + (b mod m)) mod m (a · b) mod m = ((a mod m) · (b mod m)) mod m

#Fast modular exponentiation

Compute aᵉ mod m by repeated squaring in O(log e) multiplications:

def mod_pow(a, e, m):
    result = 1
    a %= m
    while e > 0:
        if e & 1:                 # this bit of the exponent is set
            result = result * a % m
        a = a * a % m             # square for the next bit
        e >>= 1
    return result

print(mod_pow(3, 200, 13), pow(3, 200, 13))          # Python's pow does the same
print("last 3 digits of 7^2026:", mod_pow(7, 2026, 1000))
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
print("100 days after a Saturday is a", days[(days.index("Sat") + 100) % 7])

9 9
last 3 digits of 7^2026: 649
100 days after a Saturday is a Mon

#Modular inverses

The inverse of a modulo m is a number a⁻¹ with a·a⁻¹ ≡ 1 (mod m). It exists iff gcd(a, m) = 1, and the extended Euclidean algorithm finds it. Example: 3⁻¹ mod 7 = 5, since 3·5 = 15 ≡ 1.

Fermat's little theorem: if p is prime and p ∤ a, then aᵖ⁻¹ ≡ 1 (mod p). So a⁻¹ ≡ aᵖ⁻² (mod p).

#Applications

p, q = 61, 53                      # toy RSA (real keys use primes with hundreds of digits)
n, phi = p * q, (p - 1) * (q - 1)
e = 17                             # public exponent, coprime with phi
d = pow(e, -1, phi)                # private exponent: modular inverse (Python 3.8+)
message = 65
cipher = pow(message, e, n)
print(f"n={n}, e={e}, d={d}")
print(f"encrypt {message} -> {cipher}, decrypt -> {pow(cipher, d, n)}")

n=3233, e=17, d=2753
encrypt 65 -> 2790, decrypt -> 65

Boolean algebra works with two values, 0 and 1, and three operations:

It is propositional logic in algebraic dress (T = 1, F = 0) and set algebra in disguise (∪ = +, ∩ = ·). George Boole introduced it in 1854; Claude Shannon showed in 1937 that it describes switching circuits — the birth of digital electronics.

#Laws

Duality: swap + with ·, and 0 with 1, in any identity and you get another valid identity. That is why the laws come in pairs.

#Boolean functions and normal forms

A Boolean function of n variables maps each of the 2ⁿ input combinations to 0 or 1. There are 2^(2ⁿ) such functions.

• Sum of products (SOP / DNF): OR together a minterm (an AND of all variables, complemented where 0) for every row where f = 1.
• Product of sums (POS / CNF): AND together a maxterm for every row where f = 0.

Example: the majority function of three inputs (1 when at least two inputs are 1):

SOP: f = x′yz + xy′z + xyz′ + xyz, which simplifies to f = xy + yz + xz.

#Logic gates

NAND and NOR are each functionally complete: any Boolean function can be built from NAND gates alone. For example, x′ = (x·x)′ and x·y = ((x·y)′)′.

#Simplifying with Karnaugh maps

A Karnaugh map (K-map) arranges a function's truth table in a grid whose rows and columns are in Gray code order (00, 01, 11, 10), so neighbouring cells differ in exactly one variable. To simplify:

1. Write a 1 in each cell where f = 1.
2. Circle rectangular groups of 1, 2, 4 or 8 adjacent 1s (groups may wrap around the edges), as large as possible.
3. Each group becomes one product term: keep only the variables that do not change within the group.
4. OR the terms together.

For the majority function (rows x, columns yz):

Three overlapping pairs give yz (column 11), xz (cells 101, 111) and xy (cells 111, 110): f = xy + yz + xz.

Verify any simplification by comparing truth tables:

from itertools import product

def majority_sop(x, y, z):
    return (not x and y and z) or (x and not y and z) or (x and y and not z) or (x and y and z)

def majority_simple(x, y, z):
    return (x and y) or (y and z) or (x and z)

same = all(bool(majority_sop(*v)) == bool(majority_simple(*v)) for v in product([0, 1], repeat=3))
print("simplified circuit matches:", same)

def nand(a, b): return int(not (a and b))
def xor_from_nand(a, b):
    m = nand(a, b)
    return nand(nand(a, m), nand(b, m))      # XOR built from four NAND gates
print("XOR from NANDs:", [xor_from_nand(a, b) for a, b in product([0, 1], repeat=2)])

simplified circuit matches: True
XOR from NANDs: [0, 1, 1, 0]

#Half adder

Adding two bits produces a sum bit S = x ⊕ y and a carry bit C = x · y — one XOR gate and one AND gate. Chaining full adders gives the circuits that add numbers inside every CPU (see Logic Gates in Foundations).

#Logic

#Proof methods

Direct · contrapositive · contradiction · cases · counterexample · induction (base + step) · strong induction.

#Sets and functions

#Relations

#Counting

#Recurrences

#Graphs and trees

#Number theory

#Boolean algebra