Skip to main content

Module Quiz

Complete this quiz after finishing the concept pages and practice pages. Work closed-book first, then use the remediation links selectively.

Current Module Questions​

Question 1: Negating Quantified Statements​

Negate the statement:

For every integer n, if n is even, then n^2 is divisible by 4.

Answer: There exists an integer n such that n is even and n^2 is not divisible by 4.

Solution Walkthrough:

  1. Rewrite the statement as for all n, (E(n) -> D(n)).
  2. Negate the universal quantifier: there exists n such that not (E(n) -> D(n)).
  3. Negate the implication: E(n) and not D(n).

Common Errors:

  • Writing for all n instead of switching to there exists n
  • Negating only the conclusion and forgetting the hypothesis must still hold

If You Got This Wrong:

Question 2: Contrapositive Versus Converse​

What is the contrapositive of If a function is bijective, then it is injective?

Answer: If a function is not injective, then it is not bijective.

Solution Walkthrough:

  1. Identify P: the function is bijective.
  2. Identify Q: the function is injective.
  3. Form not Q -> not P.

Common Errors:

  • Giving the converse if injective, then bijective
  • Negating bijective incorrectly as surjective

If You Got This Wrong:

Question 3: Proof Method Choice​

Which proof method would you try first for the statement If n^2 is odd, then n is odd, and why?

Answer: Contrapositive proof, because proving "if n is even, then n^2 is even" is more direct than trying to force oddness out of n^2 immediately.

Solution Walkthrough:

  1. Notice the theorem is an implication.
  2. Observe that the negation of the conclusion, "n is even," has a simple algebraic form n = 2k.
  3. Show that this form forces n^2 to be even.

Common Errors:

  • Calling it contradiction without explaining why contradiction is needed
  • Starting from n^2 = 2k + 1 and getting lost in square-root style reasoning

If You Got This Wrong:

Question 4: Set Equality​

Outline a proof that A - (B union C) = (A - B) intersect (A - C).

Answer: Prove both inclusions by element-chasing.

Solution Walkthrough:

  1. Let x in A - (B union C). Then x in A and x notin B union C, so x notin B and x notin C. Hence x in A - B and x in A - C, so x in (A - B) intersect (A - C).
  2. Let x in (A - B) intersect (A - C). Then x in A, x notin B, and x notin C. Therefore x notin B union C, so x in A - (B union C).

Common Errors:

  • Proving only one inclusion
  • Replacing logical reasoning with a diagram but not a proof

If You Got This Wrong:

Question 5: Function Classification​

Classify f : Z -> Z defined by f(n) = n + 1 as injective, surjective, bijective, or neither.

Answer: Bijective.

Solution Walkthrough:

  1. Injective: if f(a) = f(b), then a + 1 = b + 1, so a = b.
  2. Surjective: for any integer y, choose n = y - 1; then f(n) = y.
  3. Since it is both injective and surjective, it is bijective.

Common Errors:

  • Arguing from examples only
  • Forgetting surjectivity requires handling an arbitrary codomain element

If You Got This Wrong:

Question 6: Relation Properties​

On the set {1, 2, 3}, let

R = {(1,1), (2,2), (3,3), (1,2), (2,3), (1,3)}

Is R reflexive, symmetric, antisymmetric, and transitive?

Answer: Reflexive: yes. Symmetric: no. Antisymmetric: yes. Transitive: yes.

Solution Walkthrough:

  1. Reflexive: all diagonal pairs are present.
  2. Symmetric: (1,2) is in R but (2,1) is not.
  3. Antisymmetric: there is no pair of distinct elements related in both directions.
  4. Transitive: the only nontrivial chain (1,2) and (2,3) gives (1,3), which is present.

Common Errors:

  • Thinking antisymmetric means "not symmetric"
  • Forgetting to inspect actual chains for transitivity

If You Got This Wrong:

Question 7: Equivalence Relation Meaning​

Why does the relation "has the same remainder modulo 4" on the integers count as an equivalence relation?

Answer: It is reflexive, symmetric, and transitive, so it groups integers into equivalence classes by shared remainder.

Solution Walkthrough:

  1. Reflexive: every integer has the same remainder as itself.
  2. Symmetric: if a has the same remainder as b, then b has the same remainder as a.
  3. Transitive: if a matches b and b matches c, then a matches c.
  4. The resulting classes are the residue classes modulo 4.

Common Errors:

  • Listing the properties without explaining the class structure
  • Confusing equivalence classes with subsets chosen arbitrarily

If You Got This Wrong:

Question 8: Partial Orders​

What is the difference between a minimal element and a least element in a partial order?

Answer: A least element is below every element in the set. A minimal element only has no strictly smaller element in the set; there may be several minimal elements.

Solution Walkthrough:

  1. "Least" is a global comparison claim.
  2. "Minimal" is a local no-smaller-neighbor claim.
  3. In partial orders with incomparable elements, minimal need not imply least.

Common Errors:

  • Treating the two terms as synonyms
  • Forgetting that incomparability blocks least-ness

If You Got This Wrong:

Question 9: Ordinary Induction Structure​

What are the five visible parts of a clean induction proof?

Answer: The proposition P(n), the base case, the inductive hypothesis, the inductive step, and the conclusion.

Solution Walkthrough:

  1. State exactly what P(n) means.
  2. Verify the starting case.
  3. Assume P(n) or the appropriate induction assumption.
  4. Derive the next case.
  5. Conclude the statement holds for all intended n.

Common Errors:

  • Omitting the base case
  • Using the inductive hypothesis without stating it
  • Forgetting to restate the final conclusion

If You Got This Wrong:

Question 10: Structural Induction Choice​

Why is structural induction a better first choice than ordinary induction for recursively defined binary strings?

Answer: Because the objects are generated by base cases and constructors, and structural induction follows that exact generation process directly.

Solution Walkthrough:

  1. Recursive definitions specify how objects are built.
  2. Structural induction proves the property for base objects and then for each constructor case.
  3. That matches the real object structure more directly than forcing a numerical induction on length.

Common Errors:

  • Saying "because it is more advanced"
  • Failing to mention the match between constructors and proof cases

If You Got This Wrong:

Interleaved Review Questions​

Prior Question 1: Algorithm Intuition​

Why does binary search run in O(log n) time?

Answer: Because each comparison cuts the remaining search space roughly in half.

Prior Question 2: CS Fundamentals​

What is an abstraction, and why does it matter in computer science?

Answer: An abstraction hides lower-level detail behind a simpler model so reasoning and design stay manageable.

Prior Question 3: Clean Code​

What is the single-responsibility idea in plain language?

Answer: A unit of code should have one main reason to change, rather than mixing unrelated responsibilities.

Prior Question 4: Git Fundamentals​

What is the difference between git merge and git rebase?

Answer: Merge combines branch histories with a merge commit; rebase rewrites commits onto a new base to create a linear history.

Prior Question 5: Clean Code Review Habit​

Why are readable names part of design rather than cosmetic style?

Answer: Because names carry intent and reduce interpretation cost for the next reader and the next change.

Self-Assessment and Remediation​

Scoring Guide​

9-10 current-module questions correct

  • Ready to move toward Module 2.

7-8 current-module questions correct

  • Good progress, but revisit the concept pages tied to missed items and rewrite one proof from scratch.

5-6 current-module questions correct

  • Do another full pass through the practice pages and complete one exercise lane from Book Exercise Lanes.

Below 5 current-module questions correct

  • Rebuild from the concept pages in order. Do not advance yet.