Discrete Math for Computing

Introduction to Discrete Mathematics

Discrete mathematics is the branch of mathematics that deals with countable, distinct, and separable structures — the perfect mathematical language for computer science. Unlike continuous mathematics (calculus, differential equations) which deals with smooth, flowing quantities, discrete mathematics focuses on objects that can be counted, enumerated, and represented as finite sets.

Every computer scientist, software engineer, and data scientist relies on discrete mathematics daily. Boolean logic underlies every conditional statement in code. Set theory defines database queries and data structures. Graph theory powers social networks, routing algorithms, and recommendation systems. Combinatorics enables efficient algorithm design and performance analysis. Number theory secures our digital communications through cryptography. Probability drives machine learning and statistical analysis.

1. Propositional Logic: The Language of Reasoning

Logic is the foundation of mathematical reasoning and computer science. Propositional logic deals with statements that are either true or false, and the logical operations that combine them.

Logical Operators

• Negation (¬p): True when p is false, false when p is true
• Conjunction (p ∧ q): True only when both p and q are true
• Disjunction (p ∨ q): True when at least one of p or q is true
• Exclusive OR (p ⊕ q): True when exactly one of p or q is true
• Implication (p → q): "If p then q" — false only when p is true and q is false
• Biconditional (p ↔ q): True when p and q have the same truth value

// Logical operators in Python
p = True
q = False

print(not p)           # False (¬p)
print(p and q)         # False (p ∧ q)
print(p or q)          # True  (p ∨ q)
print(p != q)          # True  (p ⊕ q) XOR
print(not p or q)      # Implication p → q

Logical Equivalences

Understanding logical equivalences allows simplification of complex conditions:

• De Morgan's Laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
• Double Negation: ¬(¬p) ≡ p
• Distributive Laws: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
• Implication: p → q ≡ ¬p ∨ q

Predicate Logic

Predicate logic extends propositional logic with quantifiers, enabling reasoning about collections of objects:

• Universal Quantifier (∀x): "For all x" — all elements satisfy a property
• Existential Quantifier (∃x): "There exists x" — at least one element satisfies a property

# Predicate logic examples
∀x (Person(x) → HasHeart(x))   # All people have hearts
∃x (Student(x) ∧ Genius(x))     # There exists a student who is a genius

# Python equivalent
all(person.has_heart() for person in people)    # ∀
any(student.is_genius() for student in students) # ∃

2. Set Theory: The Mathematics of Collections

Sets are fundamental data structures in mathematics and computer science. A set is an unordered collection of distinct elements.

Set Operations

• Union (A ∪ B): Elements in A or B or both
• Intersection (A ∩ B): Elements in both A and B
• Difference (A \ B): Elements in A but not in B
• Complement (Aᶜ): Elements not in A (within universal set U)
• Cartesian Product (A × B): All ordered pairs (a, b) where a ∈ A, b ∈ B

Important Sets in Computer Science

• ℕ = {0, 1, 2, 3, ...}: Natural numbers
• ℤ = {..., -2, -1, 0, 1, 2, ...}: Integers
• ℝ: Real numbers
• {0,1}ⁿ: Binary strings of length n
• Powerset P(S): Set of all subsets of S (size 2^{|S|})

# Set operations in Python
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

print(A | B)   # Union: {1,2,3,4,5,6}
print(A & B)   # Intersection: {3,4}
print(A - B)   # Difference: {1,2}
print(A ^ B)   # Symmetric difference: {1,2,5,6}

3. Combinatorics: The Art of Counting

Combinatorics deals with counting, arranging, and selecting objects. It is essential for analyzing algorithm complexity, probability, and data structure performance.

3.1 Basic Counting Principles

• Product Rule: If task A can be done in m ways and task B in n ways, then doing both can be done in m × n ways
• Sum Rule: If tasks are mutually exclusive, total ways = m + n
• Pigeonhole Principle: If n items are placed into m boxes and n > m, at least one box contains multiple items

3.2 Permutations and Combinations

# Combinatorics in Python
import math

# Permutations: P(10,3)
perm = math.perm(10, 3)  # 720

# Combinations: C(10,3)
comb = math.comb(10, 3)  # 120

# Factorial: 5!
fact = math.factorial(5)  # 120

3.3 Binomial Theorem and Pascal's Triangle

The binomial theorem expands (x + y)ⁿ:

(x + y)ⁿ = Σ C(n, k) xⁿ⁻ᵏ yᵏ

For n = 3: (x + y)³ = x³ + 3x²y + 3xy² + y³

4. Graph Theory: Modeling Relationships

Graphs model pairwise relationships between objects. They are fundamental to networks, social media, routing algorithms, and dependency management.

Key Graph Concepts

• Vertices (Nodes): Objects in the graph
• Edges: Relationships between vertices (undirected or directed)
• Degree: Number of edges incident to a vertex
• Path: Sequence of vertices connected by edges
• Cycle: Path that starts and ends at same vertex
• Tree: Connected acyclic graph (n vertices, n-1 edges)
• Bipartite Graph: Vertices can be split into two sets with edges only between sets

Graph Algorithms

• Breadth-First Search (BFS): Shortest path in unweighted graphs
• Depth-First Search (DFS): Cycle detection, topological sorting
• Dijkstra's Algorithm: Shortest path in weighted graphs
• Kruskal's/Prim's Algorithm: Minimum spanning tree
• Topological Sort: Ordering of DAG (Directed Acyclic Graph) vertices

5. Number Theory: The Mathematics of Integers

