Discrete Mathematics and Mathematical Reasoning
What this domain tests
This domain tests formal reasoning and finite structures: logic and truth values, proof technique, sets, counting, relations, and basic graph and recurrence ideas. Questions reward precision - a correct conclusion with an invalid justification loses marks.
Core rules and concepts
- Logic: ¬, ∧, ∨, →, ↔. An implication P → Q is false only when P is true and Q is false; its contrapositive ¬Q → ¬P is logically equivalent, but its converse Q → P is not.
- Quantifiers: ∀ (for all) and ∃ (there exists). Negating flips the quantifier and negates the predicate: ¬∀x P(x) ≡ ∃x ¬P(x).
- Proof methods: direct proof, contrapositive, contradiction, and mathematical induction. Induction requires a base case, an inductive hypothesis, and the inductive step.
- Sets: union, intersection, complement, and cardinality; inclusion–exclusion gives |A ∪ B| = |A| + |B| − |A ∩ B|.
- Counting: multiplication principle for sequential choices; pigeonhole principle guarantees a collision when items exceed categories.
- Graphs: the sum of degrees equals twice the number of edges; a graph has an Euler circuit only if every vertex has even degree and the graph is connected.
Worked example
Prove by induction that 1 + 3 + 5 + … + (2n − 1) = n² for all positive integers n.
Base case: n = 1 gives 1 = 1². ✓ Inductive hypothesis: assume 1 + 3 + … + (2k − 1) = k² for some k ≥ 1. Inductive step: add the next odd term, 2(k + 1) − 1 = 2k + 1: [1 + 3 + … + (2k − 1)] + (2k + 1) = k² + 2k + 1 = (k + 1)². This is exactly the formula for n = k + 1, so by induction the statement holds for all positive integers n.
Each of the three components is required; omitting the base case or failing to state the hypothesis is a structural gap.
Traps that cost marks
- Proving the converse instead of the original implication.
- Negating a quantified statement without flipping the quantifier.
- Skipping the base case or assuming the result for all n rather than for k.
- Double counting in set or counting problems by ignoring overlaps.
- Confusing Euler circuits (every edge once) with Hamiltonian cycles (every vertex once).