Sets, Logic and Counting
Sets, Logic and Counting tests set operations, propositional reasoning, permutations and combinations, and the binomial theorem. Questions often require choosing the correct counting model before calculating.
Core rules
- Sets: union, intersection, complement; De Morgan's laws (A∪B)^c=A^c∩B^c and (A∩B)^c=A^c∪B^c.
- Logic: the contrapositive of P⇒Q is ¬Q⇒¬P and is equivalent to it; the converse Q⇒P is not equivalent.
- Counting: permutations order, combinations do not. With identical objects divide by factorial repetitions. Use complementary counting for “at least one.”
- When a problem says “arrange” or “rank,” order matters; “choose” or “select” usually does not.
- Binomial theorem: (a+b)^n=Σ_{k=0}^n C(n,k)a^{n-k}b^k.
Worked example
From 8 students, choose a committee of 3 with at least one girl, given 5 girls and 3 boys. Total committees C(8,3)=56. Committees with no girls choose all 3 from 3 boys: C(3,3)=1. So the count is 56-1=55.
Traps
Do not use permutations when positions are unordered. Do not double-count when a selection can be formed in different orders. In logic, “if P then Q” does not imply “if Q then P.” In binomial expansions, track the exponent sum n-k+k=n and remember C(n,k)=C(n,n-k).