Introduction to Discrete Mathematics
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. Unlike real numbers which have the property of varying "smoothly", discrete mathematics deals with objects that can assume only distinct, separated values.
Why Study Discrete Mathematics?
- Foundation for computer science and programming
- Essential for algorithm design and analysis
- Used in cryptography and network security
- Basis for database theory and digital circuits
- Critical for combinatorics and optimization problems
Discrete vs. Continuous
This visualization shows the difference between discrete and continuous structures:
Discrete vs. Continuous Visualization
Logic and Proofs
Definition: Proposition
A proposition is a declarative sentence that is either true or false, but not both. Examples: "2 + 2 = 4" (true), "The moon is made of cheese" (false).
Logical Connectives
Compound propositions are formed from existing propositions using logical operators:
| Operator | Symbol | Name | Description |
|---|---|---|---|
| Negation | ¬p | NOT | True when p is false |
| Conjunction | p ∧ q | AND | True when both p and q are true |
| Disjunction | p ∨ q | OR | True when at least one of p or q is true |
| Implication | p → q | IF-THEN | False only when p is true and q is false |
| Biconditional | p ↔ q | IFF | True when p and q have the same truth value |
Example: Truth Table
Truth table for p → q:
|---|---|-------|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Definition: Tautology and Contradiction
A tautology is a compound proposition that is always true (e.g., p ∨ ¬p). A contradiction is a compound proposition that is always false (e.g., p ∧ ¬p).
Logical Equivalences
Two propositions are logically equivalent if they have the same truth value in all cases (≡). Important equivalences:
| Name | Equivalence |
|---|---|
| Identity Laws | p ∧ T ≡ p, p ∨ F ≡ p |
| Domination Laws | p ∨ T ≡ T, p ∧ F ≡ F |
| Idempotent Laws | p ∨ p ≡ p, p ∧ p ≡ p |
| Double Negation | ¬(¬p) ≡ p |
| Commutative Laws | p ∨ q ≡ q ∨ p, p ∧ q ≡ q ∧ p |
| Associative Laws | (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) |
| Distributive Laws | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
| De Morgan's Laws | ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| Implication | p → q ≡ ¬p ∨ q |
Methods of Proof
Theorem: Proof Techniques
- Direct Proof: Assume p is true and show q must be true
- Contrapositive: Prove ¬q → ¬p instead of p → q
- Contradiction: Assume p ∧ ¬q and derive a contradiction
- Induction: Show base case and that P(k) → P(k+1)
- Counterexample: To disprove ∀xP(x), find one x where P(x) is false
Set Theory
Definition: Set
A set is an unordered collection of distinct objects, called elements or members. Sets can be defined by listing elements (A = {1, 2, 3}) or with a rule (B = {x | x is even}).
Basic Set Operations
| Operation | Notation | Definition |
|---|---|---|
| Union | A ∪ B | {x | x ∈ A or x ∈ B} |
| Intersection | A ∩ B | {x | x ∈ A and x ∈ B} |
| Difference | A \ B | {x | x ∈ A and x ∉ B} |
| Complement | A' or Ā | {x | x ∉ A} (relative to universal set) |
| Cartesian Product | A × B | {(a,b) | a ∈ A and b ∈ B} |
Example: Set Operations
Let A = {1, 2, 3}, B = {2, 3, 4}:
Union: A ∪ B = {1, 2, 3, 4}
Intersection: A ∩ B = {2, 3}
Difference: A \ B = {1}
Cartesian Product: A × B = {(1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,2), (3,3), (3,4)}
Theorem: Set Identities
- Identity Laws: A ∪ ∅ = A, A ∩ U = A
- Domination Laws: A ∪ U = U, A ∩ ∅ = ∅
- Idempotent Laws: A ∪ A = A, A ∩ A = A
- Commutative Laws: A ∪ B = B ∪ A, A ∩ B = B ∩ A
- Associative Laws: (A ∪ B) ∪ C = A ∪ (B ∪ C)
- Distributive Laws: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
- De Morgan's Laws: (A ∪ B)' = A' ∩ B', (A ∩ B)' = A' ∪ B'
- Absorption Laws: A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A
Cardinality and Power Sets
Definition: Cardinality
The cardinality of a set A (|A|) is the number of distinct elements in A. A set is finite if its cardinality is a natural number, infinite otherwise.
Definition: Power Set
The power set of a set S (P(S)) is the set of all subsets of S, including the empty set and S itself. If |S| = n, then |P(S)| = 2ⁿ.
Example: Power Set
For S = {a, b}:
P(S) = {∅, {a}, {b}, {a, b}}
|S| = 2 ⇒ |P(S)| = 4 = 2²
Relations and Functions
Definition: Relation
A relation R from set A to set B is a subset of A × B. A relation on A is a subset of A × A. We write aRb if (a,b) ∈ R.
Properties of Relations
| Property | Definition |
|---|---|
| Reflexive | ∀a ∈ A, aRa |
| Symmetric | ∀a,b ∈ A, aRb ⇒ bRa |
| Antisymmetric | ∀a,b ∈ A, aRb ∧ bRa ⇒ a = b |
| Transitive | ∀a,b,c ∈ A, aRb ∧ bRc ⇒ aRc |
Definition: Equivalence Relation
An equivalence relation is a relation that is reflexive, symmetric, and transitive. Equivalence relations partition sets into equivalence classes.
Definition: Partial Order
A partial order is a relation that is reflexive, antisymmetric, and transitive. A set with a partial order is called a poset.
Definition: Function
A function f: A → B is a relation where each element of A appears exactly once as the first component of an ordered pair. A is the domain, B is the codomain.
Types of Functions
| Type | Definition |
|---|---|
| Injective (1-1) | f(a) = f(b) ⇒ a = b |
| Surjective (onto) | ∀b ∈ B, ∃a ∈ A with f(a) = b |
| Bijective | Both injective and surjective |
Example: Function Types
f: ℝ → ℝ, f(x) = x² is neither injective nor surjective.
f: ℝ → ℝ⁺, f(x) = x² is surjective but not injective.
f: ℝ⁺ → ℝ⁺, f(x) = x² is bijective.
Combinatorics
Definition: Combinatorics
Combinatorics is the branch of mathematics concerning the study of finite or countable discrete structures, particularly counting, arrangement, and combination.
Basic Counting Principles
Theorem: Product Rule
If a procedure can be broken into two tasks with n₁ ways to do the first and n₂ ways to do the second, then there are n₁ × n₂ ways to do the procedure.
Theorem: Sum Rule
If a task can be done either in n₁ ways or in n₂ ways (non-overlapping), then there are n₁ + n₂ ways to do the task.
Example: Counting
How many bit strings of length 8 either start with 1 or end with 00?
Solution:
Start with 1: 2⁷ = 128
End with 00: 2⁶ = 64
Both: 2⁵ = 32
Total = 128 + 64 - 32 = 160
Permutations and Combinations
Definition: Permutation
A permutation is an ordered arrangement of elements. The number of permutations of r objects from n distinct objects is P(n,r) = n!/(n-r)!
Definition: Combination
A combination is an unordered selection of elements. The number of combinations of r objects from n distinct objects is C(n,r) = n!/(r!(n-r)!)
Example: Permutations vs. Combinations
How many ways to choose a president and vice president from 10 people? (Order matters)
P(10,2) = 10 × 9 = 90
How many ways to choose a committee of 2 from 10 people? (Order doesn't matter)
C(10,2) = 45
Binomial Theorem
Theorem: Binomial Theorem
For any positive integer n:
Example: Binomial Expansion
(x + y)³ = C(3,0)x³ + C(3,1)x²y + C(3,2)xy² + C(3,3)y³ = x³ + 3x²y + 3xy² + y³
Graph Theory
Definition: Graph
A graph G = (V, E) consists of a non-empty set V of vertices (nodes) and a set E of edges (links between vertices).
Graph Example
Visual representation of a graph with 4 vertices and 5 edges:
Graph Visualization
Graph Terminology
| Term | Definition |
|---|---|
| Simple Graph | No loops or multiple edges |
| Multigraph | May have multiple edges |
| Pseudograph | May have loops and multiple edges |
| Directed Graph | Edges have direction (arcs) |
| Weighted Graph | Edges have numerical weights |
| Degree | Number of edges incident to a vertex |
| Path | Sequence of edges between two vertices |
| Cycle | Path that starts and ends at same vertex |
| Connected | Path exists between any two vertices |
Theorem: Handshaking Lemma
In any graph, the sum of all vertex degrees is equal to twice the number of edges:
This implies the number of vertices with odd degree must be even.
Special Graphs
| Graph | Description |
|---|---|
| Complete (Kₙ) | Every pair of distinct vertices is connected |
| Cycle (Cₙ) | Single cycle through all vertices |
| Wheel (Wₙ) | Cycle with additional central vertex |
| Bipartite | Vertices divided into two sets with edges only between sets |
| Tree | Connected graph with no cycles |
| Planar | Can be drawn without edge crossings |
Theorem: Euler's Formula
For any connected planar graph with V vertices, E edges, and F faces:
Applications of Discrete Mathematics
Computer Science
Discrete mathematics is fundamental to computer science:
- Algorithm design and analysis
- Data structures (trees, graphs, hash tables)
- Computability and complexity theory
- Cryptography and security
- Database theory and design
Operations Research
Applications in optimization and decision making:
- Network flow problems
- Scheduling and resource allocation
- Inventory management
- Transportation and logistics
Biology
Discrete models in biological sciences:
- Phylogenetic trees in evolutionary biology
- Gene regulatory networks
- Protein-protein interaction networks
- Population genetics
Social Sciences
Applications in modeling social systems:
- Social network analysis
- Voting systems and preference ranking
- Game theory and economic models
- Language and automata theory
Exercises and Problems
Exercise 1: Logic and Proofs
-
Construct truth tables for:
- (p ∧ q) → r
- ¬(p ∨ q) ↔ (¬p ∧ ¬q)
Solution:
a) Truth table for (p ∧ q) → r:
| p | q | r | p ∧ q | (p ∧ q) → r |
|---|---|---|-------|-------------|
| T | T | T | T | T |
| T | T | F | T | F |
| T | F | T | F | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | T | F | F | T |
| F | F | T | F | T |
| F | F | F | F | T |b) This is De Morgan's Law, which is a tautology (always true).
-
Prove that if n is an odd integer, then n² is odd.
Solution:
Let n be odd. Then n = 2k + 1 for some integer k.
n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
This is of the form 2m + 1 (where m = 2k² + 2k), hence odd.
Exercise 2: Combinatorics
-
How many strings of 8 English letters are there:
- If letters can be repeated?
- If no letters can be repeated?
- That start with X and letters can be repeated?
- That contain exactly one vowel (A,E,I,O,U) and letters can be repeated?
Solution:
a) 26⁸ (each position has 26 possibilities)
b) P(26,8) = 26 × 25 × ... × 19
c) 1 × 26⁷ (first letter fixed as X, others free)
d) Choose position for vowel (8 choices), choose vowel (5), other letters (21⁷): 8 × 5 × 21⁷
Exercise 3: Graph Theory
-
For the complete graph Kₙ:
- How many edges does it have?
- What is the degree of each vertex?
- For what values of n is Kₙ Eulerian?
Solution:
a) C(n,2) = n(n-1)/2 edges
b) n-1 edges per vertex (connected to all others)
c) Kₙ is Eulerian when n is odd (all vertices have even degree n-1)
Lesson Summary
- Discrete mathematics deals with distinct, separated objects
- Propositional logic studies truth values of compound statements
- Set theory provides foundation for discrete structures
- Relations describe connections between set elements
- Functions are special types of relations
- Combinatorics counts arrangements and selections
- Graph theory models pairwise relationships
- Proof techniques establish mathematical truths
- Discrete math is fundamental to computer science
- Counting principles include product and sum rules
- Permutations count ordered arrangements
- Combinations count unordered selections
- Graphs can model networks and relationships
- Trees are connected acyclic graphs
- Planar graphs can be drawn without edge crossings