Discrete Math | Index

Discrete math is the math of separate, countable things: true-or-false statements, whole numbers, finite sets and networks of points and lines.

The course covers logic and proofs, sets and functions, number theory, counting, recurrence relations, relations, graph theory and trees, and ends with Boolean algebra and Big-O notation.

It’s for college students in computer science and math, where discrete math is usually a first- or second-year requirement.

What to know first: Algebra 2, plus permutations, combinations and mathematical induction in Precalculus, Unit 7. No calculus is needed.

Lessons for this course are coming soon. The list below shows every planned lesson in teaching order.

Units in this course

Unit 1: Logic

  1. Propositional Logic (coming soon) — statements, connectives and how to translate English sentences into symbols
  2. Truth Tables (coming soon) — build truth tables and spot tautologies and contradictions
  3. Logical Equivalence (coming soon) — show two statements are equivalent with De Morgan’s laws and other laws of logic
  4. Predicates and Quantifiers (coming soon) — use “for all” and “there exists” and negate quantified statements
  5. Rules of Inference (coming soon) — decide whether an argument is valid with modus ponens and other rules

Also see: conditional statements and inductive and deductive reasoning (Geometry).

Unit 2: Methods of Proof

  1. Direct Proof (coming soon) — prove statements about even, odd and divisible numbers step by step
  2. Proof by Contrapositive (coming soon) — prove “if P, then Q” by proving “if not Q, then not P”
  3. Proof by Contradiction (coming soon) — prove a statement by showing that its negation leads to something impossible
  4. Strong Induction (coming soon) — prove statements where each case depends on several earlier cases

Also see: mathematical induction (Precalculus) and two-column proofs (Geometry).

Unit 3: Sets and Functions

  1. Sets and Subsets (coming soon) — set-builder notation, subsets and the empty set
  2. Set Operations (coming soon) — union, intersection, difference and complement, with Venn diagrams
  3. Power Sets and Cartesian Products (coming soon) — list every subset of a set and every ordered pair from two sets
  4. Injective, Surjective and Bijective Functions (coming soon) — tell one-to-one, onto and bijective functions apart
  5. Countable and Uncountable Sets (coming soon) — compare the sizes of infinite sets and see why the real numbers are uncountable

Also see: relations and functions and inverse functions (Algebra 1 and Algebra 2).

Unit 4: Number Theory

  1. Divisibility and the Division Algorithm (coming soon) — the definition of a | b, its properties, and quotients and remainders
  2. Euclidean Algorithm (coming soon) — find the greatest common divisor and write it as a combination of the two numbers
  3. Modular Arithmetic (coming soon) — add, subtract, multiply and take powers with remainders
  4. Linear Congruences (coming soon) — solve congruences like 7x ≡ 3 (mod 10) with modular inverses
  5. Chinese Remainder Theorem (coming soon) — solve a system of congruences with different moduli
  6. Fermat’s Little Theorem (coming soon) — simplify large powers mod a prime
  7. RSA Encryption (coming soon) — how public-key encryption uses primes and modular arithmetic

Also see: prime factorization, the greatest common factor and the least common multiple (Pre-Algebra).

Unit 5: Counting

  1. Sum and Product Rules for Counting (coming soon) — add the counts for “or” choices and multiply them for “and” choices
  2. Pigeonhole Principle (coming soon) — prove that two items must share a box when there are more items than boxes
  3. Combinations with Repetition (coming soon) — count selections that allow repeats with stars and bars
  4. Inclusion-Exclusion Principle (coming soon) — count the union of overlapping sets without double counting

Also see: permutations and combinations and the binomial theorem (Precalculus).

Unit 6: Recurrence Relations

  1. Recurrence Relations (coming soon) — define a sequence by its earlier terms and find terms by iterating
  2. Solving Linear Recurrence Relations (coming soon) — find a closed formula with the characteristic roots
  3. Generating Functions (coming soon) — encode a sequence as a power series to count and solve recurrences

Also see: arithmetic sequences and geometric sequences (Algebra 1).

Unit 7: Relations

  1. Properties of Relations (coming soon) — reflexive, symmetric, antisymmetric and transitive relations
  2. Equivalence Relations (coming soon) — equivalence classes and how they split a set into parts
  3. Partial Orders (coming soon) — partially ordered sets and Hasse diagrams

Unit 8: Graph Theory

  1. Graph Theory Basics (coming soon) — vertices, edges, degrees and the handshaking lemma
  2. Graph Isomorphism (coming soon) — represent graphs with adjacency matrices and lists and decide whether two graphs are the same
  3. Bipartite Graphs (coming soon) — recognize bipartite and complete bipartite graphs
  4. Euler Paths and Circuits (coming soon) — decide when a route can use every edge exactly once
  5. Hamilton Paths and Circuits (coming soon) — routes that visit every vertex exactly once
  6. Graph Coloring (coming soon) — color a map or graph and find its chromatic number
  7. Planar Graphs (coming soon) — draw graphs with no crossings and use Euler’s formula v − e + f = 2 for connected planar graphs
  8. Dijkstra’s Algorithm (coming soon) — find the shortest path in a graph with nonnegative edge weights

Unit 9: Trees

  1. Trees in Graph Theory (coming soon) — the properties of trees and rooted trees
  2. Minimum Spanning Trees (coming soon) — connect every vertex at the lowest total cost with Kruskal’s and Prim’s algorithms
  3. Tree Traversal (coming soon) — visit every node of a binary tree in preorder, inorder and postorder

Unit 10: Boolean Algebra and Algorithms

  1. Boolean Algebra (coming soon) — simplify expressions with the laws of Boolean algebra
  2. Logic Gates (coming soon) — build and simplify circuits with AND, OR and NOT gates
  3. Big-O Notation (coming soon) — compare how fast functions and algorithms grow

For Teachers: Standards Alignment

Lessons follow a typical one-semester college course in discrete mathematics (sometimes called discrete structures), required for most computer science majors and many math majors. There is no AP exam for this course. Permutations, combinations, the binomial theorem and mathematical induction are taught in Precalculus, Unit 7.

Previous course: Differential Equations Index · Next course: Finite Math and Business Calculus Index