Sets
For A = {1, 2, 3, 4}, B = {3, 4, 5}, and C = {2, 4, 6}, find (A ∪ B) ∖ C.
What is {1, 3, 5}?
Write the negation of p → (q ∨ r) using only ¬, ∧, and ∨.
What is p ∧ ¬q ∧ ¬r?
The symbol ∀ represents this quantifier.
What is the universal quantifier (for all)?
With 4 shirts and 3 pairs of pants, this many shirt-and-pants outfits are possible.
What is 12? (4 × 3)
Prove: If n is even, then n² is even. (n is an integer.)
Let n = 2k for an integer k. Then n² = 4k² = 2(2k²). Since 2k² is an integer, n² is even.
If |A| = 20, |B| = 17, and |A ∪ B| = 29, find the number of elements in exactly one of A and B.
What is 21? The intersection has 20 + 17 − 29 = 8 elements, so exactly one contains 29 − 8 = 21.
Simplify (p → q) ∧ (p → ¬q) to an equivalent expression involving only p.
What is ¬p? If p were true, both q and ¬q would be required; if p is false, both implications hold.
Over the integers, the statement ∃x (x² = 9) has this truth value.
What is true? (x = 3 or x = −3 is a witness.)
This many distinct arrangements can be made from 5 different books on a shelf.
What is 120? (5!)
Prove: If n² is even, then n is even. (n is an integer.)
Use contraposition. If n is odd, n = 2k + 1 for an integer k. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. Therefore, if n² is even, n is even.
If |A| = 6 and B ⊆ A with |B| = 2, how many subsets S of A satisfy B ⊆ S ⊊ A?
What is 15? Choose any subset of the 4 elements outside B, excluding the choice of all 4: 2⁴ − 1 = 15.
Determine whether [(p ∨ q) ∧ ¬p] → q is a tautology, contradiction, or contingency. Justify your answer.
A tautology. Whenever the antecedent is true, p is false and p ∨ q is true, so q must be true. When the antecedent is false, the implication is true.
The negation of ∀x P(x) is this quantified statement.
What is ∃x ¬P(x)?
This many 3-person committees can be chosen from 8 students.
What is 56? (8 choose 3 = 8!/(3!5!))
Disprove by counterexample: For all integers a and b, if ab is even, then both a and b are even.
Take a = 2 and b = 3. Their product is 6, which is even, but b = 3 is odd. Thus the universal claim is false.
If |A| = 30, |B| = 25, |C| = 20, |A ∩ B| = 10, |A ∩ C| = 8, |B ∩ C| = 7, and |A ∩ B ∩ C| = 3, find |A ∪ B ∪ C|.
What is 53? By inclusion–exclusion: 30 + 25 + 20 − 10 − 8 − 7 + 3 = 53.
Determine whether (p → q) → (q → p) is a tautology, contradiction, or contingency. Give all assignments that make it false.
A contingency. It is false exactly when p is false and q is true: then p → q is true and q → p is false. It is true for the other three assignments.
Over the integers, ∀x ∃y (y > x) has this truth value.
What is true? (For each x, choose y = x + 1.)
This many length-8 bit strings contain exactly three 1s.
What is 56? (8 choose 3)
If a = 2m + 1 and b = 2n + 1 are odd integers, writing a + b in this form proves the sum is even.
What is 2(m + n + 1)?
For arbitrary sets A, B, C, determine whether A ∖ (B ∩ C) = (A ∖ B) ∩ (A ∖ C). If false, give a counterexample and the correct identity.
False. Take A = B = {1} and C = ∅: the left side is {1}, but the right side is ∅. The correct identity is A ∖ (B ∩ C) = (A ∖ B) ∪ (A ∖ C).
Find a conjunctive normal form (an AND of OR clauses) equivalent to p ↔ (q ∧ r).
What is (¬p ∨ q) ∧ (¬p ∨ r) ∧ (p ∨ ¬q ∨ ¬r)? Expand the biconditional into both implications and distribute.
Over the integers, the negation of ∀x ∃y (y > x) is this statement.
What is ∃x ∀y (y ≤ x)?
This is the minimum number of students needed to guarantee that at least three share a birth month.
What is 25? (With 12 months, 24 could have two per month; the 25th forces three.)
Prove √2 is irrational.
Assume √2 = a/b for positive integers a and b with no common factor greater than 1. Then a² = 2b², so a² is even and therefore a is even. Write a = 2k. Substitution gives b² = 2k², so b is also even. Thus a and b share a factor of 2, a contradiction. Therefore √2 is irrational.