Number theory is the study of integers and their properties. It forms the foundation of modern cryptography.

5.1 Divisibility and Modular Arithmetic

• a divides b (a | b): b = a·k for some integer k
• Modular arithmetic: a ≡ b (mod m) means m | (a - b)
• Properties: (a mod m + b mod m) mod m = (a + b) mod m

# Modular arithmetic in Python
print(17 % 5)     # 2 (remainder)
print(pow(2, 10, 1000))  # 24 (modular exponentiation: 2¹⁰ mod 1000)

5.2 Greatest Common Divisor (GCD)

The Euclidean algorithm efficiently computes GCD:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Example: gcd(48, 18) = 6

5.3 Prime Numbers and Factorization

Prime numbers are fundamental to cryptography. The Fundamental Theorem of Arithmetic states every integer > 1 has a unique prime factorization.

5.4 Cryptography Applications

• RSA Encryption: Uses large prime multiplication (easy) and factorization (hard)
• Diffie-Hellman Key Exchange: Based on discrete logarithm problem
• Hash Functions: Use modular arithmetic for data integrity

6. Probability: Quantifying Uncertainty

Probability theory is essential for machine learning, randomized algorithms, and system reliability analysis.

6.1 Basic Probability Concepts

• Sample Space (S): Set of all possible outcomes
• Event (E): Subset of the sample space
• Probability P(E): |E| / |S| (for equally likely outcomes)
• P(¬E) = 1 - P(E)
• P(A ∪ B) = P(A) + P(B) - P(A ∩ B)

# Probability of rolling a sum of 7 with two dice
outcomes = [(i, j) for i in range(1,7) for j in range(1,7)]
success = sum(1 for i,j in outcomes if i+j == 7)
probability = success / len(outcomes)  # 6/36 = 1/6 ≈ 0.1667

6.2 Conditional Probability and Bayes' Theorem

Conditional probability: P(A|B) = P(A ∩ B) / P(B)

Bayes' Theorem: P(A|B) = P(B|A)·P(A) / P(B)

6.3 Random Variables and Expectation

• Expected Value: E[X] = Σ x·P(X=x)
• Linearity of Expectation: E[X+Y] = E[X] + E[Y] (always true)
• Variance: Var(X) = E[(X-μ)²] = E[X²] - E[X]²

6.4 Common Probability Distributions

• Uniform Distribution: Equal probability for all outcomes
• Binomial Distribution: Number of successes in n independent trials
• Poisson Distribution: Events occurring in fixed interval
• Normal Distribution: Continuous distribution (Central Limit Theorem)

7. Proof Techniques: Mathematical Reasoning

Proofs are the foundation of mathematical certainty. Computer scientists use proof techniques to verify algorithms, data structures, and system properties.

7.1 Direct Proof

Assume hypothesis, logically derive conclusion.

Theorem: If n is even, then n² is even.
Proof: If n is even, n = 2k for some integer k.
Then n² = (2k)² = 4k² = 2(2k²), which is even. ∎

7.2 Proof by Contradiction

Assume the negation of the conclusion, derive a contradiction.

Theorem: √2 is irrational.
Proof: Assume √2 = a/b in lowest terms.
Then 2 = a²/b² → a² = 2b², so a is even → a=2c.
Then (2c)² = 2b² → 4c² = 2b² → 2c² = b², so b is even.
Contradiction (a/b not in lowest terms). ∎

7.3 Proof by Induction

Mathematical induction proves statements for all natural numbers:

1. Base Case: Prove P(1) is true
2. Inductive Step: Assume P(k) true, prove P(k+1) true

Theorem: Sum of first n integers = n(n+1)/2
Base: n=1: 1 = 1(2)/2 = 1 ✓
Inductive: Assume 1+2+...+k = k(k+1)/2
Then 1+2+...+k+(k+1) = k(k+1)/2 + (k+1)
= (k+1)(k/2 + 1) = (k+1)(k+2)/2 ✓

7.4 Proof by Contrapositive

To prove p → q, prove ¬q → ¬p (logically equivalent).

8. Applications in Computer Science

8.1 Algorithms and Data Structures

• Binary Search: O(log n) time — divide-and-conquer
• Hash Tables: Use modular arithmetic and prime numbers
• Heaps: Tree structure with heap property
• Graph Algorithms: BFS, DFS, Dijkstra's, A*

8.2 Database Theory

• Relational Algebra: Set operations on relations
• Normalization: Functional dependencies and set theory

8.3 Machine Learning

• Linear Regression: Linear algebra and statistics
• Decision Trees: Tree structures and entropy (information theory)
• Neural Networks: Graph theory and probability

8.4 Cryptography and Security

• RSA: Number theory, modular arithmetic, primes
• Elliptic Curve Cryptography: Algebraic geometry
• Hash Functions: Modular arithmetic, probability

8.5 Formal Verification

Using logic and proof techniques to verify that software behaves correctly. Tools like Coq, Isabelle, and TLA+ enable mathematical verification of critical systems.

Conclusion

Discrete mathematics is not merely abstract theory — it is the working language of computer science. Every conditional statement in code reflects propositional logic. Every database query is a set operation. Every social network recommendation relies on graph theory. Every secure transaction depends on number theory. Every machine learning prediction involves probability.

Mastering these mathematical foundations enables you to understand why algorithms work, analyze their efficiency, and design new solutions to computational problems. Whether you're building the next generation of AI systems, securing digital infrastructure, or developing scalable software, discrete mathematics provides the intellectual tools you need.