Discrete Mathematics

Discrete mathematics deals with countable, distinct objects. While not as central as calculus or linear algebra, it's valuable for understanding algorithms, complexity, and certain AI architectures.

Why it matters: Graph neural networks, combinatorial optimization, and algorithm analysis all rely on discrete math concepts.

Logic & Proofs

Propositional Logic

Statements that are true or false.

P: "It is raining"
Q: "I have an umbrella"
P ∧ Q: Both are true
P ∨ Q: At least one is true

Logical Operators

Combine and modify propositions.

∧ (AND), ∨ (OR), ¬ (NOT)
→ (implies), ↔ (if and only if)
⊕ (XOR)

Graph Theory

Graphs model relationships between objects. Essential for social networks, knowledge graphs, and Graph Neural Networks (GNNs).

Graph Basics

G = (V, E) where V is vertices (nodes) and E is edges (connections).

Directed: Edges have direction

Undirected: Edges are bidirectional

Weighted: Edges have values

Cyclic: Contains loops

Graph Algorithms

BFS: Breadth-first search

DFS: Depth-first search

Dijkstra: Shortest path

PageRank: Node importance

AI Applications

Graph Neural Networks (GNNs) for molecular property prediction
Knowledge graphs for reasoning and QA systems
Social network analysis
Recommendation systems (user-item graphs)

Combinatorics

The mathematics of counting. Important for understanding complexity and probability.

Permutations

Arrangements where order matters.

P(n, k) = n! / (n-k)!
Example: 5 people, 3 positions
P(5, 3) = 60 ways

Combinations

Selections where order doesn't matter.

C(n, k) = n! / (k!(n-k)!)
Example: Choose 3 from 5
C(5, 3) = 10 ways

Set Theory

Foundation of mathematics. Sets are collections of distinct objects.

∪ (Union): A ∪ B = all elements in A or B

∩ (Intersection): A ∩ B = elements in both

− (Difference): A − B = in A but not B

⊆ (Subset): A ⊆ B = all of A is in B

∅ (Empty set): Set with no elements

|A| (Cardinality): Number of elements

Complexity Theory

Understanding algorithm efficiency using Big O notation.

O(1)

Constant

Array access

O(log n)

Logarithmic

Binary search

O(n)

Linear

Loop through array

O(n log n)

Linearithmic

Merge sort

O(n²)

Quadratic

Nested loops

O(2ⁿ)

Exponential

Recursive fib

AI Relevance

▹Graph Neural Networks use graph theory

▹Complexity analysis for algorithm efficiency

▹Combinatorics in search spaces and optimization

▹Logic in knowledge representation and reasoning

▹Set theory in data structures and databases

▹Boolean algebra in neural network activations

Key Takeaway: While less central than calculus or linear algebra, discrete math is essential for graph-based AI, algorithm design, and computational complexity.