Discrete Mathematics
Complete Notes

What is Discrete Mathematics?

Discrete Mathematics is the study of mathematical structures that are fundamentally discrete (separate, distinct) rather than continuous. It deals with objects that can only take specific, separated values.

Discrete vs Continuous Mathematics

Why is Discrete Math Important for Computer Science?

• Algorithm Design — Understanding complexity and efficiency
• Data Structures — Trees, graphs, and networks
• Logic & Proofs — Foundation of program correctness
• Cryptography — Number theory and security
• Database Theory — Relations and set operations
• Artificial Intelligence — Logic, probability, graph search
• Networking — Graph theory for network topology

Main Topics in Discrete Mathematics

What is a Proposition?

A proposition (or statement) is a declarative sentence that is either true (T) or false (F), but not both. The truth value is either 1 (true) or 0 (false).

Examples of Propositions

Logical Operators (Connectives)

Truth Tables

1. Negation (NOT)

2. Conjunction (AND)

3. Disjunction (OR)

4. Implication (IF-THEN)

p → q means "if p then q". It's false only when p is true and q is false.

5. Biconditional (IF AND ONLY IF)

p ↔ q is true when both have the same truth value.

What is Predicate Logic?

Predicate logic (also called first-order logic) extends propositional logic by dealing with statements that contain variables. A predicate is a statement whose truth value depends on one or more variables.

Predicates vs Propositions

Quantifiers

Quantifiers allow us to make statements about "all" or "some" elements in a domain.

1. Universal Quantifier (∀)

Symbol: ∀ (for all, for every)

Meaning: ∀x P(x) means "P(x) is true for ALL values of x in the domain"

Example:
∀x (x² ≥ 0)  means "For all real numbers x, x² is non-negative"
This is TRUE for all real numbers.

∀x (x > 5)  means "For all x, x is greater than 5"
This is FALSE (not all numbers are > 5).

2. Existential Quantifier (∃)

Symbol: ∃ (there exists, for some)

Meaning: ∃x P(x) means "P(x) is true for AT LEAST ONE value of x"

Example:
∃x (x² = 16)  means "There exists an x such that x² = 16"
This is TRUE (x = 4 or x = -4).

∃x (x² = -1)  means "There exists a real x such that x² = -1"
This is FALSE for real numbers.

Negation of Quantifiers

Multiple Quantifiers

Order matters when using multiple quantifiers!

∀x ∃y (x + y = 0)
"For every x, there exists a y such that x + y = 0"
TRUE (for any x, we can choose y = -x)

∃y ∀x (x + y = 0)
"There exists a y such that for all x, x + y = 0"
FALSE (no single y works for ALL x)

Translating English to Logic

What is a Set?

A set is a well-defined collection of distinct objects, called elements or members. Sets are usually denoted by capital letters (A, B, C) and elements by lowercase letters.

A = {1, 2, 3, 4, 5}
B = {red, blue, green}
C = {x | x is an even number}  ← set-builder notation

∈  means "is an element of"
∉  means "is not an element of"

3 ∈ A   (3 is in A)
6 ∉ A   (6 is not in A)

Types of Sets

Set Operations

1. Union (∪)

A ∪ B contains all elements that are in A OR in B (or in both).

A = {1, 2, 3}
B = {3, 4, 5}
A ∪ B = {1, 2, 3, 4, 5}

2. Intersection (∩)

A ∩ B contains only elements that are in BOTH A AND B.

A = {1, 2, 3}
B = {3, 4, 5}
A ∩ B = {3}

3. Difference (−)

A − B contains elements in A but NOT in B.

A = {1, 2, 3}
B = {3, 4, 5}
A − B = {1, 2}

