Short notes: Discrete Mathematics
Every topic in revision form: the key ideas, formulas, the question types GATE asks, and the traps. Read it the night before.
Almost every paper has a logic question: is a formula valid, which statement is equivalent, which quantifier translation is right, or how many Boolean functions exist.
- Propositions, connectives and truth tables. A proposition is a statement that is true or false. Connectives: ¬, ∧, ∨, →, ↔, ⊕. p → q is false only when p is true and q is false; it is true whenever p is false. p ↔ q is true when both agree. A formula with n variables has 2ⁿ rows. Precedence (high to low): ¬, ∧, ∨, →, ↔; → is right associative.→ p → q is false only for T, F. An n-variable formula has 2ⁿ rows.
- Equivalences and the standard laws. Two formulas are equivalent if they have the same truth table, i.e. p ↔ q is a tautology. Core laws: De Morgan ¬(p∧q) ≡ ¬p∨¬q; implication p→q ≡ ¬p∨q; contrapositive p→q ≡ ¬q→¬p; ¬(p→q) ≡ p∧¬q; p↔q ≡ (p→q)∧(q→p); distribution of ∧ over ∨ and ∨ over ∧. The converse q→p and inverse ¬p→¬q are NOT equivalent to p→q.→ Only the contrapositive is equivalent to p → q; the converse and inverse are not.
- Normal forms, tautology and satisfiability. A formula is a tautology (valid) if true in every row, a contradiction if true in none, satisfiable if true in at least one. DNF = OR of ANDs (one minterm per true row); CNF = AND of ORs (one maxterm per false row). SAT is NP-complete, but 2-SAT is in P. There are 2^(2ⁿ) Boolean functions of n variables. {∧,¬}, {∨,¬}, {→,¬}, {NAND} and {NOR} are functionally complete; {∧,∨} is not.→ n variables: 2ⁿ rows, 2^(2ⁿ) functions. DNF from true rows, CNF from false rows.
- Arguments and rules of inference. An argument is valid if whenever all premises are true the conclusion is true (equivalently (P₁∧…∧Pₙ) → C is a tautology). Rules: modus ponens (p→q, p ⊢ q), modus tollens (p→q, ¬q ⊢ ¬p), hypothetical syllogism, disjunctive syllogism (p∨q, ¬p ⊢ q), resolution (p∨q, ¬p∨r ⊢ q∨r). Fallacies: affirming the consequent (p→q, q ⊢ p) and denying the antecedent (p→q, ¬p ⊢ ¬q) are invalid.→ Valid means no counter-example row. Never affirm the consequent.
- Quantifiers and first-order translation. ∀x P(x) is true if P holds for every element of the domain; ∃x P(x) if for at least one. Negation: ¬∀x P ≡ ∃x ¬P and ¬∃x P ≡ ∀x ¬P. Translating: "all A are B" is ∀x (A(x) → B(x)); "some A is B" is ∃x (A(x) ∧ B(x)). Order matters: ∃y ∀x P(x,y) ⇒ ∀x ∃y P(x,y), but not the other way round. ∀ distributes over ∧, ∃ distributes over ∨, but not vice versa.→ ∀ pairs with →, ∃ pairs with ∧. ∃∀ ⇒ ∀∃ but not back.
- Proof techniques and induction. Direct proof, contrapositive (prove ¬q → ¬p), contradiction (assume the negation and derive absurdity), and mathematical induction: prove the base case P(b), then P(k) → P(k+1) for all k ≥ b. Strong induction assumes P(b..k). A claim that holds for many cases (n² + n + 41 prime for n ≤ 39) can still be false; the base case must be right (2ⁿ > n² starts at n = 5).→ Base case, then P(k) ⇒ P(k+1). Check where the claim really starts.
Formulas
What GATE asks
- ★★★Which statement is equivalent / logically implies another?. Reduce both sides with De Morgan and p → q ≡ ¬p ∨ q, or test with a 2 or 3 variable truth table.
- ★★★Translate English to first-order logic. "All A are B" uses →, "some A is B" uses ∧. Check each option against a tiny model.
- ★★★Is the formula valid / satisfiable?. Try to make it false; if impossible it is valid. Count true rows.
- ★★★Count Boolean functions / functional completeness. 2^(2ⁿ) functions; NAND and NOR alone are complete.
- ★★★Inference: what follows from the premises. Apply the rules in order; reject affirming the consequent.
Traps
A steady 2 to 3 marks: count relations with a property, decide whether a relation is an equivalence or partial order, read a Hasse diagram or lattice, and classify functions.
- Sets and counting with sets. Operations: ∪, ∩, difference, complement, symmetric difference A Δ B = (A−B)∪(B−A). |P(A)| = 2^|A|, |A × B| = |A|·|B|. Inclusion–exclusion: |A∪B| = |A|+|B|−|A∩B|; for three sets subtract the pairs and add back the triple. Set identities (De Morgan for sets) mirror the logic laws.→ |A∪B| = |A|+|B|−|A∩B|; |P(A)| = 2ⁿ; |A×B| = |A||B|.
- Relations and their properties. A relation R on A is a subset of A×A. Reflexive: (a,a) for all a. Irreflexive: no (a,a). Symmetric: (a,b) ⇒ (b,a). Antisymmetric: (a,b) and (b,a) ⇒ a = b. Asymmetric: (a,b) ⇒ (b,a) not in R. Transitive: (a,b),(b,c) ⇒ (a,c). Symmetric and antisymmetric are not opposites: the identity is both; some relations are neither.→ Symmetric and antisymmetric are not opposites; the identity is both.
- Closures and counting relations. Reflexive closure R ∪ I; symmetric closure R ∪ Rᵀ; transitive closure R ∪ R² ∪ … ∪ Rⁿ (Warshall in O(n³)). Counting on an n-set: all 2^(n²); reflexive 2^(n²−n); symmetric 2^(n(n+1)/2); antisymmetric 2ⁿ·3^(n(n−1)/2); asymmetric 3^(n(n−1)/2); equivalence relations Bell(n).→ Symmetric: 2^(n(n+1)/2). Reflexive: 2^(n²−n). Antisymmetric: 2ⁿ·3^(n(n−1)/2).
- Equivalence relations and partitions. Equivalence = reflexive + symmetric + transitive. It splits the set into disjoint equivalence classes that cover it (a partition); every partition gives an equivalence relation. Number of classes of x ≡ y (mod k) is k. If a relation has k classes of sizes s₁..s_k it has Σ sᵢ² pairs. The number of equivalence relations on an n-set is the Bell number.→ Equivalence ⇔ partition. Pairs = Σ (class size)². Count of relations = Bell(n).
- Partial orders, Hasse diagrams and lattices. Partial order = reflexive + antisymmetric + transitive. A Hasse diagram draws only covering pairs, upward, no loops. Maximal/minimal elements may be several; greatest/least are unique if they exist. A lattice has a lub and glb for every pair. Divisor posets D_n are distributive lattices; D_n is a Boolean algebra iff n is squarefree. A chain of length k has k elements; width is the size of the largest antichain (Dilworth: = minimum number of chains covering).→ Hasse draws covers only. Lattice = every pair has lub and glb. Maximal ≠ greatest.
- Functions: one-to-one, onto, bijective. f : A → B. Injective: different inputs give different outputs. Surjective: every element of B is hit. Bijective = both. Counts with |A| = m, |B| = n: all functions nᵐ; injective n!/(n−m)!; bijective n! (m = n); surjective Σ(−1)ᵏ C(n,k)(n−k)ᵐ = n!·S(m,n). For finite sets of equal size, injective ⇔ surjective.→ Onto count: inclusion–exclusion (or n!·S(m,n)). Injective: n!/(n−m)!.
- Composition, inverse and countability. Composition (g∘f)(x) = g(f(x)) is associative, not commutative. If g∘f is injective then f is injective; if g∘f is surjective then g is surjective. f has an inverse iff it is a bijection. A set is countable if it is finite or in bijection with ℕ: ℤ, ℚ, ℕ×ℕ, finite strings over a finite alphabet are countable; the reals, P(ℕ) and the set of all languages are uncountable (Cantor).→ g∘f injective ⇒ f injective; g∘f onto ⇒ g onto. Strings are countable, languages are not.
Formulas
What GATE asks
- ★★★Count relations or functions with a given property. Use the formulas for reflexive/symmetric/antisymmetric; for onto functions use inclusion–exclusion or S(m,n).
- ★★★Is this relation an equivalence / partial order?. Test the three properties in turn; one counter-example kills it.
- ★★★Hasse diagram, lattice, lub/glb. Read covers, find minimal/maximal, check each pair has a unique lub and glb.
- ★★★Number of equivalence classes / size of a relation. Sum of squares of class sizes; or count classes of mod k.
- ★★★Injective/surjective/composition statements. Test with small counter-examples; use g∘f results.
Traps
The counting questions are the easiest marks in Discrete Maths: permutations with restrictions, distributions, pigeonhole, derangements and one recurrence or generating function per paper.
- Counting basics: permutations and combinations. Sum rule (either-or) adds, product rule (and-then) multiplies. P(n,r) = n!/(n−r)! counts ordered selections; C(n,r) = n!/(r!(n−r)!) counts unordered. C(n,r) = C(n,n−r), Pascal C(n,r) = C(n−1,r−1) + C(n−1,r), Σ C(n,r) = 2ⁿ. Arrangements of n objects with repeats: n!/(k₁!k₂!…). Circular arrangements: (n−1)!.→ Order matters: P(n,r). Order ignored: C(n,r). Repeats: divide by k!.
- Repetition and distributions (stars and bars). Strings of length r over n symbols: nʳ. Solutions of x₁+…+x_k = n with xᵢ ≥ 0: C(n+k−1, k−1); with every xᵢ ≥ 1: C(n−1, k−1). Put a lower bound on a variable by substituting xᵢ = yᵢ + bound first. Distinct balls in distinct boxes: kⁿ. Distinct balls in identical non-empty boxes: Stirling S(n,k).→ Identical objects into k boxes: C(n+k−1, k−1). Substitute away lower bounds first.
- Pigeonhole principle. If n objects go into k boxes, some box has at least ⌈n/k⌉ objects. To guarantee m in one box you need k(m−1)+1 objects. Typical uses: among 13 people two share a birth month; among any n+1 numbers two have the same remainder mod n; any set of n+1 integers from 1..2n contains two where one divides the other.→ Some box has ≥ ⌈n/k⌉. To force m you need k(m−1)+1.
- Inclusion–exclusion and derangements. Numbers ≤ N divisible by none of a set: N − Σ⌊N/aᵢ⌋ + Σ⌊N/lcm(aᵢ,aⱼ)⌋ − … . Euler φ(n) = n Π(1 − 1/p). Derangements (no element fixed): Dₙ = n! Σₖ (−1)ᵏ/k! = (n−1)(Dₙ₋₁ + Dₙ₋₂). D₁ = 0, D₂ = 1, D₃ = 2, D₄ = 9, D₅ = 44. Dₙ/n! → 1/e. Permutations with exactly k fixed points: C(n,k)·D_{n−k}.→ D₄ = 9, D₅ = 44. Inclusion–exclusion alternates signs: add singles, subtract pairs, add triples.
- Recurrence relations. Linear homogeneous with constant coefficients aₙ = c₁aₙ₋₁ + c₂aₙ₋₂: characteristic equation r² − c₁r − c₂ = 0. Distinct roots: aₙ = A r₁ⁿ + B r₂ⁿ. Repeated root: (A + Bn) rⁿ. Fit A and B to the initial values. A constant forcing term adds a particular solution. Famous ones: Fibonacci, Tower of Hanoi T(n) = 2T(n−1) + 1 = 2ⁿ − 1. Divide-and-conquer recurrences use the Master theorem.→ Characteristic roots: distinct gives A r₁ⁿ + B r₂ⁿ, repeated gives (A + Bn) rⁿ.
- Generating functions. The generating function of a₀, a₁, … is Σ aₙxⁿ. 1/(1−x) gives all 1s; (1+x)ᵐ gives C(m,n); 1/(1−x)ᵐ gives C(n+m−1,n); xᵏ/(1−x) shifts. Independent choices multiply their series; the coefficient of xᵏ is the number of ways to total k. Solving a recurrence: multiply by xⁿ, sum, solve for G(x), expand by partial fractions.→ 1/(1−x)ᵐ gives C(n+m−1,n); multiply series for independent choices.
- Catalan, Stirling and Bell numbers. Catalan Cₙ = C(2n,n)/(n+1): 1, 1, 2, 5, 14, 42, 132. It counts binary trees with n nodes, balanced parentheses, triangulations of an (n+2)-gon, and monotone paths below the diagonal. Stirling S(n,k) (second kind): partitions of an n-set into k blocks; S(n,2) = 2ⁿ⁻¹ − 1, S(n,n−1) = C(n,2). Bell Bₙ = Σ S(n,k): 1, 1, 2, 5, 15, 52.→ Catalan 1,1,2,5,14,42. Bell 1,1,2,5,15,52. Bell = sum of Stirling.
Formulas
What GATE asks
- ★★★Number of solutions / ways to distribute. Stars and bars after removing lower bounds; subtract cases that violate an upper bound by inclusion–exclusion.
- ★★★Solve or evaluate a recurrence. Characteristic equation, or unroll a few terms and spot the pattern.
- ★★★Pigeonhole: minimum number to guarantee something. Worst case: fill every box to m−1, then add one.
- ★★★Derangements / inclusion–exclusion / φ(n). Plug in the formula; known values D₄ = 9, D₅ = 44.
- ★★★Counting with restrictions (words, seating, committees). Glue items that must be together, count the gaps for items that must be apart.
Traps
Four to six marks every year: degree and handshake facts, trees, connectivity, planarity, colouring and Euler/Hamilton questions. (Shortest paths and spanning-tree algorithms are in the Algorithms subject.)
- Graph basics: degrees and the handshake lemma. A simple graph has no loops or repeated edges. Σ deg(v) = 2e, so the number of odd-degree vertices is even. K_n has n(n−1)/2 edges and is (n−1)-regular. A degree sequence is graphical if it passes Havel–Hakimi. A simple graph on n vertices has at most C(n,2) edges; a regular graph of degree r has nr/2 edges. In a directed graph Σ in-degree = Σ out-degree = e.→ Σ deg = 2e. Odd vertices come in pairs. Havel–Hakimi decides graphical sequences.
- Connectivity: components, bridges, cut vertices. A graph with n vertices and e edges has at least n − e components. A connected graph needs at least n−1 edges; a graph with more than C(n−1,2) edges must be connected. A bridge is an edge whose removal disconnects; a cut vertex likewise. Vertex connectivity κ ≤ edge connectivity λ ≤ min degree δ. A graph is 2-connected iff every pair lies on a common cycle.→ Disconnected: at most C(n−1,2) edges. Components ≥ n − e.
- Trees and spanning trees. A tree is a connected acyclic graph. Equivalent: connected with n−1 edges; acyclic with n−1 edges; exactly one path between any two vertices. Every tree with n ≥ 2 has at least 2 leaves. A forest with c components has n − c edges. Cayley: n^(n−2) labelled trees on n vertices (Prüfer codes). The number of spanning trees of K_n is n^(n−2); in general use Kirchhoff: any cofactor of the Laplacian D − A.→ Tree: n − 1 edges, unique paths, ≥ 2 leaves. Cayley n^(n−2).
- Euler and Hamilton paths and circuits. An Euler circuit uses every edge exactly once and returns: connected and every degree even. An Euler path exists iff exactly 0 or 2 vertices have odd degree. A Hamilton cycle visits every vertex once; there is no clean criterion (NP-complete). Sufficient: Dirac δ ≥ n/2; Ore deg u + deg v ≥ n for non-adjacent pairs. K_n (n ≥ 3) has (n−1)!/2 Hamilton cycles. A bipartite graph with unequal sides has no Hamilton cycle.→ Euler: count odd-degree vertices (0 → circuit, 2 → path). Hamilton: no test.
- Planarity. A planar graph can be drawn with no crossings. Euler's formula: v − e + f = 2 for a connected planar graph. For simple planar graphs with v ≥ 3: e ≤ 3v − 6; if also triangle-free (e.g. bipartite): e ≤ 2v − 4. Every planar graph has a vertex of degree ≤ 5. Kuratowski: planar iff no subdivision of K₅ or K₃,₃. K₄ is planar; K₅ and K₃,₃ are not. The sum of face degrees = 2e.→ v − e + f = 2. Planar: e ≤ 3v − 6 (or 2v − 4 if triangle-free). K₅, K₃,₃ are not planar.
- Colouring, cliques and independent sets. The chromatic number χ(G) is the fewest colours giving adjacent vertices different colours. χ ≥ ω (clique), χ ≤ Δ + 1, and for bipartite graphs χ = 2 (no odd cycle). χ(K_n) = n; χ(C_odd) = 3; χ(C_even) = 2; every tree has χ = 2; every planar graph has χ ≤ 4 (Four Colour Theorem). α(G) is the largest independent set; α·χ ≥ n. The complement turns cliques into independent sets.→ ω ≤ χ ≤ Δ+1. Odd cycle ⇒ χ ≥ 3. Bipartite ⇔ χ ≤ 2.
- Matching and covers. A matching has no shared vertices; a perfect matching covers all vertices (n even). ν(G) is the maximum matching size. A vertex cover touches every edge; τ(G) is the smallest. König: in a bipartite graph ν = τ. Gallai: α + τ = n. Hall: a bipartite graph has a matching saturating side A iff |N(S)| ≥ |S| for every S ⊆ A. K_{n,n} has n! perfect matchings; K_{2n} has (2n−1)!! of them.→ König: bipartite ν = τ. Gallai: α + τ = n. K_{n,n} has n! perfect matchings.
Formulas
What GATE asks
- ★★★Degree sequence / handshake / count edges. Σ deg = 2e; use the parity of odd vertices; Havel–Hakimi for "is this sequence possible".
- ★★★Number of components, edges, connectivity bound. Maximum edges without being connected is C(n−1, 2); minimum components is n − e.
- ★★★Trees: leaves, height, spanning-tree count. e = n − 1; leaves from the degree sum; Cayley or Kirchhoff for counting.
- ★★★Planarity, faces, chromatic number. Euler formula to count faces; e ≤ 3v − 6 to rule out planarity; χ from clique and odd cycles.
- ★★★Euler/Hamilton and matching statements. Count odd vertices; Hall's condition; König.
Traps
One question most years: decide whether a set with an operation is a group, find the order of an element, use Lagrange, or count subgroups and generators of a cyclic group.
- Algebraic structures and the group axioms. A structure (S, ∘) is a group if it is closed, associative, has an identity, and every element has an inverse. Without inverses it is a monoid; without identity too, a semigroup. Abelian = commutative. The identity and the inverse of each element are unique. In a group (ab)⁻¹ = b⁻¹a⁻¹ and cancellation holds. Examples: (ℤ, +), (ℤₙ, +ₙ), (ℤₚ*, ×ₚ) for prime p, Sₙ under composition (non-abelian for n ≥ 3). (ℤ, ×) and (ℕ, +) are not groups.→ Closure, associativity, identity, inverses. (ℤₙ, × mod n) is never a group.
- Subgroups and Lagrange's theorem. H ⊆ G is a subgroup if it is a group under the same operation (test: non-empty and a b⁻¹ ∈ H). Lagrange: |H| divides |G|. So a group of prime order has only the trivial subgroups and is cyclic. The converse is false in general: A₄ has order 12 but no subgroup of order 6. Intersection of subgroups is a subgroup; union usually is not. Index [G : H] = |G|/|H|.→ Lagrange: |H| divides |G|. Cyclic group: one subgroup per divisor.
- Cyclic groups and element orders. The order of a is the least k > 0 with aᵏ = e, and it divides |G|. G is cyclic if some element has order |G|. In a cyclic group of order n: one subgroup for each divisor of n; φ(n) generators; the element aᵏ has order n/gcd(n,k). (ℤₙ, +) is cyclic for every n; (ℤₙ*, ×) is cyclic iff n = 1, 2, 4, pᵏ, 2pᵏ. Every group of prime order is cyclic; every cyclic group is abelian.→ Cyclic of order n: φ(n) generators. Order of aᵏ is n/gcd(n,k).
- Rings, fields and ℤₙ arithmetic. A ring has two operations: (R, +) is an abelian group, multiplication is associative and distributes over +. A field is a commutative ring with 1 in which every non-zero element has a multiplicative inverse. ℤₙ is a field iff n is prime; otherwise it has zero divisors (elements with ab = 0, a,b ≠ 0). Units of ℤₙ are those a with gcd(a,n) = 1, so there are φ(n) of them. A finite integral domain is a field. Boolean algebra = complemented distributive lattice.→ ℤₙ is a field iff n is prime. Units: gcd(a, n) = 1.
Formulas
What GATE asks
- ★★★Is (S, ∘) a group / which axiom fails?. Check closure, associativity, identity, inverses in order; one missing inverse kills it.
- ★★★Order of an element / number of generators. order divides |G|; generators of ℤₙ are the a with gcd(a,n) = 1.
- ★★★Subgroups and Lagrange. Possible subgroup orders are divisors of |G|; count subgroups of a cyclic group by divisors.
- ★★★Rings, fields and ℤₙ. Prime n gives a field; otherwise find a zero divisor.