DISCRETE MATHEMATICS

Final Exam Comprehensive Notes

Topics: Sets | Functions | Pigeonhole Principle | Counting

1. SETS
1.1 Basic Definitions
Set An unordered collection of distinct objects (elements/members).
Written as a ∈ A (a belongs to A).

Empty Set ∅ The set with no elements. Also written {}. For all sets S: ∅ ⊆ S.

Cardinality |S| The number of distinct elements in a finite set S.

Universal Set U The set containing all objects under consideration.

1.2 Set Notations

Notation Meaning Example
A⊆B A is a subset of B (every {1,2} ⊆ {1,2,3}
element of A is in B)
A⊂B A is a PROPER subset (A ⊆ B {1,2} ⊂ {1,2,3}
and A ≠ B)
A⊇B A is a superset of B (B ⊆ A) {1,2,3} ⊇ {1,2}
A=B A and B have exactly the {2,4} = {4,2}
same elements
A∉B/A⊄B A is not a subset of B; ∃x {1,5} ⊄ {1,2,3}
(x∈A ∧ x∉B)

1.3 Set Operations

Operation Symbol Definition Example
Union A∪B {x | x∈A ∨ x∈B} {1,2} ∪ {2,3} = {1,2,3}
Intersection A∩B {x | x∈A ∧ x∈B} {1,2} ∩ {2,3} = {2}
Difference A−B {x | x∈A ∧ x∉B} {1,2,3} − {2} = {1,3}
Complement Ā {x∈U | x∉A} = U − A If U={a..z},
 A={vowels},
Ā={consonants}

1.4 Set Identities (MEMORIZE THESE)

Law Identity 1 Identity 2
Identity A∩U=A A∪∅=A
Domination A∪U=U A∩∅=∅
Idempotent A∪A=A A∩A=A
Double Complement Ā̄ = A
Commutative A∪B=B∪A A∩B=B∩A
Associative A∪(B∪C)=(A∪B)∪C A∩(B∩C)=(A∩B)∩C
Distributive A∪(B∩C)=(A∪B)∩(A∪C) A∩(B∪C)=(A∩B)∪(A∩C)
De Morgan's Ā ∩ B̄ = (A∪B) Ā ∪ B̄ = (A∩B)
Absorption A∪(A∩B)=A A∩(A∪B)=A
Complement A∪Ā=U A∩Ā=∅

⚡ EXAM TIP: A − B = A ∩ B̄ . This identity frequently appears in proofs. Also: to prove A = B,

prove A ⊆ B AND B ⊆ A.

1.5 Inclusion-Exclusion (PIE)

|A ∪ B| = |A| + |B| − |A ∩ B|

|A ∪ B ∪ C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

Example: 350 applicants; 220 CS, 147 Business, 51 both. Neither = 350 − (220+147−51) = 350 − 316 =
34.

Extreme Difficulty Questions — Sets

Q1. Let A, B, C be finite sets. Prove that |A ∪ B ∪ C| = |A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|

using only the two-set PIE formula applied twice.

Q2. Given |U|=100, |A|=40, |B|=35, |C|=30, |A∩B|=12, |A∩C|=10, |B∩C|=8, |A∩B∩C|=4. Find |A̅ ∩B̅ ∩C̅ |
(elements in none of the three sets).

Q3. Prove using set-builder notation and logical equivalences that A−(B∩C) = (A−B)∪(A−C).
Q4. How many integers from 1 to 1000 are NOT divisible by 2, 3, or 5? Use PIE.

Q5. If A has n elements, prove that the power set P(A) has exactly 2ⁿ elements.
2. FUNCTIONS
2.1 Core Definitions
Function f: A→B Assigns exactly ONE element f(a) ∈ B to each element a ∈ A. Every
element of A must map somewhere.

Domain The set A — the input set of f.

Codomain The set B — the declared output set.

Range The ACTUAL set of outputs: R = {b | ∃a, f(a)=b}. Range ⊆ Codomain.

Pre-image If f(a)=b, then a is a pre-image of b. An element can have multiple pre-

images.

⚡ EXAM TIP: Range ≠ Codomain (unless surjective). Codomain is declared; range is what is
actually mapped to.

2.2 Types of Functions

Injective (One-to-One)
Every element of the range has exactly 1 pre-image. No two different inputs produce the same output.
∀x,y ∈ A: f(x) = f(y) ⟹ x = y (equivalently: x ≠ y ⟹
f(x) ≠ f(y))

