Discrete Maths on one card

Lesson notes

Key points

• De Morgan's laws: Not (P and Q) equals not P or not Q, and vice versa.
• / A ∪ B| = |A|+|B|−|A∩B|: Inclusion–exclusion counts a union without double-counting the shared elements.
• Power set: 2ⁿ: A set with n elements has exactly two to the n subsets.
• Contrapositive proof: To prove P implies Q, prove not Q implies not P instead.
• Induction: Prove the base case, then show case k forces case k plus one.
• Handshake lemma: The degrees of all vertices sum to twice the number of edges.

Takeaway: De Morgan, 2ⁿ subsets, induction, and degree sum = 2 × edges.