Why Discrete Math for CS?
Discrete mathematics studies structures that are fundamentally countable — integers, graphs, logic — as opposed to continuous mathematics (calculus, real analysis). It's the mathematical foundation of computer science: logic underlies programming languages, graph theory underlies networks and algorithms, combinatorics appears in complexity analysis and probability, and proof techniques are used in algorithm correctness and cryptography.
Logic and Propositions
A proposition is a statement that is either true (T) or false (F). Logical operators combine propositions into compound statements.
| Operator | Symbol | True when |
|---|---|---|
| AND (conjunction) | p ∧ q | Both p and q are true |
| OR (disjunction) | p ∨ q | At least one of p, q is true |
| NOT (negation) | ¬p | p is false |
| IMPLIES (implication) | p → q | p is false, OR q is true (false only when p=T and q=F) |
| IFF (biconditional) | p ↔ q | p and q have the same truth value |
| XOR (exclusive or) | p ⊕ q | Exactly one of p, q is true |
A tautology is a formula that is always true (e.g., p ∨ ¬p). A contradiction is always false (e.g., p ∧ ¬p). Key laws: De Morgan's: ¬(p ∧ q) = ¬p ∨ ¬q and ¬(p ∨ q) = ¬p ∧ ¬q.
Set Theory
A set is an unordered collection of distinct elements. Sets are the foundation of modern mathematics and appear everywhere in CS — type systems, database theory, language semantics.
| Operation | Symbol | Meaning |
|---|---|---|
| Union | A ∪ B | All elements in A or B (or both) |
| Intersection | A ∩ B | Elements in both A and B |
| Difference | A − B | Elements in A but not in B |
| Complement | A' | Elements not in A (relative to universal set) |
| Subset | A ⊆ B | Every element of A is in B |
| Power set | P(A) | Set of all subsets of A; |P(A)| = 2^|A| |
| Cartesian product | A × B | All ordered pairs (a, b) where a ∈ A, b ∈ B |
Inclusion-Exclusion Principle
|A ∪ B| = |A| + |B| − |A ∩ B|. Extends to three sets: |A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. Used to count "at least one" conditions by avoiding double-counting overlaps.
Relations and Functions
A relation R from set A to set B is a subset of A × B. Key properties of relations on a set A: reflexive (a R a for all a), symmetric (a R b implies b R a), transitive (a R b and b R c implies a R c). A relation that is all three is an equivalence relation (partitions A into equivalence classes).
A function f: A → B maps each element of A to exactly one element of B. Injective (one-to-one): different inputs give different outputs. Surjective (onto): every output has at least one input. Bijective: both — a perfect pairing. Bijections enable counting and cryptography.
Combinatorics
Combinatorics counts arrangements and selections. It's essential for algorithm analysis (how many operations?), probability, and cryptography (how many keys are possible?).
| Concept | Formula | When to use |
|---|---|---|
| Permutation | P(n,r) = n!/(n−r)! | Ordered arrangements of r items from n (order matters) |
| Combination | C(n,r) = n! / (r!(n−r)!) | Unordered selections of r items from n (order doesn't matter) |
| Multiplication Rule | |A| × |B| | Independent sequential choices (first do A, then B) |
| Binomial Theorem | (x+y)ⁿ = Σ C(n,k) xᵏ yⁿ⁻ᵏ | Expanding binomials; Pascal's triangle gives C(n,k) |
| Pigeonhole Principle | n items in k boxes → ≥1 box has ≥⌈n/k⌉ | Proving collisions exist (hash functions, birthday paradox) |
// Examples:
// How many 3-letter passwords from 26 letters (no repeat)? P(26,3) = 26×25×24 = 15,600
// How many ways to choose a 5-card hand from 52? C(52,5) = 2,598,960
// Birthday paradox: how many people needed for >50% chance two share a birthday?
// ~23 people — probability ≈ 1 − (365/365)(364/365)...(343/365) ≈ 0.507Graph Theory
A graph G = (V, E) is a set of vertices V and edges E. Graphs model networks, dependencies, social connections — anything with relationships between entities.
| Term | Definition |
|---|---|
| Degree | Number of edges incident to a vertex; handshaking lemma: Σ degrees = 2|E| |
| Path | Sequence of vertices where each consecutive pair is connected by an edge |
| Cycle | A path that starts and ends at the same vertex |
| Connected | Every vertex is reachable from every other vertex |
| Tree | Connected graph with no cycles; always has exactly |V| − 1 edges |
| Bipartite | Vertices can be divided into two disjoint sets with no edges within a set |
| Planar | Can be drawn without crossing edges; Euler's formula: V − E + F = 2 |
Proof Techniques
Direct Proof
Assume hypothesis, derive conclusion step by step. Example: prove "if n is even, n² is even."
Let n be even → n = 2k for some integer k.
n² = (2k)² = 4k² = 2(2k²).
Since 2k² is an integer, n² = 2·(integer) → n² is even. □Proof by Contradiction
Assume the opposite of what you want to prove, derive a contradiction.
// √2 is irrational:
Assume √2 = p/q (fully reduced, p,q integers, gcd(p,q) = 1).
Then 2 = p²/q² → p² = 2q² → p² is even → p is even → p = 2k.
Then (2k)² = 2q² → 4k² = 2q² → q² = 2k² → q is even.
But p and q both even contradicts gcd(p,q) = 1. ⊥ → √2 is irrational. □Mathematical Induction
Prove for base case, then prove if true for n it's true for n+1.
// Prove 1 + 2 + ... + n = n(n+1)/2
Base case (n=1): 1 = 1·2/2 = 1. ✓
Inductive step: Assume true for n (i.e., sum = n(n+1)/2).
Prove for n+1:
1+2+...+n+(n+1) = n(n+1)/2 + (n+1)
= (n+1)[n/2 + 1]
= (n+1)(n+2)/2 ← this is (n+1)((n+1)+1)/2. ✓ □Key Takeaways
- Logic operators (AND, OR, NOT, IMPLIES) map directly to programming:
&&,||,!. De Morgan's law is used constantly in code simplification. - Sets appear everywhere — database relational algebra is set algebra.
- Counting techniques determine algorithm complexity: C(n,2) = O(n²) explains why nested loops are quadratic.
- Pigeonhole principle: with n+1 inputs into n buckets (hash slots, categories), at least one collision is guaranteed.
- Graph theory is the backbone of algorithm problems — almost every hard problem is a graph problem in disguise.
- Induction is how you prove algorithms correct on all inputs — prove base case, prove the step.