Discrete Mathematics and Logic
Discrete mathematics and logic on this paper tests precise statement manipulation, proof structure, counting, and elementary graph and number theory.
Logic
- Connectives ¬, ∧, ∨, →, ↔. P → Q is equivalent to ¬P ∨ Q and to its contrapositive ¬Q → ¬P; it is not equivalent to the converse Q → P.
- Negation rules: ¬∀x P(x) ≡ ∃x ¬P(x); ¬∃x P(x) ≡ ∀x ¬P(x).
- A tautology is true on every row of its truth table; verify by enumeration or by laws such as De Morgan, distributivity and absorption.
Proof
- Direct, contrapositive, contradiction, and induction.
- Induction has three parts: base case, inductive hypothesis for n = k, and the step to k + 1. The step must use the hypothesis explicitly.
Counting and graphs
- Permutations nPr = n!/(n − r)!; combinations nCr = n!/(r!(n − r)!).
- Inclusion–exclusion: |A∪B| = |A| + |B| − |A∩B|.
- Handshake lemma: the sum of degrees is twice the number of edges, so the number of odd-degree vertices is even.
- Euler circuit exists iff the graph is connected and every vertex has even degree; Euler path iff exactly two vertices have odd degree.
- A tree on n vertices has n − 1 edges and no cycles.
Worked example
Prove 2ⁿ > n² for all integers n ≥ 5. Base: n = 5 gives 32 > 25. True. Hypothesis: assume 2ᵏ > k² for some k ≥ 5. Step: 2^{k+1} = 2·2ᵏ > 2k². It suffices that 2k² ≥ (k + 1)², i.e. k² − 2k − 1 ≥ 0, which holds for k ≥ 1 + √2 ≈ 2.41, hence for k ≥ 5. Therefore 2^{k+1} > (k + 1)², closing the induction.
Traps that cost marks
- Proving the converse when the contrapositive was asked for.
- Induction steps that assume the result for all values up to k when only k was hypothesised, or that skip the base case.
- Double counting when order does not matter.
- Invoking the pigeonhole principle without naming the boxes and the items.
- Claiming an Euler circuit without checking connectivity.