• To PROVE injective: Assume f(x)=f(y), then show x=y algebraically.

• To DISPROVE: Find x ≠ y such that f(x) = f(y).

Surjective (Onto)
Every element in the codomain B has at least one pre-image. Range = Codomain.
∀b ∈ B, ∃a ∈ A: f(a) = b

• To PROVE surjective: Take arbitrary y ∈ B, find an x ∈ A with f(x) = y.

• To DISPROVE: Find a y ∈ B such that no x satisfies f(x) = y.

Bijective (One-to-One Correspondence)

Both injective AND surjective. Every element of B has exactly one pre-image in A.
 • A bijection is invertible — f⁻¹ exists.
• For bijection f: A→B to exist, |A| = |B| must hold for finite sets.

Type Formal Condition Example (f: R→R)

Injective only 1-1 but range ≠ codomain f(x) = eˣ (range is R⁺, not all of
R)
Surjective only Onto but not 1-1 f(x) = x³−x (not 1-1 on R)
Bijective Both 1-1 and onto f(x) = x³ (on R→R)
Neither Not 1-1 and not onto f(x) = x² (on R→R)

2.3 Composition of Functions

For g: A→B and f: B→C, the composition f∘g: A→C is defined as:
(f∘g)(a) = f(g(a)) for all a ∈ A

• Apply g FIRST, then f to the result.

• Composition is NOT commutative: f∘g ≠ g∘f in general.
• If g,f are both injective ⟹ f∘g is injective.
• If g,f are both surjective ⟹ f∘g is surjective.

Example: f(x)=2x+3, g(x)=3x+2

◦ (f∘g)(x) = f(g(x)) = f(3x+2) = 2(3x+2)+3 = 6x+7
◦ (g∘f)(x) = g(f(x)) = g(2x+3) = 3(2x+3)+2 = 6x+11

2.4 Inverse Functions

A function f: A→B is invertible if and only if it is bijective.
The inverse f⁻¹: B→A satisfies: f⁻¹(b) = a whenever f(a) = b.
f∘f⁻¹ = I_B and f⁻¹∘f = I_A (identity functions)

2.5 Monotone Functions & Injectivity

• Strictly increasing: x > y ⟹ f(x) > f(y) ⟹ always injective.
• Strictly decreasing: x > y ⟹ f(x) < f(y) ⟹ always injective.
• Example: x³ is strictly increasing on R, so injective (and also surjective → bijective).
• Example: x² is NOT strictly increasing on R (f(−2)=f(2)) → not injective.

Extreme Difficulty Questions — Functions

Q1. Let f: A→B and g: B→C. Prove that if f∘g (wait: g∘f?) is injective, then f must be injective. Is g also
necessarily injective?
Q2. Suppose f: Z→Z is defined by f(n) = n² + n. Is f injective? Surjective? Justify rigorously.

Q3. Let f: R→R with f(x) = (2x+1)/(x−3) for x ≠ 3. Prove f is injective. Find f ⁻¹. What is the domain of
f⁻¹?

Q4. How many functions are there from a set with m elements to a set with n elements? How many are
injective? How many are bijective (when m=n)?

Q5. Suppose f: A→B is surjective and g: B→C is injective. Is g∘f necessarily injective? Surjective?
Prove or disprove.
3. PIGEONHOLE PRINCIPLE
3.1 Basic Pigeonhole Principle
If n pigeons are placed into k pigeonholes and n > k, then at
least one hole contains ≥ 2 pigeons.

Classic Example Pigeons Holes Conclusion

13 people → same 13 people 12 months At least 2 share a
birth month month
27 words → same 27 words 26 letters At least 2 start with
starting letter same letter
367 people → same 367 people 366 days At least 2 share a
birthday birthday
102 students in a 102 students 101 possible scores At least 2 get the
class (0–100) same score

3.2 Generalized Pigeonhole Principle

If N objects are placed into k boxes, then at least one box contains at least ⌈N/k⌉ objects.
At least one box has ≥ ⌈N/k⌉ objects

Example: 100 people into 12 months → at least ⌈100/12⌉ = ⌈8.33⌉ = 9 share a month.

Finding minimum N: To guarantee at least r objects in some box among k boxes:

N = k(r−1) + 1

Example: 5 grades (A,B,C,D,F), guarantee ≥6 students with same grade: N = 5×(6−1)+1 = 26 students.

3.3 Strategy for PHP Problems

