Skip to content
Tutorials Center
My learning

Topics

Lesson 64 of 68 · Practice and Review

Exercises: Logic, Sets and Proofs

Sixteen graded exercises on logic, quantifiers, sets, relations, functions and proofs, each with a runnable Python solution that checks the answer.

Reading about logic and sets is one thing; using them under pressure is another. This lesson gives you sixteen exercises, graded by difficulty, covering everything from the first half of the course: propositional logic, quantifiers, sets, relations, functions and proof support. Each group of exercises comes with a runnable solution block. The code does not just print answers; it checks them by brute force, which is exactly the habit that catches mistakes.

How to use this page: read the exercise, try it on paper first, write down your answer, and only then run the solution. The grades are ★ (warm-up, one idea), ★★ (needs two ideas or some care) and ★★★ (a real puzzle). Where a question asks you to prove something, the code tests the claim on many cases, which helps you find the right statement but never replaces the written proof. For the proof ideas themselves see How Proofs Work and Mathematical Induction.

Four rounds of four

Logic Tautologies, equivalences, a puzzle.
Quantifiers and sets Nested quantifiers, counting subsets.
Relations and functions Properties, injective, surjective.
Proof support Counterexamples, sums, induction bases.
1 / 2

Round 1: logic

Exercise 1 (★). Decide whether each statement is a tautology: (a) (p ∧ q) → p, (b) (p ∨ q) → p, (c) ((p → q) ∧ (q → r)) → (p → r).

Exercise 2 (★★). Show that ¬(p ∧ q) is equivalent to ¬p ∨ ¬q, that p → q is equivalent to ¬p ∨ q, and that exclusive or (p ≠ q) is equivalent to (p ∨ q) ∧ ¬(p ∧ q).

Exercise 3 (★★). How many of the eight truth assignments to p, q, r satisfy (p ∨ q) ∧ (¬p ∨ r) ∧ (¬q ∨ ¬r)? Which ones are they?

Exercise 4 (★★★). On an island, knights always tell the truth and knaves always lie. Person A says: "We are both knaves." What are A and B?

A truth table settles the first three, and the puzzle in the fourth can be solved by trying all four combinations of knight and knave and keeping those where each person's statement agrees with their type. If you need a refresher, see Truth Tables and Logical Equivalences and Laws.

Python Solutions for Round 1

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

(a) and (c) are tautologies; (b) is not, since p = False, q = True makes the premise true and the conclusion false. All three equivalences in Exercise 2 hold on every row. Exercise 3 has exactly two models: p = False, q = True, r = False and p = True, q = False, r = True. For the puzzle, A cannot be a knight, because a knight cannot truthfully say "we are both knaves". So A is a knave and the statement is false, which means at least one of them is a knight, and since A is not, B is a knight. The brute-force search finds only that one consistent case.

Round 2: quantifiers and sets

Exercise 5 (★★). Let the domain be the integers 1 to 10. Decide the truth of (a) ∀x ∃y (y > x), (b) ∃x ∀y (y ≤ x), (c) ∀x ∃y (x + y = 11), (d) ∃y ∀x (x + y = 11). Which pair differs only in the order of the quantifiers, and why does the order matter?

Exercise 6 (★). Let A be the multiples of 2 and B the multiples of 3 among the numbers 1 to 30. Find |A ∪ B|, |A ∩ B| and |A − B|, and check the inclusion-exclusion formula.

Exercise 7 (★★). The set S = {1, 2, 3, 4, 5, 6} has how many subsets, and how many of them have elements that add up to exactly 10? List them.

Exercise 8 (★★). With the universe U = {1, ..., 20}, let X be the even numbers and Y the multiples of 5. Check both De Morgan laws for sets, and say how many numbers lie in neither X nor Y.

See Predicates and Quantifiers, Sets and Set Operations and Power Sets and Cartesian Products if you need the definitions.

Python Solutions for Round 2

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In Exercise 5, (a) is false (the largest number, 10, has nothing above it), (b) is true (take x = 10), (c) is true (take y = 11 − x) and (d) is false (no single y works for every x). Statements (c) and (d) differ only in the order of the quantifiers, yet have opposite truth values: in (c) the choice of y may depend on x, while in (d) one y must work for every x. In Exercise 6 the sizes are 20, 5 and 10. Exercise 7 has 64 subsets (2⁶), five of which sum to 10: {4, 6}, {1, 3, 6}, {1, 4, 5}, {2, 3, 5} and {1, 2, 3, 4}. For Exercise 8 both laws hold, and 8 numbers lie in neither set: 1, 3, 7, 9, 11, 13, 17 and 19.

Round 3: relations and functions

Exercise 9 (★★). On the numbers 1 to 6, define a R b to mean a − b is divisible by 3. Is R reflexive, symmetric and transitive? How many pairs does it contain? Then check whether the relation "a divides b" on the same set is reflexive, antisymmetric and transitive.

Exercise 10 (★). Is f(x) = x² on the integers from −3 to 3 injective? What is its image? Is g(x) = 2x + 1 on 0 to 4 injective?

Exercise 11 (★★★). How many injective functions are there from a 3-element set into a 5-element set? How many surjective functions are there from a 4-element set onto a 3-element set? Count by enumerating every function, then match your answers with a formula.

