Logic & sets
Overlapping groups, subsets, truth tables, and “if … then”.
Pen and paper is fine · no calculator needed why?
Opens at level 32. You're level 1. You can read and practice here now.
the idea
Two overlapping groups share members, so adding them counts the shared ones twice. Take the overlap off once.
A set of n things has 2 to the power n subsets, because each thing is either in or out.
"If P, then Q" means the same as its contrapositive, "if not Q, then not P". The converse, "if Q, then P", can be false while the original is true. A truth table lists every true/false mix of the letters: 4 rows for two letters, 8 for three.
techniques
Add, then take off the overlap
- Either group: add the two counts and subtract the overlap once.
- Neither: the total minus that.
- Only the first: its count minus the overlap.
worked example
Of 50 people surveyed, 30 drink tea, 25 drink coffee, and 12 drink both. How many drink neither?
- Tea or coffee: 30 + 25 − 12 = 43.
- Neither: 50 − 43 = 7.
Answer: 7
In or out: powers of 2
- All subsets, the empty one included: 2 multiplied by itself n times.
- Non-empty subsets: subtract 1.
- Subsets of exactly k elements: C(n, k).
worked example
How many non-empty subsets does a set with 5 elements have?
- 2 × 2 × 2 × 2 × 2 = 32 subsets.
- Leave out the empty one: 32 − 1 = 31.
Answer: 31
Count the true rows
- ∧ (and) needs both sides true; ∨ (or) needs at least one; ¬ (not) flips true and false.
- → (if … then) is false only when the left is true and the right false.
- Count the true rows, or count the false ones and subtract from the total.
worked example
How many of the 8 rows of the truth table make p → (q ∧ r) true? Key: ∧ means and, → means if … then.
- False only when p is true and q ∧ r is false.
- p true: 4 rows, and q ∧ r is false in 3 of them.
- 8 − 3 = 5.
Answer: 5
watch out for
- Forgetting to take off the overlap, so the people in both groups count twice.
- Doubling n instead of raising 2 to the power n. A set of 7 has 128 subsets, not 14.
- Taking the converse as the same statement. Wet ground doesn’t prove rain; a sprinkler could have done it.
- Treating → as false whenever its left side is false. With a false left side, "if … then" is true.
practice
Overlapping groups
worked example
Of 47 gym members, 12 swim, 23 run, and 2 do both. How many swim or run (or both)?
Answer: 33
- Adding 12 and 23 counts the 2 who do both twice, so take them off once:
- 12 + 23 − 2 = 33.
Counting subsets
worked example
How many non-empty subsets does a set with 4 elements have?
Answer: 15
- Each element is in or out: 2⁴ = 16 subsets.
- Leave out the empty one: 16 − 1 = 15.
“If … then”
worked example
Which statement means the same as “If a number is divisible by 4, it is even”?
- If a number is even, it is divisible by 4
- A number is divisible by 4 and it is even
- If a number is not even, it is not divisible by 4
- If a number is not divisible by 4, it is not even
Answer: If a number is not even, it is not divisible by 4
- Swapping the two parts and negating both (the contrapositive) keeps the meaning: “If a number is not even, it is not divisible by 4”.
- The converse and the inverse can be false while the original is true: 6 is even but not divisible by 4.
Truth-table rows
worked example
How many of the 8 rows of the truth table make (¬p ∨ q) → r true? Key: ∨ = or, ¬ = not, → = if … then.
Answer: 5
- Check all 8 rows, written as (p, q, r) with T for true and F for false.
- False only in TTF, FTF and FFF.
- So 5 of the 8 rows make it true.