• Identify what the PIGEONS are (the objects being distributed).
• Identify what the HOLES are (the categories/properties).
• Count: if pigeons > holes, you're done for basic PHP.
• For generalized: use ⌈N/k⌉ ≥ r to find minimum N.

3.4 Worked Examples

Socks Problem
12 brown + 12 black socks, picking in the dark:
 • (a) Guarantee 2 same color: 3 socks (2 holes=colors, need 2+1=3 by PHP).
• (b) Guarantee 2 black: Take all 12 brown first (worst case), then need 2 black = 12+2 = 14 socks.

States Problem
Students from 50 states, guarantee 100 from same state:
• N = 50×(100−1)+1 = 50×99+1 = 4951 students.

Remainders Problem
Among any 5 integers, two have the same remainder mod 4.
• Holes: remainders {0,1,2,3} = 4 holes.
• Pigeons: 5 integers > 4 holes → by PHP, two share a remainder.

Same Gender Problem

Among 7 people, at least 4 must be the same gender:
• 2 genders (holes), 7 people (pigeons). ⌈7/2⌉ = 4. So at least 4 are same gender.

⚡ EXAM TIP: PHP guarantees EXISTENCE only — it tells you something must exist, but not
which specific item it is.

Extreme Difficulty Questions — Pigeonhole

Q1. Show that among any 11 integers, there must be two whose difference is divisible by 10. (Hint:
remainders mod 10)

Q2. Prove that among any n+1 integers chosen from {1, 2, ..., 2n}, at least one must divide another.
(Hint: write each integer as 2^k · m where m is odd.)

Q3. In any set of 10 integers, show that some non-empty subset has a sum divisible by 10. (Hint:
Consider partial sums s₀=0, s₁=a₁, s₂=a₁+a₂, ... and remainders mod 10.)

Q4. A chess master plays 77 games over 11 weeks (at least 1 game per day). Show there is some
consecutive sequence of days in which the master plays exactly 11 games.

Q5. Prove that among any 5 points placed inside a unit square (1×1), some two are at distance ≤ √2/2 ≈
0.707 from each other.
4. COUNTING
4.1 Product Rule (Multiplication Principle)
If an event E is a sequence of r ordered tasks, and task i can be done in nᵢ ways, then:
Total ways = n₁ × n₂ × ... × nᵣ

Examples:
• License plates (3 letters + 3 digits): 26³ × 10³ = 17,576,000
• Passwords (1–3 letters, repeats allowed): 26 + 26² + 26³ = 18,278
• 32 computers × 24 ports = 768 total ports

4.2 Sum Rule (Addition Principle)

If event E can happen in one of k MUTUALLY EXCLUSIVE ways with n₁, n₂, ..., n ₖ options each:
Total ways = n₁ + n₂ + ... + nₖ = |A₁ ∪ A₂ ∪ ... ∪ Aₖ| (when
all Aᵢ pairwise disjoint)

Examples:
• Choose 1 project from lists of 23, 15, 19 (no overlap): 23+15+19 = 57
• Three letter initials: 26³ = 17,576 (product rule, not sum rule!)

4.3 Inclusion-Exclusion for Counting

|A ∪ B| = |A| + |B| − |A ∩ B|

Use when options OVERLAP (not mutually exclusive). Always subtract the overlap.

Integers < 1000 divisible by 7 or 11:

• |div by 7| = ⌊999/7⌋ = 142
• |div by 11| = ⌊999/11⌋ = 90
• |div by 77| = ⌊999/77⌋ = 12
• |div by 7 or 11| = 142 + 90 − 12 = 220

4.4 Common Counting Patterns

Scenario Formula Example
Bit strings of length n 2ⁿ Length 8: 2⁸ = 256
Strings of length n over k- kⁿ 3-letter initials: 26³
symbol alphabet
 Strings length 1 to n over k k + k² + ... + kⁿ = k(kⁿ−1)/(k−1) Passwords ≤3 letters:
symbols 26+676+17576
At least one specific char in Total − (strings without it) With ≥1 vowel: 26ⁿ − 21ⁿ
string of n
Strings of length n, start and 2ⁿ⁻² Length 10, start & end with 1:
end with 1 (binary) 2⁸
Three-digit multiples of k ⌊999/k⌋ − ⌊99/k⌋ Multiples of 7: 142−14=128

4.5 The Nested Loop / Product Rule for Code

The value of k after nested loops:
Product Rule version: k = n₁ × n₂ × ... × nₘ
Sum Rule version: k = n₁ + n₂ + ... + nₘ

