Discrete Mathematics for CS

Discrete Mathematics for Computer Science

Discrete mathematics is the study of mathematical structures that are fundamentally countable rather than continuous. Unlike calculus, which operates on real numbers and infinite limits, discrete math deals with integers, graphs, sets, and logical statements — precisely the structures that computers manipulate.

Logic and Proof

Propositional logic forms the foundation of digital circuits and program verification. A proposition is any statement with a definite truth value. Logical connectives combine propositions: AND (∧), OR (∨), NOT (¬), implication (p → q means "if p then q"), and biconditional (p ↔ q means "p if and only if q").

A tautology is a formula true under all assignments (e.g., p ∨ ¬p). A contradiction is always false (p ∧ ¬p). These concepts underlie SAT solvers used in chip verification, formal methods, and AI planning.

Predicate logic extends propositional logic with quantifiers: ∀ (for all) and ∃ (there exists). "Every user has a password" is ∀u ∃p Holds(u, p). Predicate logic is the basis for SQL semantics, Prolog, and type theory.

Proof techniques are the machinery of mathematical reasoning:

• Direct proof: assume the hypothesis, derive the conclusion through logical steps
• Proof by contrapositive: prove ¬Q → ¬P to establish P → Q (logically equivalent)
• Proof by contradiction: assume ¬P, derive a contradiction, conclude P
• Mathematical induction: prove a base case, then prove that if it holds for n it holds for n+1

Set Theory

A set is an unordered collection of distinct elements. Operations: union (A ∪ B), intersection (A ∩ B), difference (A − B), complement (Ā), and Cartesian product (A × B = all ordered pairs from A and B).

Power set P(S) is the set of all subsets of S. If |S| = n, then |P(S)| = 2ⁿ. This exponential growth explains why exhaustive search over subsets is intractable for large n.

Relations are subsets of Cartesian products. A relation R on set A is:

• Reflexive: ∀a, aRa
• Symmetric: aRb → bRa
• Transitive: aRb ∧ bRc → aRc
• An equivalence relation is all three — it partitions a set into equivalence classes (think: grouping users by role).
• A partial order is reflexive, antisymmetric, and transitive (think: topological ordering of dependencies).

Functions are special relations mapping each input to exactly one output. A function is injective (one-to-one) if distinct inputs map to distinct outputs; surjective (onto) if every output is reached; bijective if both. Bijections are used in cryptographic key generation and hash function design.

Combinatorics

Counting is fundamental to algorithm analysis and probability. The multiplication principle: if task A can be done in m ways and task B in n ways, they can be done in sequence in m·n ways.

Permutations: number of ways to arrange n distinct objects = n! Number of k-item arrangements from n objects = n!/(n−k)!

Combinations: C(n,k) = n! / (k!(n−k)!) — number of ways to choose k items from n without regard to order. C(10,3) = 120 ways to pick 3 features from 10.

Pigeonhole Principle: if n+1 items are placed in n containers, at least one container has ≥ 2 items. This proves the existence of hash collisions: mapping more keys than buckets guarantees at least one collision.

Graph Theory

A graph G = (V, E) consists of vertices V and edges E. Degree of a vertex = number of incident edges. The sum of all degrees = 2|E| (each edge contributes to two vertices).

Paths and cycles: a path visits vertices without repetition; a cycle returns to its start. A graph is connected if a path exists between every pair of vertices.

Trees are connected acyclic graphs. A tree with n vertices has exactly n−1 edges. Every tree has at least two leaf nodes (degree 1). Spanning trees connect all vertices with minimal edges — the basis for network routing protocols.

Planar graphs can be drawn without edge crossings. Euler's formula: V − E + F = 2 for connected planar graphs (F = faces including the outer face). This proves that K₅ and K₃,₃ are non-planar — relevant in VLSI circuit design where crossing wires require additional layers.

Graph coloring: assign colors to vertices so no adjacent vertices share a color. The chromatic number χ(G) is the minimum colors needed. The four color theorem states any planar map needs at most 4 colors. Graph coloring models register allocation in compilers: variables are vertices, edges connect variables live simultaneously, colors represent registers.

Recurrence Relations

Many algorithms' runtime satisfies a recurrence. Merge sort: T(n) = 2T(n/2) + cn. The Master Theorem solves T(n) = aT(n/b) + f(n) for divide-and-conquer algorithms, yielding the complexity without unrolling the recursion manually.

Fibonacci numbers satisfy F(n) = F(n-1) + F(n-2) — an additive recurrence. The closed form (Binet's formula) expresses Fibonacci in terms of the golden ratio φ, demonstrating how combinatorics and algebra interlock.