4. Complement (A' or Ā)

A' contains all elements in the universal set U that are NOT in A.

U = {1, 2, 3, 4, 5, 6}
A = {1, 2, 3}
A' = {4, 5, 6}

5. Cartesian Product (×)

A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.

A = {1, 2}
B = {x, y}
A × B = {(1,x), (1,y), (2,x), (2,y)}

|A × B| = |A| × |B| = 2 × 2 = 4

Set Identities (Laws)

De Morgan's Laws for Sets

(A ∪ B)' = A' ∩ B'
(A ∩ B)' = A' ∪ B'

"The complement of a union is the intersection of complements"
"The complement of an intersection is the union of complements"

What is a Relation?

A relation R from set A to set B is a subset of the Cartesian product A × B. It shows how elements of A are related to elements of B.

A = {1, 2, 3}
B = {4, 5}
R = {(1,4), (2,5), (3,4)}  ← relation from A to B

We write: 1 R 4 (1 is related to 4)

Types of Relations

For a relation R on a set A (from A to A):

Equivalence Relation

A relation that is reflexive, symmetric, and transitive is called an equivalence relation.

Example: "=" (equality) is an equivalence relation
- Reflexive: x = x
- Symmetric: if x = y, then y = x
- Transitive: if x = y and y = z, then x = z

What is a Function?

A function f from A to B (written f: A → B) is a special relation where every element in A is related to EXACTLY ONE element in B.

f: A → B
A is the domain
B is the codomain
The set of actual output values is the range

Example:
f(x) = x²
Domain: ℝ (all real numbers)
Codomain: ℝ
Range: [0, ∞) (non-negative reals only)

Types of Functions

Function Examples

One-to-One but NOT Onto:
f: ℝ → ℝ, f(x) = 2x
One-to-one: different x → different 2x
Not onto: odd numbers never appear as outputs

Onto but NOT One-to-One:
f: ℝ → ℝ, f(x) = x²
Onto [0,∞): all non-negative numbers are outputs
Not one-to-one: f(2) = f(-2) = 4

Bijective:
f: ℝ → ℝ, f(x) = x + 5
One-to-one: different x → different x+5
Onto: every real number y = x+5 for some x

Composition of Functions

If f: A → B and g: B → C, then (g ∘ f): A → C is defined as (g ∘ f)(x) = g(f(x))

f(x) = x + 3
g(x) = 2x

(g ∘ f)(x) = g(f(x)) = g(x+3) = 2(x+3) = 2x + 6
(f ∘ g)(x) = f(g(x)) = f(2x) = 2x + 3

Note: g ∘ f ≠ f ∘ g (order matters!)

What is Mathematical Induction?

Mathematical induction is a proof technique used to prove statements about all natural numbers (or integers). Think of it like dominoes — if the first falls and each domino knocks down the next, all dominoes will fall!

Principle of Mathematical Induction

To prove a statement P(n) is true for all n ≥ 1:

• Step 1 (Base Case): Prove P(1) is true
• Step 2 (Inductive Hypothesis): Assume P(k) is true for some arbitrary k ≥ 1
• Step 3 (Inductive Step): Using the assumption, prove P(k+1) is true
• Conclusion: By induction, P(n) is true for all n ≥ 1

Example 1: Sum of First n Natural Numbers

Prove: 1 + 2 + 3 + ... + n = n(n+1)/2

Step 1: Base Case (n=1)
Left side: 1
Right side: 1(1+1)/2 = 1
✓ True for n=1

Step 2: Inductive Hypothesis
Assume true for n=k:
1 + 2 + 3 + ... + k = k(k+1)/2

Step 3: Inductive Step (prove for n=k+1)
Need to show: 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2

Left side:
= [1 + 2 + ... + k] + (k+1)
= k(k+1)/2 + (k+1)           [using hypothesis]
= k(k+1)/2 + 2(k+1)/2
= [k(k+1) + 2(k+1)]/2
= (k+1)(k+2)/2               [factoring]
= Right side  ✓

Conclusion: By induction, formula is true for all n ≥ 1.

Example 2: Power Inequality

Prove: 2ⁿ > n for all n ≥ 1

Base Case (n=1):
2¹ = 2 > 1  ✓

Inductive Hypothesis:
Assume 2^k > k for some k ≥ 1

Inductive Step (prove 2^(k+1) > k+1):
2^(k+1) = 2 · 2^k
        > 2 · k         [using hypothesis: 2^k > k]
        = k + k
        ≥ k + 1        [since k ≥ 1]
∴ 2^(k+1) > k+1  ✓

Conclusion: By induction, 2ⁿ > n for all n ≥ 1.

Strong Induction

In strong induction, we assume P(1), P(2), ..., P(k) are ALL true (not just P(k)), then prove P(k+1).

Regular Induction: Assume P(k) → Prove P(k+1)
Strong Induction:   Assume P(1)∧P(2)∧...∧P(k) → Prove P(k+1)

Use strong induction when proving P(k+1) requires
information from multiple previous cases.

Common Mistakes in Induction

• Forgetting Base Case — Always prove for n=1 (or starting value)
• Not Using Hypothesis — Must explicitly use P(k) assumption in step 3
• Proving Wrong Direction — Must prove P(k) → P(k+1), not the reverse
• Circular Reasoning — Don't assume what you're trying to prove

What is Combinatorics?

Combinatorics is the branch of mathematics concerned with counting, arranging, and combining objects. It answers questions like "How many ways can we arrange these items?" or "How many subsets can we choose?"

Fundamental Counting Principles

1. Addition Principle (OR)

If task A can be done in m ways and task B can be done in n ways, and they CANNOT be done together, then either A OR B can be done in m + n ways.

Example: Travel from City X to City Y
- By train: 3 routes
- By bus: 5 routes
Total ways = 3 + 5 = 8 ways

2. Multiplication Principle (AND)

If task A can be done in m ways and task B can be done in n ways, and both must be done, then A AND B can be done in m × n ways.

Example: Password with 1 letter + 1 digit
- Letters: 26 ways
- Digits: 10 ways
Total passwords = 26 × 10 = 260

Permutations (Order Matters)

A permutation is an arrangement of objects where ORDER matters.

Permutation of n Objects

Number of ways to arrange n distinct objects = n! (n factorial)

n! = n × (n-1) × (n-2) × ... × 2 × 1

Example: Arrange 4 books on a shelf
4! = 4 × 3 × 2 × 1 = 24 ways

Permutation of r Objects from n

P(n, r) or nPr = number of ways to arrange r objects chosen from n objects

P(n, r) = n!/(n-r)!

Example: Choose and arrange 3 winners from 10 contestants
P(10, 3) = 10!/(10-3)! = 10!/7! = 10×9×8 = 720 ways

Combinations (Order Doesn't Matter)

A combination is a selection of objects where ORDER does NOT matter.

C(n, r) or nCr = n!/[r!(n-r)!]

Also written as (n choose r) or ⁿCᵣ

Example: Choose 3 students from 10 for a committee
C(10, 3) = 10!/[3!(10-3)!]
         = 10!/(3!×7!)
         = (10×9×8)/(3×2×1)
         = 120 ways

Permutation vs Combination

Special Cases

C(n, 0) = 1    (one way to choose nothing)
C(n, n) = 1    (one way to choose everything)
C(n, r) = C(n, n-r)    (symmetry property)

Example: C(10, 3) = C(10, 7) = 120

Permutations with Repetition

When objects are not all distinct:

n!/(n₁! × n₂! × ... × nₖ!)

where n₁, n₂, ..., nₖ are counts of repeated objects

Example: Arrange letters in "MISSISSIPPI"
Total letters = 11
M:1, I:4, S:4, P:2

Arrangements = 11!/(1!×4!×4!×2!) = 34,650

Common Problem Types

What is Probability?

Probability measures how likely an event is to occur. It's a number between 0 (impossible) and 1 (certain).

P(Event) = (Number of favorable outcomes) / (Total number of possible outcomes)

P(E) ∈ [0, 1]
P(certain event) = 1
P(impossible event) = 0

Basic Probability Example

Rolling a fair die (6 faces: 1,2,3,4,5,6):

P(getting 4) = 1/6
P(getting even) = 3/6 = 1/2    (faces: 2,4,6)
P(getting ≤ 6) = 6/6 = 1       (certain)
P(getting 7) = 0/6 = 0         (impossible)

Complement Rule

The probability that an event does NOT occur:

P(not E) = 1 − P(E)
or
P(E') = 1 − P(E)

Example: P(not getting 4) = 1 − 1/6 = 5/6

Addition Rule (OR)

For mutually exclusive events (cannot happen together):

P(A or B) = P(A ∪ B) = P(A) + P(B)

Example: Drawing a card
P(Ace or King) = P(Ace) + P(King)
               = 4/52 + 4/52 = 8/52 = 2/13

For non-mutually exclusive events (can happen together):

P(A or B) = P(A) + P(B) − P(A and B)

Example: Drawing a card
P(Heart or King) = P(Heart) + P(King) − P(King of Hearts)
                 = 13/52 + 4/52 − 1/52
                 = 16/52 = 4/13

Multiplication Rule (AND)

For independent events (one doesn't affect the other):

P(A and B) = P(A ∩ B) = P(A) × P(B)

Example: Flipping two coins
P(both heads) = P(H on first) × P(H on second)
              = 1/2 × 1/2 = 1/4

Conditional Probability

Probability of A given that B has occurred:

P(A|B) = P(A ∩ B) / P(B)

Example: Two dice rolled, sum is 8
P(first die is 3 | sum is 8)

Outcomes where sum = 8: (2,6),(3,5),(4,4),(5,3),(6,2) = 5 outcomes
Outcomes where first = 3 and sum = 8: (3,5) = 1 outcome

P(first=3 | sum=8) = 1/5

Independent vs Dependent Events

Expected Value

The average outcome if an experiment is repeated many times:

E(X) = Σ [x × P(x)]

Example: Rolling a die
E(X) = 1×(1/6) + 2×(1/6) + 3×(1/6) + 4×(1/6) + 5×(1/6) + 6×(1/6)
     = (1+2+3+4+5+6)/6
     = 21/6 = 3.5

What is a Graph?

A graph G = (V, E) is a collection of vertices (nodes) V and edges (connections) E that connect pairs of vertices. Graphs model relationships and networks.

Graph Terminology

Types of Graphs

Degree of a Vertex

The degree of a vertex is the number of edges connected to it.

In undirected graph:
deg(v) = number of edges at vertex v

In directed graph:
in-degree = number of edges coming IN
out-degree = number of edges going OUT

Handshaking Lemma

The sum of all vertex degrees equals twice the number of edges:

Σ deg(v) = 2|E|

Why? Each edge contributes 1 to the degree of TWO vertices.

Corollary: In any graph, the number of vertices
with odd degree is EVEN.

Paths and Cycles

• Path: Sequence of vertices where each adjacent pair is connected by an edge
• Simple Path: No vertex is repeated
• Cycle: Path that starts and ends at the same vertex
• Simple Cycle: Cycle with no repeated vertices (except first/last)

Euler and Hamilton Paths

Graph Representation

1. Adjacency Matrix

A matrix where entry (i,j) = 1 if edge exists between vertex i and j, otherwise 0.

Graph: A-B, B-C, A-C

    A  B  C
A [ 0  1  1 ]
B [ 1  0  1 ]
C [ 1  1  0 ]

2. Adjacency List

For each vertex, list its adjacent vertices.

A: [B, C]
B: [A, C]
C: [A, B]

What is a Tree?

A tree is a connected graph with NO cycles. It's the most fundamental hierarchical structure in computer science.

Properties of Trees

• A tree with n vertices has exactly n − 1 edges
• There is exactly one path between any two vertices
• Removing any edge disconnects the tree
• Adding any edge creates exactly one cycle
• A tree is a minimally connected graph

Tree Terminology

Types of Trees

Binary Tree Properties

For a binary tree with n vertices:
- Maximum number of vertices at level i = 2^i
- Maximum vertices in tree of height h = 2^(h+1) − 1
- Minimum height for n vertices = ⌈log₂(n+1)⌉ − 1

For a perfect binary tree:
- Height h → vertices = 2^(h+1) − 1
- Height h → leaves = 2^h

Tree Traversal Methods

Ways to visit all vertices in a tree:

Spanning Trees

A spanning tree of a connected graph G is a subgraph that:

• Includes all vertices of G
• Is a tree (connected, no cycles)
• Has exactly n − 1 edges (where n = number of vertices)

Minimum Spanning Tree (MST)

For a weighted graph, the MST is the spanning tree with minimum total edge weight.

Algorithms to find MST:
1. Kruskal's Algorithm — Sort edges, add smallest without creating cycle
2. Prim's Algorithm — Start from a vertex, grow tree by adding cheapest edge

What is Boolean Algebra?

Boolean algebra is a branch of mathematics that deals with variables that have only two possible values: true (1) or false (0). It's the mathematical foundation of digital electronics and computer logic.

Boolean Operations

Boolean Algebra Laws

De Morgan's Laws

(x · y)' = x' + y'
(x + y)' = x' · y'

In words:
"The complement of AND is OR of complements"
"The complement of OR is AND of complements"

Simplification Example

Simplify: F = x·y + x·y'

Step 1: Factor out x
F = x·(y + y')

Step 2: Apply complement law: y + y' = 1
F = x·1

Step 3: Apply identity law: x·1 = x
F = x

Result: The expression simplifies to just x!

Boolean Functions

A Boolean function maps Boolean inputs to a Boolean output:

f(x, y, z) = x·y' + x'·z

Truth table:
x  y  z | f
0  0  0 | 0
0  0  1 | 1
0  1  0 | 0
0  1  1 | 1
1  0  0 | 1
1  0  1 | 1
1  1  0 | 0
1  1  1 | 0

Canonical Forms

What is a Recurrence Relation?

A recurrence relation is an equation that defines a sequence based on previous terms. Each term is expressed as a function of earlier terms.

Components of a Recurrence Relation

• Recurrence equation: The recursive formula
• Initial conditions: Base case values

Example: a_n = 2·a_(n-1) + 3  with a_0 = 1

a_0 = 1               (initial condition)
a_1 = 2·1 + 3 = 5
a_2 = 2·5 + 3 = 13
a_3 = 2·13 + 3 = 29
...

Types of Recurrence Relations

Solving Linear Homogeneous Recurrence Relations

For: a_n = c₁·a_(n-1) + c₂·a_(n-2)

Step 1: Form characteristic equation: r² = c₁·r + c₂

Step 2: Solve for roots r₁, r₂

Step 3: General solution depends on roots:

• Two distinct roots: a_n = A·r₁ⁿ + B·r₂ⁿ
• One repeated root r: a_n = (A + B·n)·rⁿ

Step 4: Use initial conditions to find A and B

Example: Solve a_n = 5a_(n-1) − 6a_(n-2), a_0=1, a_1=4

Step 1: Characteristic equation
r² = 5r − 6
r² − 5r + 6 = 0
(r − 2)(r − 3) = 0
r₁ = 2, r₂ = 3

Step 2: General solution (two distinct roots)
a_n = A·2ⁿ + B·3ⁿ

Step 3: Apply initial conditions
a_0 = 1: A·2⁰ + B·3⁰ = 1  →  A + B = 1
a_1 = 4: A·2¹ + B·3¹ = 4  →  2A + 3B = 4

Solve system:
From first: B = 1 − A
Substitute: 2A + 3(1−A) = 4
           2A + 3 − 3A = 4
           −A = 1
           A = −1, B = 2

Step 4: Final solution
a_n = −1·2ⁿ + 2·3ⁿ = 2·3ⁿ − 2ⁿ

Verify: a_0 = 2·1 − 1 = 1  ✓
        a_1 = 2·3 − 2 = 4  ✓

Famous Recurrence Relations

Inclusion-Exclusion Principle

For counting elements in unions of sets, avoiding double-counting:

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

For three sets:
|A ∪ B ∪ C| = |A| + |B| + |C|
              − |A ∩ B| − |A ∩ C| − |B ∩ C|
              + |A ∩ B ∩ C|

Pattern: Add individual, subtract pairs, add triples...

Example: Inclusion-Exclusion

In a class of 50 students:
- 30 study Math
- 25 study Physics
- 10 study both

How many study at least one subject?

|M ∪ P| = |M| + |P| − |M ∩ P|
        = 30 + 25 − 10
        = 45 students

Pigeonhole Principle

Simple version: If n+1 objects are placed into n boxes, then at least one box contains more than one object.

Generalized Pigeonhole Principle

If n objects are placed into k boxes, then at least one box contains at least ⌈n/k⌉ objects.

⌈ ⌉ is the ceiling function (rounds up)

Example: 50 students, 7 days of the week
At least one day has: ⌈50/7⌉ = ⌈7.14⌉ = 8 students born on it

Pigeonhole Principle Examples

Example 1: Handshakes
In any group of 6 people, either:
- 3 people mutually know each other, OR
- 3 people are mutual strangers

Example 2: Socks
You have 10 black socks and 10 white socks in a drawer.
How many must you grab (in the dark) to guarantee a matching pair?

Answer: 3 socks
(2 colors = 2 boxes, so 3rd sock must match one)

Example 3: Integers
Among any 5 integers, at least two have the same remainder
when divided by 4.

Proof: 4 possible remainders (0,1,2,3) = 4 boxes
       5 integers = 5 objects
       By pigeonhole: ⌈5/4⌉ = 2 must have same remainder

Counting with Restrictions

1. Arrangements with Restrictions

Problem: Arrange 5 people in a row where 2 specific people
must sit together.

Solution: Treat the 2 as one unit
- Units to arrange: 4 (the pair + 3 others) = 4! ways
- Ways to arrange the pair internally = 2! ways
- Total = 4! × 2! = 24 × 2 = 48 ways

2. Distributing Objects into Boxes

Stars and Bars Method

Distributing n identical objects into k distinct boxes:

Number of ways = C(n + k − 1, k − 1)

Example: Distribute 5 identical candies among 3 children
C(5 + 3 − 1, 3 − 1) = C(7, 2) = 21 ways

Visual: ★★★★★ with 2 bars | to separate:
★★|★|★★ means child1 gets 2, child2 gets 1, child3 gets 2

What is a Mathematical Proof?

A proof is a logical argument that establishes the truth of a mathematical statement beyond any doubt. It uses axioms, definitions, and previously proven results.

Types of Proof Techniques

1. Direct Proof

Start with assumptions (hypothesis), use logical steps, arrive at conclusion.

Structure: Assume P is true → ... logical steps ... → Therefore Q is true

Example: Prove that if n is even, then n² is even.

Proof:
Assume n is even.
Then n = 2k for some integer k    (definition of even)
n² = (2k)² = 4k² = 2(2k²)
Since 2k² is an integer, n² = 2m where m = 2k²
Therefore n² is even.  ∎

2. Proof by Contrapositive

To prove P → Q, instead prove ¬Q → ¬P (contrapositive is logically equivalent)

Example: Prove if n² is odd, then n is odd.

Instead, prove: if n is even, then n² is even
(contrapositive of original statement)

Assume n is even.
n = 2k
n² = 4k² = 2(2k²)  ← even
Therefore, if n is even, n² is even.

By contrapositive: if n² is odd, then n is odd.  ∎

3. Proof by Contradiction

Assume the statement is FALSE, derive a contradiction, conclude it must be TRUE.

Structure: Assume ¬P → ... → Contradiction! → Therefore P must be true

Example: Prove √2 is irrational.

Proof by contradiction:
Assume √2 is rational.
Then √2 = p/q where p,q are integers, q≠0, in lowest terms

√2 = p/q
2 = p²/q²
p² = 2q²    ← p² is even, so p is even
Let p = 2k
(2k)² = 2q²
4k² = 2q²
q² = 2k²    ← q² is even, so q is even

But p and q are both even, contradicting "lowest terms"!
Therefore √2 must be irrational.  ∎

4. Proof by Cases

Break the proof into exhaustive cases, prove each separately.

Example: Prove that n² + n is even for all integers n.

Case 1: n is even
n = 2k
n² + n = (2k)² + 2k = 4k² + 2k = 2(2k² + k) ← even

Case 2: n is odd
n = 2k + 1
n² + n = (2k+1)² + (2k+1)
       = 4k² + 4k + 1 + 2k + 1
       = 4k² + 6k + 2
       = 2(2k² + 3k + 1) ← even

All cases covered, so n² + n is always even.  ∎

5. Proof by Counterexample

To disprove a universal statement (∀x P(x)), find ONE example where it's false.

Disprove: "All prime numbers are odd"

Counterexample: 2 is prime and even.
Therefore the statement is FALSE.  ∎

6. Mathematical Induction

(Already covered in Unit 6 — used to prove statements for all natural numbers)

Proof Strategies Summary

Common Proof-Writing Tips

• Start clearly: State what you're proving
• Use definitions: Apply precise mathematical definitions
• Show all steps: Don't skip logical leaps
• Use proper notation: ∀, ∃, →, ⇔ correctly
• End with ∎ or QED: Signals proof is complete
• Check logic: Each step must follow from previous

🔑 Key Formulas — Quick Reference