Nested loops (all nested inside each other) → multiply all loop counts.
Sequential loops (one after another) → add all loop counts.

4.6 Constraint-Based Counting

Key technique: Split into cases or use Total − Complement.

Passwords with at least one digit

• Length 6–8, uppercase or digit (36 chars total), at least 1 digit.
◦ Total(length n) = 36ⁿ. No-digit(length n) = 26ⁿ.
◦ Valid(length n) = 36ⁿ − 26ⁿ.
◦ Total = (36⁶−26⁶) + (36⁷−26⁷) + (36⁸−26⁸)

4.7 Bit String Problems

Problem Method Answer
Length n, any 2ⁿ 2ⁿ
Length n, begin and end with 1 Fix first & last as 1, free middle 2ⁿ⁻²
(n−2)
Length 10, begin and end with 2⁸ = 256 256
1
Length 7, begin with 00 OR PIE: |A|+|B|−|A∩B| = 2⁵+2⁴−2² 44
end with 111 = 44
Length ≤n (not counting 2+4+8+...+2ⁿ = 2ⁿ⁺¹−2 2ⁿ⁺¹−2
empty)
Extreme Difficulty Questions — Counting

Q1. How many 8-character strings over {a–z} contain the substring 'ab'? (Hint: count placements of 'ab',
use inclusion-exclusion for overlapping occurrences.)

Q2. How many ways can you form a committee of 3 men and 2 women from 8 men and 6 women such
that a specific man M and specific woman W are NEVER on the committee together?

Q3. Strings of length 8 over lowercase English (26 letters) — how many contain exactly one vowel?
(Hint: choose position for vowel, choose the vowel, fill rest with consonants.)

Q4. A 5-digit number (no leading zero) is formed from digits 0–9. How many such numbers have digits
in strictly increasing order? (Hint: every set of 5 digits from 1–9 gives exactly one increasing number.)

Q5. How many positive integers less than 1,000,000 have digit-sum exactly 10? (Advanced: use
generating functions or stars-and-bars with constraints.)
5. QUICK REFERENCE CHEAT SHEET
Sets at a Glance
• A⊆B iff ∀x(x∈A → x∈B)
• A=B iff A⊆B AND B⊆A
• A−B = A∩B̄ (very useful identity)
• De Morgan: (A∪B)̄ = Ā∩B̄ ; (A∩B)̄ = Ā∪B̄
• |A∪B| = |A|+|B|−|A∩B| (Inclusion-Exclusion)

Functions at a Glance
• Injective: f(x)=f(y) ⟹ x=y (distinct inputs → distinct outputs)
• Surjective: ∀b∈B, ∃a∈A: f(a)=b (range = codomain)
• Bijective = Injective + Surjective → invertible
• (f∘g)(x) = f(g(x)) — apply g first, f second
• Strictly monotone ⟹ injective

Pigeonhole at a Glance
• Basic: n pigeons, k holes, n>k → some hole has ≥2
• Generalized: some hole has ≥⌈N/k⌉
• Minimum N for ≥r in some hole: N = k(r−1)+1

Counting at a Glance
• Product Rule: Sequential independent tasks → multiply
• Sum Rule: Mutually exclusive choices → add
• Inclusion-Exclusion: overlapping sets → add, subtract overlap
• Complement trick: Total − (unwanted cases)

Floor and Ceiling

⌊x⌋ = greatest integer ≤ x ⌈x⌉ = smallest integer ≥ x

⌈N/k⌉ = minimum guaranteed in some box when N items in k boxes.

Key PHP Formulas

Goal Formula
Min pigeons to guarantee ≥r in some hole (k N = k(r−1) + 1
holes)
Guaranteed max in some hole with N items, k ⌈N/k⌉
holes
Min cards to guarantee ≥2 of same suit (4 suits) N = 4(2−1)+1 = 5

LAST-MINUTE EXAM TIPS

1. For proofs: always state what you ASSUME and what you WANT TO SHOW before
writing.
2. For injective proofs: start with f(x)=f(y), manipulate algebraically to conclude x=y.
3. For surjective proofs: pick arbitrary y∈B, solve for x in terms of y, verify x ∈A.
4. PHP: clearly identify your pigeons AND pigeonholes before applying the principle.
5. Counting: when stuck, try Total − Complement or split into disjoint cases.
6. Set proofs: use element-chasing (show x∈LHS ↔ x∈RHS) or apply known identities.
7. De Morgan's laws work for sets, logic, AND complement of functions — learn all three
forms.