MAT 243: Discrete Mathematical Structures

A Comprehensive Guide to Mastering Foundational Topics in Discrete Mathematics

Table of Contents

1. Propositional Logic 2. Predicates and Quantifiers 3. Rules of Inference and Proof Techniques 4. Set Theory 5. Functions, Sequences, and Summation 6. Algorithms and Growth of Functions 7. Elementary Number Theory 8. Mathematical Induction and Recursion 9. Combinatorics and Counting Principles 10. Relations Glossary

1. Propositional Logic

Propositional logic forms the foundation of mathematical reasoning and computer science. A proposition is a declarative statement that is either true or false, but not both.

Basic Logical Operators

Negation (¬): If p is true, then ¬p is false, and vice versa.
Conjunction (∧): p ∧ q is true only when both p and q are true.
Disjunction (∨): p ∨ q is false only when both p and q are false.
Implication (→): p → q is false only when p is true and q is false.
Biconditional (↔): p ↔ q is true when p and q have the same truth value.

Truth Tables

Truth tables enumerate all possible truth value assignments for propositions. They are essential for verifying logical equivalences and analyzing complex statements.

Example: Truth Table for Implication
p q p → q
T T T
T F F
F T T
F F T

Notice that an implication is only false when the hypothesis is true and the conclusion is false. This counterintuitive behavior is crucial in mathematical proofs.

Logical Equivalences

Two compound propositions are logically equivalent if they have the same truth values in all possible cases. We denote logical equivalence with ≡.

Key Equivalences:
De Morgan's Laws:
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

Implication:
p → q ≡ ¬p ∨ q
p → q ≡ ¬q → ¬p (contrapositive)

Double Negation:
¬(¬p) ≡ p

Applications in Computer Science

Propositional logic is fundamental to:

Programming Example:
function checkAccess(isAdmin, hasPermission, isOwner) { // Logical expression: access granted if // (admin OR has permission) AND (not suspended) return (isAdmin || hasPermission) && isOwner; } // This mirrors the logical statement: // access = (A ∨ P) ∧ O

2. Predicates and Quantifiers

Predicates extend propositional logic by allowing variables and quantifiers. A predicate is a statement involving variables that becomes a proposition when the variables are assigned values.

Universal Quantifier (∀)

∀x P(x) means "P(x) is true for all values of x in the domain"
Example: Let P(x) be "x² ≥ 0"
∀x ∈ ℝ, P(x) is TRUE (every real number squared is non-negative)

Existential Quantifier (∃)

∃x P(x) means "there exists at least one x such that P(x) is true"
Example: Let Q(x) be "x² = 2"
∃x ∈ ℝ, Q(x) is TRUE (√2 satisfies this)
∃x ∈ ℚ, Q(x) is FALSE (no rational number squares to 2)

Nested Quantifiers

Order matters crucially when quantifiers are nested. Consider these different statements:

∀x ∃y (x < y)
"For every x, there exists a y greater than x" (TRUE for real numbers)

∃y ∀x (x < y)
"There exists a y that is greater than all x" (FALSE for real numbers)

Negating Quantified Statements

Negation Rules:
¬(∀x P(x)) ≡ ∃x ¬P(x)

¬(∃x P(x)) ≡ ∀x ¬P(x)
Example: Negate "All students passed the exam"
Original: ∀x (Student(x) → Passed(x))
Negation: ∃x (Student(x) ∧ ¬Passed(x))
In English: "There exists a student who did not pass"

3. Rules of Inference and Proof Techniques

Mathematical proofs are logical arguments that establish the truth of mathematical statements. Mastering proof techniques is essential for mathematical maturity.

Rules of Inference

Modus Ponens:
p → q
p
∴ q
Modus Tollens:
p → q
¬q
∴ ¬p
Hypothetical Syllogism:
p → q
q → r
∴ p → r

Direct Proof

To prove p → q directly, assume p is true and show that q must follow logically.

Theorem: If n is an odd integer, then n² is odd.

Proof:
  1. Assume n is odd. Then n = 2k + 1 for some integer k.
  2. Consider n² = (2k + 1)² = 4k² + 4k + 1
  3. Factor: n² = 2(2k² + 2k) + 1
  4. Let m = 2k² + 2k, which is an integer.
  5. Then n² = 2m + 1, which is odd by definition. ∎

Proof by Contrapositive

To prove p → q, instead prove ¬q → ¬p (the contrapositive).

Theorem: If n² is even, then n is even.

Proof (by contrapositive):
  1. We prove: if n is odd, then n² is odd.
  2. Assume n is odd. Then n = 2k + 1 for some integer k.
  3. n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
  4. Therefore n² is odd.
  5. By contrapositive, if n² is even, then n must be even. ∎

Proof by Contradiction

Assume the statement is false and derive a logical contradiction.

Theorem: √2 is irrational.

Proof (by contradiction):
  1. Assume √2 is rational. Then √2 = p/q where p, q are integers with no common factors (lowest terms).
  2. Squaring both sides: 2 = p²/q²
  3. Therefore: 2q² = p²
  4. This means p² is even, so p must be even (by previous theorem).
  5. Let p = 2k. Then 2q² = (2k)² = 4k²
  6. Dividing by 2: q² = 2k²
  7. This means q² is even, so q is even.
  8. But if both p and q are even, they share a common factor of 2.
  9. This contradicts our assumption that p/q is in lowest terms.
  10. Therefore, √2 must be irrational. ∎

Constructive vs Non-Constructive Proofs

A constructive proof explicitly constructs an example, while a non-constructive proof shows existence without construction.

Non-Constructive Example: There exist irrational numbers a and b such that a^b is rational.

Proof: Consider √2^√2. Either it's rational (and we're done), or it's irrational. If it's irrational, let a = √2^√2 and b = √2. Then:
a^b = (√2^√2)^√2 = √2^(√2·√2) = √2^2 = 2
Which is rational. Therefore, such numbers exist. ∎

