Discrete Mathematics - Sets, Logic, Graphs, and Combinatorics

Table of Contents

1. Sets
2. Logic
3. Proofs
4. Relations
5. Functions (Discrete)
6. Graph Theory
7. Combinatorics
8. Number Theory
9. Recurrence Relations

---

Sets

Basic Concepts

Set: Collection of distinct objects

Notation:

• {1, 2, 3}
• {x : x has property P}
• Empty set ∅ = {}

Set Operations

Union: A ∪ B = {x : x ∈ A or x ∈ B}

Intersection: A ∩ B = {x : x ∈ A and x ∈ B}

Complement: A’ = {x : x ∉ A} (relative to universal set)

Difference: A - B = {x : x ∈ A and x ∉ B}

Symmetric difference: A ⊕ B = (A - B) ∪ (B - A)

Properties

• Commutative: A ∪ B = B ∪ A, A ∩ B = B ∩ A
• Associative: (A ∪ B) ∪ C = A ∪ (B ∪ C)
• Distributive: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
• De Morgan: (A ∪ B)’ = A’ ∩ B’, (A ∩ B)’ = A’ ∪ B’

Cartesian Product

A × B = {(a, b) : a ∈ A, b ∈ B}

Power Set

P(S) = {A : A ⊆ S}

If |S| = n, then |P(S)| = 2^n.

Venn Diagrams

Visual representation of sets.

---

Logic

Propositions

Proposition: Statement that is true or false (not both)

Compound propositions: Built from atomic propositions

Logical Operators

Negation ¬p: Not p

Conjunction p ∧ q: p AND q

Disjunction p ∨ q: p OR q

Exclusive or p ⊕ q: p XOR q (one but not both)

Conditional p → q: If p then q

• False only when p true and q false

Biconditional p ↔ q: p if and only if q

• True when both same truth value

Equivalences

Identity: p ∧ T ≡ p, p ∨ F ≡ p

Domination: p ∨ T ≡ T, p ∧ F ≡ F

Idempotent: p ∨ p ≡ p, p ∧ p ≡ p

Double negation: ¬(¬p) ≡ p

Commutative: p ∨ q ≡ q ∨ p, p ∧ q ≡ q ∧ p

Associative: p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r

Distributive: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q

Absorption: p ∨ (p ∧ q) ≡ p

Predicates and Quantifiers

Predicate: Statement with variables P(x)

Universal quantifier ∀: For all x, P(x)

Existential quantifier ∃: There exists x such that P(x)

Negation:

• ¬(∀x P(x)) ≡ ∃x ¬P(x)
• ¬(∃x P(x)) ≡ ∀x ¬P(x)

Nested Quantifiers

Order matters: ∀x ∃y and ∃y ∀x are different.

---

Proofs

Direct Proof

To prove p → q, assume p and derive q.

Proof by Contraposition

To prove p → q, prove ¬q → ¬p.

Proof by Contradiction

To prove p, assume ¬p and derive contradiction.

Proof by Cases

Consider all possible cases.

Mathematical Induction

To prove P(n) for all n ∈ ℕ:

1. Base case: P(1) true
2. Inductive step: P(k) → P(k+1) for all k ≥ 1

Strong induction: If P(1), …, P(k) true, then P(k+1) true

---

Relations

Binary Relations

R ⊆ A × B

Domain: {a : (a,b) ∈ R for some b}

Range: {b : (a,b) ∈ R for some a}

Properties (on A × A)

Reflexive: (a,a) ∈ R for all a ∈ A

Symmetric: (a,b) ∈ R ⟹ (b,a) ∈ R

Antisymmetric: (a,b) ∈ R and (b,a) ∈ R ⟹ a = b

Transitive: (a,b) ∈ R and (b,c) ∈ R ⟹ (a,c) ∈ R

Equivalence Relations

Equivalence relation: Reflexive, symmetric, transitive

Equivalence class [a]: {x ∈ A : (a,x) ∈ R}

Partition: {[a] : a ∈ A}

Partial Orders

Partial order: Reflexive, antisymmetric, transitive

Poset: Set with partial order

Total order: Partial order with (a,b) or (b,a) for all a,b

Hasse diagram: Visual representation (upward arrows)

Functions as Relations

f: A → B is relation where for each a ∈ A, exactly one b ∈ B with (a,b) ∈ f.

---

Functions (Discrete)

Injectivity, Surjectivity, Bijectivity

One-to-one (injective): f(a₁) = f(a₂) ⟹ a₁ = a₂

Onto (surjective): For every b ∈ B, there exists a ∈ A with f(a) = b

Bijective: One-to-one and onto

If |A| = |B| < ∞, then: Injective ⟺ surjective ⟺ bijective

Composition

(g ∘ f)(a) = g(f(a))

(g ∘ f) is defined only if range(f) ⊆ domain(g).

Cardinality

Countable: Can be listed as sequence

ℤ, ℚ countable ℝ uncountable

Cantor’s diagonal argument: Show ℝ uncountable

---

Graph Theory

Basic Definitions

Graph G = (V, E):

• V: vertices
• E: edges (pairs of vertices)

Simple graph: No loops or multiple edges

Multigraph: Multiple edges allowed