Exercise 12 (★★). A student claims "n² + n + 41 is prime for every positive integer n." Find the first counterexample.

Review Relations, Equivalence Relations and Partial Orders and Functions and Cardinality first if needed.

Python Solutions for Round 3

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The congruence relation is reflexive, symmetric and transitive with 12 pairs, so it is an equivalence relation whose classes are {1, 4}, {2, 5} and {3, 6}. The divisibility relation is reflexive, antisymmetric and transitive but not symmetric, which makes it a partial order. In Exercise 10, x² is not injective because f(−2) = f(2) = 4, and its image is {0, 1, 4, 9}; 2x + 1 is injective. Exercise 11 has answers 60 and 36; the first is 5 · 4 · 3, and the second comes from inclusion-exclusion over the missed elements. For Exercise 12 the first counterexample is n = 40, since 40² + 40 + 41 = 1681 = 41 · 41.

Round 4: support for proofs

These exercises ask you to prove something. The code first tests the claim, then you write the proof.

Exercise 13 (★★). Prove that n³ − n is divisible by 6 for every integer n, and that the square of an integer leaves remainder 0 or 1 when divided by 4. (Hint: n³ − n = (n − 1)·n·(n + 1); for the second, split into even and odd n.)

Exercise 14 (★). Check numerically the formulas 1² + 2² + ... + n² = n(n + 1)(2n + 1)/6, 1 + 2 + 4 + ... + 2ⁿ⁻¹ = 2ⁿ − 1 and 1 + 3 + 5 + ... + (2n − 1) = n². Then prove one of them by induction.

Exercise 15 (★★). For which positive integers n is 2ⁿ ≥ n³? State the claim precisely and say where an induction proof must start.

Exercise 16 (★★★). Prove that among any 13 integers two have the same remainder when divided by 12. Is 13 the smallest number that guarantees this?

Python Testing the claims of Round 4

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For Exercise 13, the first test confirms the divisibility and the second prints [0, 1]. For the proof of the first claim, the product (n − 1)n(n + 1) contains three consecutive integers, so one is a multiple of 3 and at least one is even, which makes the product divisible by 2 · 3 = 6. For the second claim, an even n = 2k gives n² = 4k², and an odd n = 2k + 1 gives n² = 4k² + 4k + 1, so the remainders are 0 and 1.

Exercise 14: all three identities pass. Sample induction for the last one: the base case n = 1 gives 1 = 1², and if the first n odd numbers add to n², then adding the next odd number 2n + 1 gives n² + 2n + 1 = (n + 1)².

Exercise 15: the claim holds for n = 1 and for every n ≥ 10, and fails for n = 2, ..., 9. An induction proof must therefore take n = 10 as its base case (1024 ≥ 1000). For the step, assume 2ᵏ ≥ k³ with k ≥ 10; then 2ᵏ⁺¹ ≥ 2k³, and 2k³ ≥ (k + 1)³ because (1 + 1/k)³ ≤ 1.1³ < 2 when k ≥ 10.

Exercise 16 is the pigeonhole principle: there are only 12 possible remainders (the pigeonholes) and 13 integers (the pigeons), so some remainder is used twice. Thirteen is the smallest number that works, because the twelve integers 0 to 11 all have different remainders.

Scoring yourself

  • 14 to 16 solved on paper first: you are ready for the counting and number theory exercises.
  • 9 to 13: review the lessons linked above for the rounds you missed, then redo those exercises with fresh numbers.
  • Fewer than 9: that is normal on a first pass. Rerun each solution, change the numbers (a different domain, a different modulus) and predict the new output before you run it.

Making variations is the best practice there is. Change 12 to 7 in Exercise 16, change 5 to 3 in Exercise 11 and see whether the formulas still match.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. Which of these is a tautology?

    If p and q are both true then p is true, so (p and q) -> p can never be false. The other statements each have a falsifying assignment.
  2. 2. On the integers 1 to 10, 'for all x exists y with x + y = 11' is true but 'exists y for all x with x + y = 11' is false. Why?

    Quantifier order matters. In the first, y may be chosen after seeing x; in the second, a single y must work for all x, which is a much stronger demand.
  3. 3. How many subsets does a 6-element set have?

    Each element is either in a subset or not, giving 2^6 = 64 subsets.
  4. 4. For 2^n >= n^3, where must an induction proof start?

    The claim fails for n = 2 to 9 and holds for all n >= 10, so the base case is n = 10, and the step must be valid from there.
  5. 5. What guarantees that 13 integers include two with the same remainder mod 12?

    There are only 12 possible remainders and 13 integers, so two integers must land in the same remainder class.

Summary

  • Truth tables and brute-force enumeration settle propositional questions and finite quantifier questions reliably; the order of nested quantifiers changes the meaning.
  • Set identities, inclusion-exclusion and subset counts (2ⁿ) can be verified directly on small universes.
  • Relations are checked property by property: congruence mod 3 is an equivalence relation, divisibility is a partial order.
  • Counting injective and surjective functions by enumeration confirms the formulas P(m, n) and inclusion-exclusion.
  • Numerical tests find counterexamples and base cases quickly, but only a written proof settles a claim for all n.

Next: Exercises: Counting and Number Theory.