4. Set Theory

Set theory provides the foundation for modern mathematics. A set is an unordered collection of distinct objects called elements or members.

Set Notation and Definitions

A = {1, 2, 3, 4, 5} (roster notation)
B = {x ∈ ℕ | x < 6} (set-builder notation)
∅ or {} (empty set)

Set Operations

Union (A ∪ B): All elements in A or B or both
Intersection (A ∩ B): All elements in both A and B
Difference (A - B): All elements in A but not in B
Complement (A̅): All elements in the universal set U not in A

Venn Diagram: A ∪ B

The shaded regions show the union of sets A and B

Set Identities

De Morgan's Laws for Sets:
(A ∪ B)̅ = A̅ ∩ B̅
(A ∩ B)̅ = A̅ ∪ B̅
Distributive Laws:
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Cardinality and Power Sets

The cardinality |A| is the number of elements in set A. The power set P(A) is the set of all subsets of A.

Example: Let A = {1, 2, 3}
|A| = 3
P(A) = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
|P(A)| = 2³ = 8

General Rule: If |A| = n, then |P(A)| = 2ⁿ

Cartesian Product

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

Example: A = {1, 2}, B = {x, y}
A × B = {(1,x), (1,y), (2,x), (2,y)}
|A × B| = |A| · |B| = 2 · 2 = 4

5. Functions, Sequences, and Summation

Functions

A function f: A → B assigns to each element of A (domain) exactly one element of B (codomain). The range is the set of all actual outputs.

Injective (One-to-One): Different inputs produce different outputs
∀x₁, x₂ ∈ A, if f(x₁) = f(x₂), then x₁ = x₂
Surjective (Onto): Every element in the codomain is mapped to
∀y ∈ B, ∃x ∈ A such that f(x) = y
Bijective: Both injective and surjective (perfect one-to-one correspondence)
Examples:
f(x) = 2x (ℝ → ℝ) is injective and surjective (bijective)
g(x) = x² (ℝ → ℝ) is neither injective (g(-2) = g(2)) nor surjective (no x gives -1)
h(x) = x² (ℝ⁺ → ℝ⁺) is bijective when domain and codomain are restricted to non-negative reals

