courses › Counting & Discrete Math

Logic & sets

level 32 course

Overlapping groups, subsets, truth tables, and “if … then”.

Pen and paper is fine · no calculator needed why?

Opens at level 32.

Builds on: Counting (not open yet)

the lesson

The idea, the techniques and a tip for each skill, right here. The Learn page adds worked examples for every skill and untimed practice.

Read the lesson · about 3 minutes

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

Two groups that overlap: either, neither, or only one.

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

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

Counting the subsets of a set.

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

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

How many rows of a truth table make a formula true.

∧ (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

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

Tips by skill

TipOverlapping groups: Add the two groups and subtract the overlap once. Neither is the total minus that.
TipCounting subsets: Each element is in or out: 2 to the power n. Subtract 1 for non-empty; use C(n, k) for a fixed size.
Tip“If … then”: Swap the two parts and negate both. That version, the contrapositive, always means the same as the original.
TipTruth-table rows: Go row by row. → is false only when the left side is true and the right side false.

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.

skills · practice stats

From rounds of this course only: box, review and test-out answers are left out. Once a skill has 40 tries, it compares your first 20 tries with your last 20.

Overlapping groups par 18 s not tried yet
worked example
Of 47 gym members, 12 swim, 23 run, and 2 do both. How many swim or run (or both)?

Answer: 33
1. Adding 12 and 23 counts the 2 who do both twice, so take them off once:
2. 12 + 23 − 2 = 33.
Counting subsets par 11 s not tried yet
worked example
How many non-empty subsets does a set with 4 elements have?

Answer: 15
1. Each element is in or out: 2⁴ = 16 subsets.
2. Leave out the empty one: 16 − 1 = 15.
“If … then” par 17 s not tried yet
worked example
Which statement means the same as “If a number is divisible by 4, it is even”?
1. If a number is even, it is divisible by 4
2. A number is divisible by 4 and it is even
3. If a number is not even, it is not divisible by 4
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
1. Swapping the two parts and negating both (the contrapositive) keeps the meaning: “If a number is not even, it is not divisible by 4”.
2. The converse and the inverse can be false while the original is true: 6 is even but not divisible by 4.
Truth-table rows par 20 s not tried yet
worked example
How many of the 8 rows of the truth table make (¬p ∨ q) → r true? Key: ∨ = or, ¬ = not, → = if … then.

Answer: 5
1. Check all 8 rows, written as (p, q, r) with T for true and F for false.
2. False only in TTF, FTF and FFF.
3. So 5 of the 8 rows make it true.

rest ladder

Win 3 of your last 4 rounds and the course rests. A win is 90% right, within 2× the round's par. Pass the review when it comes back and the next rest is longer.

1 day
3 days
7 days
14 days
30 days
60 days
mastered · every 90 days

your rounds

No rounds yet.