Pseudograph: Loops and multiple edges

Degree deg(v): Number of edges incident to v

Handshaking Lemma: Σ deg(v) = 2|E|

Paths and Cycles

Walk: Sequence of vertices connected by edges

Trail: Walk with no repeated edges

Path: Trail with no repeated vertices

Cycle: Path with same start and end vertex

Euler path: Uses every edge exactly once

Euler circuit: Euler path that is cycle

Theorem: Euler circuit exists ⟺ all degrees even Euler path exists ⟺ exactly two odd-degree vertices

Hamilton Paths

Hamilton path: Visits each vertex exactly once

Hamilton circuit: Hamilton path that is cycle

No simple necessary and sufficient condition known.

Isomorphism

Isomorphic graphs: Same structure, different labels

Invariants: Properties preserved under isomorphism

• Number of vertices
• Number of edges
• Degree sequence
• Connectivity

Connectivity

Connected: Path exists between any two vertices

Connected component: Maximal connected subgraph

Cut vertex: Removing it disconnects graph

Cut edge: Removing it disconnects graph

Trees

Tree: Connected graph with no cycles

Forest: Graph with no cycles (may be disconnected)

Properties:

• |E| = |V| - 1
• Adding any edge creates cycle
• Removing any edge disconnects

Spanning tree: Tree containing all vertices of graph

Directed Graphs

Directed edge (u,v): From u to v

In-degree, out-degree

Directed cycles, paths

Connectivity (Directed)

Strongly connected: Path exists both ways between any u,v

Weakly connected: Connected if made undirected

Matching

Matching: Set of edges with no shared vertices

Complete matching: Uses all vertices of smaller bipartite set

Hall’s Marriage Theorem: Complete matching exists ⟺ every subset has enough neighbors

---

Combinatorics

Counting Principles

Sum rule: Tasks that cannot occur simultaneously

Product rule: Sequence of choices

Pigeonhole principle: n+1 pigeons, n holes ⟹ two in same hole

Permutations and Combinations

Permutation: Ordered arrangement of r objects from n

$P(n,r) = \frac{n!}{(n-r)!}$

Combination: Unordered selection of r objects from n

$C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

Permutations with repetition: n^r (ordered) Combinations with repetition: C(n+r-1, r)

Binomial Theorem

$(x+y)^n = \sum_{k=0}^n \binom{n}{k}x^{n-k}y^k$

Pascal’s Triangle

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

Inclusion-Exclusion

For two sets: |A ∪ B| = |A| + |B| - |A ∩ B|

General: |A₁ ∪ … ∪ A_n| = Σ|A_i| - Σ|A_i ∩ A_j| + Σ|A_i ∩ A_j ∩ A_k| - …

---

Number Theory

Divisibility

d divides n (d|n): n = kd for some k

Properties:

• If a|b and b|c, then a|c
• If a|b and a|c, then a|(mb + nc)

Division Algorithm

For integers a, d (d > 0): a = dq + r where 0 ≤ r < d

Greatest Common Divisor

gcd(a,b): Largest d with d|a and d|b

Euclidean Algorithm: gcd(a,b) = gcd(b, a mod b)

Extended Euclidean: Find x,y with gcd(a,b) = ax + by

Modular Arithmetic

a ≡ b (mod n): n divides (a-b)

Properties:

• a ≡ a (mod n)
• a ≡ b ⟹ b ≡ a
• a ≡ b and b ≡ c ⟹ a ≡ c
• a ≡ b, c ≡ d ⟹ a+c ≡ b+d and ac ≡ bd

Chinese Remainder Theorem

If gcd(m₁, m₂) = 1, system x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂) has unique solution modulo m₁m₂.

Fermat’s Little Theorem

If p prime and gcd(a,p) = 1: a^(p-1) ≡ 1 (mod p)

Wilson’s Theorem

(p-1)! ≡ -1 (mod p) ⟺ p is prime

Euler’s Theorem

If gcd(a,n) = 1: a^φ(n) ≡ 1 (mod n)

where φ(n) is Euler’s totient function.

---

Recurrence Relations

Linear Homogeneous Recurrence

Form: $a_n = c_1a_{n-1} + c_2a_{n-2} + ... + c_ka_{n-k}$

Characteristic equation: r^k - c₁r^(k-1) - … - c_k = 0

General solution:

• If roots r₁, …, r_k distinct: a_n = α₁r₁^n + … + α_ₖrₖ^n
• If r repeated m times: add r^n, nr^n, …, n^(m-1)r^n

Non-Homogeneous

Form: a_n = c₁a_(n-1) + … + c_k a_(n-k) + g(n)

Method: Find particular solution + homogeneous solution.

Guess based on g(n):

• Polynomial: try polynomial
• r^n: try Ar^n (adjust if characteristic root)

Generating Functions

G(x) = Σ a_n x^n

Operations:

• Sum: G(x) + H(x) generates a_n + b_n
• Product: G(x)H(x) generates convolution
• Derivative: xG’(x) generates na_n

Closed forms: Convert to rational functions, partial fractions.

---

Next: Statistics or Probability

---

Last updated: Comprehensive discrete mathematics reference covering sets, logic, graphs, and combinatorics.