Function Composition and Inverse

Composition: (g ∘ f)(x) = g(f(x))

Inverse: f⁻¹ exists if and only if f is bijective
f(f⁻¹(x)) = x and f⁻¹(f(x)) = x

Sequences

A sequence is a function from positive integers to a set. We typically write aₙ instead of a(n).

Arithmetic Sequence: aₙ = a₁ + (n-1)d
Example: 2, 5, 8, 11, 14, ... (d = 3)

Geometric Sequence: aₙ = a₁ · rⁿ⁻¹
Example: 3, 6, 12, 24, 48, ... (r = 2)

Summation Notation

Σ(i=1 to n) i = n(n+1)/2

Σ(i=1 to n) i² = n(n+1)(2n+1)/6

Σ(i=0 to n) rⁱ = (rⁿ⁺¹ - 1)/(r - 1) for r ≠ 1
Example: Calculate Σ(i=1 to 100) i
Using the formula: 100(101)/2 = 5050

6. Algorithms and Growth of Functions

Big-O Notation

Big-O notation describes the asymptotic upper bound of an algorithm's time or space complexity.

f(n) = O(g(n)) if there exist constants c > 0 and n₀ > 0 such that
0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀

Common Complexity Classes

Notation Name Example
O(1) Constant Array access, hash table lookup
O(log n) Logarithmic Binary search, balanced tree operations
O(n) Linear Linear search, array traversal
O(n log n) Linearithmic Efficient sorting (merge sort, heap sort)
O(n²) Quadratic Nested loops, bubble sort
O(2ⁿ) Exponential Recursive fibonacci, subset generation
O(n!) Factorial Permutation generation, traveling salesman brute force
Algorithm Analysis Example:
function findMax(arr) { let max = arr[0]; // O(1) for (let i = 1; i < arr.length; i++) { // O(n) if (arr[i] > max) { // O(1) max = arr[i]; // O(1) } } return max; // O(1) } // Overall complexity: O(n)

Big-Omega and Big-Theta

Ω(g(n)): Lower bound - f(n) grows at least as fast as g(n)
Θ(g(n)): Tight bound - f(n) grows at the same rate as g(n)
Example: For f(n) = 3n² + 5n + 2:
f(n) = O(n²) - upper bound
f(n) = Ω(n²) - lower bound
f(n) = Θ(n²) - tight bound

7. Elementary Number Theory

Divisibility

a | b (a divides b) if there exists an integer k such that b = ak
Properties of Divisibility:
  • If a | b and b | c, then a | c (transitivity)
  • If a | b and a | c, then a | (b + c) and a | (b - c)
  • If a | b, then a | bc for any integer c

Prime Numbers

A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself.

Fundamental Theorem of Arithmetic: Every integer greater than 1 can be uniquely represented as a product of prime numbers (up to ordering).
Example:
84 = 2² × 3 × 7
100 = 2² × 5²
1001 = 7 × 11 × 13

Greatest Common Divisor (GCD)

The GCD of two integers is the largest positive integer that divides both numbers.

Euclidean Algorithm:
function gcd(a, b) { while (b !== 0) { let temp = b; b = a % b; a = temp; } return a; } // Example: gcd(48, 18) // 48 = 2 × 18 + 12 // 18 = 1 × 12 + 6 // 12 = 2 × 6 + 0 // GCD = 6

Modular Arithmetic

a ≡ b (mod m) means m divides (a - b), or equivalently, a and b have the same remainder when divided by m.

Examples:
17 ≡ 5 (mod 12) because 17 - 5 = 12
-3 ≡ 7 (mod 10) because -3 - 7 = -10
Properties:
If a ≡ b (mod m) and c ≡ d (mod m), then:
  • a + c ≡ b + d (mod m)
  • a × c ≡ b × d (mod m)
  • aⁿ ≡ bⁿ (mod m)

8. Mathematical Induction and Recursion

Principle of Mathematical Induction

To prove ∀n ≥ n₀, P(n) is true:

  1. Base Case: Show P(n₀) is true
  2. Inductive Step: Show that if P(k) is true, then P(k+1) is true
  3. Conclusion: By induction, P(n) is true for all n ≥ n₀
Theorem: Prove that Σ(i=1 to n) i = n(n+1)/2 for all n ≥ 1

Proof:
  1. Base Case (n=1): LHS = 1, RHS = 1(2)/2 = 1. ✓
  2. Inductive Hypothesis: Assume true for n = k:
    Σ(i=1 to k) i = k(k+1)/2
  3. Inductive Step: Prove for n = k+1:
    Σ(i=1 to k+1) i = [Σ(i=1 to k) i] + (k+1)
    = k(k+1)/2 + (k+1) [by hypothesis]
    = (k+1)[k/2 + 1]
    = (k+1)(k+2)/2
    = (k+1)((k+1)+1)/2 ✓
  4. Conclusion: By induction, the formula holds for all n ≥ 1. ∎

Strong Induction

In strong induction, we assume P(n₀), P(n₀+1), ..., P(k) are all true when proving P(k+1).

Theorem: Every integer n ≥ 2 can be written as a product of primes.

Proof (by strong induction):
  1. Base Case: n = 2 is prime, so it's trivially a product of primes (itself).
  2. Inductive Hypothesis: Assume every integer from 2 to k can be written as a product of primes.
  3. Inductive Step: Consider k+1:
    Case 1: If k+1 is prime, we're done.
    Case 2: If k+1 is composite, then k+1 = ab where 2 ≤ a, b ≤ k.
    By the inductive hypothesis, both a and b can be written as products of primes.
    Therefore, k+1 = ab is also a product of primes.
  4. Conclusion: By strong induction, every integer n ≥ 2 is a product of primes. ∎

Recursion

A recursive definition defines an object in terms of itself with a base case.

Factorial Function:
function factorial(n) { if (n === 0) return 1; // base case return n * factorial(n-1); // recursive case } // factorial(5) = 5 × 4 × 3 × 2 × 1 = 120
Fibonacci Sequence:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n ≥ 2
function fibonacci(n) { if (n <= 1) return n; return fibonacci(n-1) + fibonacci(n-2); } // Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Structural Induction

Used to prove properties about recursively defined structures like trees, lists, or formal languages.

9. Combinatorics and Counting Principles

Basic Counting Principles

Product Rule: If there are n₁ ways to do task 1 and n₂ ways to do task 2, there are n₁ × n₂ ways to do both tasks.
Sum Rule: If there are n₁ ways to do task 1 and n₂ ways to do task 2 (and they're mutually exclusive), there are n₁ + n₂ ways to do either task.

Permutations

A permutation is an arrangement where order matters.

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

Number of ways to arrange r objects from n distinct objects
Example: How many ways can we arrange 3 books from a shelf of 5?
P(5, 3) = 5!/(5-3)! = 5!/2! = 120/2 = 60 ways

Combinations

A combination is a selection where order doesn't matter.

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

Also written as (n choose r) or ⁿCᵣ
Example: How many ways can we choose 3 books from 5?
C(5, 3) = 5!/(3!×2!) = 120/(6×2) = 10 ways

Binomial Theorem

(x + y)ⁿ = Σ(k=0 to n) C(n,k) xⁿ⁻ᵏ yᵏ
Example: (x + y)³ = C(3,0)x³ + C(3,1)x²y + C(3,2)xy² + C(3,3)y³
= x³ + 3x²y + 3xy² + y³

Pigeonhole Principle

If n items are put into m containers and n > m, then at least one container must contain more than one item.

Generalized: If n items are put into m containers, at least one container has ⌈n/m⌉ items.
Example: In any group of 13 people, at least 2 were born in the same month.
(13 people, 12 months → by pigeonhole principle)

Inclusion-Exclusion Principle

|A ∪ B| = |A| + |B| - |A ∩ B|

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
Example: In a class of 30 students, 20 play soccer, 15 play basketball, and 10 play both. How many play at least one sport?
|S ∪ B| = 20 + 15 - 10 = 25 students

Basic Probability

P(E) = |E| / |S|
where E is an event and S is the sample space
Example: Probability of rolling a sum of 7 with two dice:
Favorable outcomes: (1,6), (2,5), (3,4), (4,3), (5,2), (6,1) = 6 outcomes
Total outcomes: 6 × 6 = 36
P(sum = 7) = 6/36 = 1/6

10. Relations

Binary Relations

A binary relation R from set A to set B is a subset of A × B. We write aRb to mean (a,b) ∈ R.

Properties of Relations

Reflexive: ∀a ∈ A, aRa
(Every element relates to itself)
Symmetric: ∀a,b ∈ A, if aRb then bRa
(If a relates to b, then b relates to a)
Transitive: ∀a,b,c ∈ A, if aRb and bRc then aRc
(Relation chains together)
Antisymmetric: ∀a,b ∈ A, if aRb and bRa then a = b
(Different elements can't relate both ways)

Equivalence Relations

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

Examples of Equivalence Relations:
  • Equality (=) on any set
  • Congruence modulo n: a ≡ b (mod n)
  • "Has the same age as" on people
  • "Is similar to" on triangles

Equivalence Classes

For an equivalence relation R on set A, the equivalence class of element a is:

[a] = {b ∈ A | aRb}
Example: Consider integers under congruence mod 3
[0] = {..., -6, -3, 0, 3, 6, 9, ...}
[1] = {..., -5, -2, 1, 4, 7, 10, ...}
[2] = {..., -4, -1, 2, 5, 8, 11, ...}

These three equivalence classes partition the integers.

Partial Orders

A relation that is reflexive, antisymmetric, and transitive is a partial order.

Examples of Partial Orders:
  • ≤ on real numbers
  • ⊆ (subset relation) on sets
  • "Divides" (|) on positive integers
  • Lexicographic ordering on strings

Hasse Diagrams

A Hasse diagram is a visual representation of a partial order, showing elements as nodes with lines connecting comparable elements (smaller below larger).

Hasse Diagram Example: Divisibility on {1, 2, 3, 4, 6, 12}

12
/ \
6 4
/ \ /
3 2
\ /
1

This shows the divisibility relationships (reading bottom to top)

Applications in Computer Science

Code Example: Checking Transitivity
function isTransitive(relation, set) { for (let a of set) { for (let b of set) { for (let c of set) { if (relation(a, b) && relation(b, c)) { if (!relation(a, c)) { return false; // Found violation } } } } } return true; }

Comprehensive Glossary

Algorithm: A finite sequence of well-defined instructions to solve a problem or perform a computation.

Antisymmetric: A relation R where if aRb and bRa, then a = b.

Bijection: A function that is both injective (one-to-one) and surjective (onto).

Biconditional: A logical statement p ↔ q that is true when both p and q have the same truth value.

Big-O Notation: A mathematical notation describing the limiting behavior of a function, used to classify algorithms.

Binomial Coefficient: The number C(n,k) representing the number of ways to choose k items from n items.

Cardinality: The number of elements in a set, denoted |A|.

Cartesian Product: The set A × B of all ordered pairs (a,b) where a ∈ A and b ∈ B.

Codomain: The set of all possible output values of a function.

Combination: A selection of items where order doesn't matter.

Complement: The set of all elements not in a given set (relative to a universal set).

Composite Number: An integer greater than 1 that is not prime (has factors other than 1 and itself).

Conjunction: The logical operation AND (∧), true only when both operands are true.

Contrapositive: The statement ¬q → ¬p, logically equivalent to p → q.

Converse: The statement q → p, obtained by swapping hypothesis and conclusion of p → q.

Countable: A set that can be put in one-to-one correspondence with natural numbers or a subset thereof.

Direct Proof: Proving p → q by assuming p and logically deriving q.

Disjunction: The logical operation OR (∨), false only when both operands are false.

Divisibility: Integer a divides integer b (a|b) if b = ka for some integer k.

Domain: The set of all possible input values for a function.

Empty Set: The set containing no elements, denoted ∅ or {}.

Equivalence Class: The set of all elements related to a given element under an equivalence relation.

Equivalence Relation: A relation that is reflexive, symmetric, and transitive.

Euclidean Algorithm: An efficient algorithm for computing the greatest common divisor of two integers.

Existential Quantifier: The symbol ∃ meaning "there exists."

Function: A relation that assigns exactly one output to each input.

Greatest Common Divisor (GCD): The largest positive integer that divides two given integers.

Hasse Diagram: A graph representation of a partial order showing comparable elements.

Implication: The logical statement p → q, false only when p is true and q is false.

Inclusion-Exclusion Principle: A counting technique for finding the size of a union of sets.

Induction: A proof technique establishing a statement for all natural numbers.

Injection: A function where different inputs produce different outputs (one-to-one).

Integer: A whole number that can be positive, negative, or zero.

Intersection: The set A ∩ B containing elements in both A and B.

Inverse Function: A function f⁻¹ that "undoes" f, existing only for bijections.

Logical Equivalence: Two statements having the same truth value in all cases.

Mathematical Induction: Proving a statement by showing base case and inductive step.

Modular Arithmetic: Arithmetic where numbers "wrap around" upon reaching a modulus.

Modus Ponens: The rule of inference: from p → q and p, conclude q.

Modus Tollens: The rule of inference: from p → q and ¬q, conclude ¬p.

Negation: The logical NOT operation (¬), reversing truth value.

Partial Order: A relation that is reflexive, antisymmetric, and transitive.

Partition: A collection of disjoint subsets whose union is the original set.

Permutation: An arrangement of objects where order matters.

Pigeonhole Principle: If n items are put into m containers with n > m, at least one container has multiple items.

Power Set: The set P(A) of all subsets of set A.

Predicate: A statement involving variables that becomes a proposition when values are assigned.

Prime Number: An integer greater than 1 divisible only by 1 and itself.

Proof by Contradiction: Assuming the negation of the statement and deriving a contradiction.

Proof by Contrapositive: Proving p → q by proving ¬q → ¬p.

Proposition: A declarative statement that is either true or false.

Range: The set of actual output values produced by a function.

Recurrence Relation: An equation defining a sequence in terms of previous terms.

Recursion: Defining something in terms of itself with a base case.

Reflexive: A relation R where every element relates to itself (aRa for all a).

Relation: A subset of the Cartesian product of two sets.

Sequence: An ordered list of numbers, typically defined by a formula or recurrence.

Set: An unordered collection of distinct objects.

Strong Induction: Induction assuming all previous cases when proving the next case.

Subset: Set A is a subset of B (A ⊆ B) if every element of A is in B.

Summation: The notation Σ representing the sum of a sequence of terms.

Surjection: A function where every element in the codomain is mapped to (onto).

Symmetric: A relation R where if aRb then bRa.

Tautology: A compound proposition that is always true.

Transitive: A relation R where if aRb and bRc, then aRc.

Truth Table: A table showing all possible truth value combinations for a logical statement.

Union: The set A ∪ B containing elements in A or B or both.

Universal Quantifier: The symbol ∀ meaning "for all."

Universe (Universal Set): The set of all elements under consideration in a particular context.

Vacuous Truth: A conditional statement that is true because its hypothesis is false.

Venn Diagram: A visual representation of set relationships using overlapping shapes.

Study Tips

Master these concepts through practice. Work problems daily, connect ideas across topics, and always understand why methods work, not just how to apply them. Discrete mathematics is the foundation of computer science—every algorithm, data structure, and complexity analysis builds on these principles.