Discrete Mathematics: cram pack

Logical equivalence: two formulas are equivalent (≡) when they have the same value in every row of the truth table. A tautology is 1 in every row, a contradiction is 0 in every row, and a contingency is neither. Useful laws: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b and ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contrapositive); ¬(a → b) ≡ a ∧ ¬b; and the distributive laws, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

Quantifiers and arguments: ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x). Move a negation inwards, swap every quantifier it passes, and negate the inner formula with the propositional laws, such as ¬(a → b) ≡ a ∧ ¬b. An argument is valid when the conclusion is 1 in every row in which all premises are 1. A single row with true premises and a false conclusion is a counterexample and shows the argument is invalid.

Relations: a relation R on a set X is a set of ordered pairs (x, y). R is reflexive when (x, x) ∈ R for every x in X; symmetric when (x, y) ∈ R always comes with (y, x) ∈ R; antisymmetric when (x, y) and (y, x) are both in R only if x = y; and transitive when (x, y) and (y, z) in R force (x, z) ∈ R. An equivalence relation is reflexive, symmetric and transitive, and splits X into disjoint classes.

Relations: a relation R on a set X is a set of ordered pairs (x, y). R is reflexive when (x, x) ∈ R for every x in X; symmetric when (x, y) ∈ R always comes with (y, x) ∈ R; antisymmetric when (x, y) and (y, x) are both in R only if x = y; and transitive when (x, y) and (y, z) in R force (x, z) ∈ R. An equivalence relation is reflexive, symmetric and transitive, and splits X into disjoint classes.

Euler, Hamilton and trees: a connected graph has an Euler circuit (every edge once, back to the start) when every vertex has even degree, and an Euler path that is not a circuit when exactly two vertices have odd degree; the path then runs from one odd vertex to the other. A Hamilton circuit visits every vertex once; K_n has (n − 1)!/2 of them. A tree on n vertices has n − 1 edges, and a connected graph with m edges keeps a spanning tree after removing m − n + 1 edges.

Shortest paths and spanning trees: Dijkstra’s algorithm settles one vertex per round: the unsettled vertex with the smallest tentative distance. Its distance is then final, and every neighbour v gets d(v) = min(d(v), d(u) + w(u, v)). Kruskal’s algorithm builds a minimum spanning tree by taking the edges from light to heavy and skipping any edge that would close a cycle; Prim’s algorithm grows one tree from a start vertex by always adding the lightest edge that leaves it. A spanning tree of n vertices has n − 1 edges.

Inverses and congruences: a has an inverse modulo n exactly when gcd(a, n) = 1. The extended Euclidean algorithm writes 1 = s·n + t·a, and then a⁻¹ ≡ t (mod n). A congruence a·x ≡ b (mod n) with gcd(a, n) = 1 has the solution x ≡ a⁻¹·b. Two congruences x ≡ r₁ (mod m₁) and x ≡ r₂ (mod m₂) with coprime moduli have one solution modulo m₁·m₂ (Chinese remainder theorem). Euler’s φ(n) counts the numbers from 1 to n that are coprime to n: φ(n) = n·∏(1 − 1/p).

Modular powers and RSA: compute aᵏ mod n by repeated squaring: write k in binary, square, reduce after every step and multiply the powers whose bit is 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) for a prime p not dividing a, so the exponent can be reduced modulo p − 1. RSA: choose primes p and q, n = p·q and φ(n) = (p − 1)(q − 1); the public exponent e is coprime to φ(n), and the private exponent is d = e⁻¹ mod φ(n). Encrypt with c = mᵉ mod n and decrypt with m = cᵈ mod n.