Free practice final
Discrete Math practice final (free, with answers)
A typical Discrete Math final covers propositional logic, proof techniques including induction, sets, functions and relations, counting, recurrences, modular arithmetic, and graphs and trees. Try each problem on paper before opening the answer, and use the explanation to check both your result and your reasoning.
Topics
- Logic and Truth Tables
- Proofs and Induction
- Sets
- Functions and Relations
- Counting
- Recurrences
- Modular Arithmetic
- Graphs and Trees
15 questions
Try each one before you open its answer.
1. Which statement is logically equivalent to ¬(p → q)?
- A ¬p → ¬q
- B ¬p ∨ q
- C p ∧ ¬q
- D ¬p ∧ q
Show answer
Answer: C. p ∧ ¬q
Since p → q ≡ ¬p ∨ q, De Morgan's law gives ¬(p → q) ≡ ¬(¬p ∨ q) ≡ p ∧ ¬q. This matches the truth table: an implication is false only when its hypothesis is true and its conclusion is false.
2. In how many of the 8 rows of its truth table is (p → q) ∧ (q → r) true?
Show answer
Answer: 4
The statement is false whenever p is true and q is false, or q is true and r is false. The only rows that avoid both are (p, q, r) = (F, F, F), (F, F, T), (F, T, T) and (T, T, T), so it is true in 4 rows.
3. To prove "if n² is even, then n is even" for integers n by contraposition, what do you assume and what do you show?
- A Assume n is odd, and show that n² is odd
- B Assume n² is even, and show that n is even
- C Assume n is even, and show that n² is even
- D Assume n² is odd, and show that n is odd
Show answer
Answer: A. Assume n is odd, and show that n² is odd
The contrapositive of p → q is ¬q → ¬p, which is logically equivalent to the original. Here it says that if n is odd then n² is odd, and indeed (2k + 1)² = 2(2k² + 2k) + 1 is odd. Assuming n² is even is a direct proof, and the last two options prove the converse and the inverse, which are not equivalent to the original statement.
4. Find a closed form for S(n) = 1/(1 · 2) + 1/(2 · 3) + 1/(3 · 4) + ... + 1/(n(n + 1)), the kind of formula you would then prove by induction.
Show answer
Answer: S(n) = n/(n + 1)
Each term splits as 1/k − 1/(k + 1), so the sum telescopes to 1 − 1/(n + 1) = n/(n + 1). In the inductive step, k/(k + 1) + 1/((k + 1)(k + 2)) = (k² + 2k + 1)/((k + 1)(k + 2)) = (k + 1)/(k + 2), which is the formula for n = k + 1.
5. For all sets A, B and C, which set is always equal to A − (B ∪ C)?
- A (A − B) ∪ (A − C)
- B (A − B) ∩ (A − C)
- C (A ∩ B) − C
- D (A − B) ∪ C
Show answer
Answer: B. (A − B) ∩ (A − C)
An element is in A − (B ∪ C) exactly when it is in A, not in B, and not in C, which is the same as being in both A − B and A − C. This is De Morgan's law applied inside A. The union (A − B) ∪ (A − C) equals A − (B ∩ C) instead.
6. Define f: ℤ → ℤ on the integers by f(n) = ⌊n/2⌋, the greatest integer less than or equal to n/2. Which statement is true?
- A f is one-to-one but not onto
- B f is a bijection
- C f is neither one-to-one nor onto
- D f is onto but not one-to-one
Show answer
Answer: D. f is onto but not one-to-one
f is not one-to-one because f(0) = f(1) = 0. It is onto because every integer m is an output: f(2m) = m.
7. Let R = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 3), (3, 1), (2, 4), (4, 2)} be a relation on the set {1, 2, 3, 4}. Which statement is true?
- A R is an equivalence relation with classes {1, 3} and {2, 4}
- B R is an equivalence relation with classes {1, 2} and {3, 4}
- C R is reflexive and symmetric but not transitive
- D R is a partial order
Show answer
Answer: A. R is an equivalence relation with classes {1, 3} and {2, 4}
R contains every pair (a, a), contains (b, a) whenever it contains (a, b), and chaining any two of its pairs gives a pair in R, so it is reflexive, symmetric and transitive. In fact a R b exactly when a and b have the same parity, so the classes are {1, 3} and {2, 4}. It is not a partial order, because (1, 3) and (3, 1) are both in R with 1 ≠ 3.
8. A committee of 4 people is chosen from 7 juniors and 5 seniors. How many possible committees include at least one senior?
Show answer
Answer: 460
Count the complement: there are C(12, 4) = 495 committees in all and C(7, 4) = 35 made up only of juniors, so 495 − 35 = 460 include at least one senior. Choosing "one senior, then any 3 others" instead gives 5 · C(11, 3) = 825, which counts committees with several seniors more than once.
9. How many integers from 1 to 1000 are divisible by none of 2, 3 and 5?
- A 734
- B 299
- C 266
- D 333
Show answer
Answer: C. 266
Using ⌊1000/d⌋ for each divisor d, inclusion–exclusion counts the integers divisible by at least one of 2, 3 and 5 as 500 + 333 + 200 − 166 − 100 − 66 + 33 = 734. The remaining 1000 − 734 = 266 are divisible by none of them.
10. What is the smallest number of integers you must choose from {1, 2, ..., 20} to be certain that two of the chosen numbers add up to 21?
- A 10
- B 11
- C 12
- D 20
Show answer
Answer: B. 11
Split the numbers into the 10 pairs {1, 20}, {2, 19}, ..., {10, 11}, each of which sums to 21. By the pigeonhole principle, any 11 numbers include both members of some pair, while the 10 numbers 1 through 10 show that 10 is not enough.
11. Solve the recurrence a(n) = 5a(n − 1) − 6a(n − 2) with a(0) = 1 and a(1) = 4.
Show answer
Answer: a(n) = 2 · 3ⁿ − 2ⁿ
The characteristic equation r² − 5r + 6 = 0 has roots 2 and 3, so a(n) = A · 2ⁿ + B · 3ⁿ. The initial values give A + B = 1 and 2A + 3B = 4, so B = 2 and A = −1. As a check, a(2) = 5 · 4 − 6 · 1 = 14 = 2 · 9 − 4.
12. Which x with 0 ≤ x < 26 satisfies 7x ≡ 3 (mod 26)?
- A 15
- B 11
- C 21
- D 19
Show answer
Answer: D. 19
Since 7 · 15 = 105 = 4 · 26 + 1, the inverse of 7 modulo 26 is 15. Multiplying both sides by 15 gives x ≡ 45 ≡ 19 (mod 26), and 7 · 19 = 133 = 5 · 26 + 3 checks.
13. What is the remainder when 3¹⁰⁰ is divided by 7?
Show answer
Answer: 4
By Fermat's little theorem, 3⁶ ≡ 1 (mod 7). Since 100 = 6 · 16 + 4, 3¹⁰⁰ = (3⁶)¹⁶ · 3⁴ ≡ 3⁴ = 81 ≡ 4 (mod 7).
14. A tree has 4 vertices of degree 3 and 2 vertices of degree 2, and every other vertex is a leaf (degree 1). How many leaves does it have?
- A 4
- B 5
- C 6
- D 8
Show answer
Answer: C. 6
Let L be the number of leaves. The tree has 6 + L vertices, so it has 5 + L edges, and the sum of the degrees is twice the number of edges: 4 · 3 + 2 · 2 + L = 2(5 + L). That gives 16 + L = 10 + 2L, so L = 6.
15. Which of these graphs has an Euler circuit, a closed walk that uses every edge exactly once?
- A The complete graph K₄
- B The complete graph K₅
- C The complete bipartite graph K₂,₃
- D The complete bipartite graph K₃,₃
Show answer
Answer: B. The complete graph K₅
A connected graph has an Euler circuit exactly when every vertex has even degree. Every vertex of K₅ has degree 4, while every vertex of K₄ and K₃,₃ has degree 3, and K₂,₃ has two vertices of degree 3.