Sets and logic · Year 13

In Year 13 you learn: proof and logic.

Sets collect objects together. Logic makes precise what “and”, “or”, “not” and “if … then” mean. Together they are the grammar of mathematics. They also power database searches and computer circuits.

Key facts

• A ∪ B (union): in A or B or both. A ∩ B (intersection): in both. A′ (complement): not in A. ∅ is the empty set.
• n(A ∪ B) = n(A) + n(B) − n(A ∩ B). For three sets: add the singles, subtract the pairs, add back the triple.
• A set with n elements has 2ⁿ subsets, and n(A × B) = n(A) × n(B).
• ¬ means not, ∧ means and, ∨ means or, and ⇔ means if and only if. ⇒ means implies: it is false only when a true statement implies a false one.
• De Morgan’s laws: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q.
• P ⇒ Q is equivalent to its contrapositive ¬Q ⇒ ¬P, but not to its converse Q ⇒ P.

Worked examples

Other years

• Sets and logic · Year 11
• Sets and logic · Year 12