Math Ladder · College

Discrete Math

Logic and proof techniques, sets, functions and relations, counting, induction and recurrences, and graphs: the math of separate, countable things.

0 of 50 topics passed

Start this course Skill map

50 topics in 7 units. Builds on Algebra 2 and Precalculus and Trigonometry and Probability and Statistics. Leads to Number Theory, Real Analysis and Abstract Algebra. Not sure this is the right course? Find your rung.

  • Passed
  • Review due
  • Learning
  • Ready to learn
  • Needs an earlier topic

Unit 1 Logic

8 topics

Read and build compound statements, truth tables, quantifiers and valid arguments.

  1. Statements and Connectives
  2. Truth Tables
  3. The Conditional and the Biconditional
  4. Logical Equivalence and De Morgan's Laws
  5. Quantifiers
  6. Negating Quantified Statements
  7. Nested Quantifiers
  8. Valid Arguments and Rules of Inference

Unit 2 Proof Techniques

5 topics

Test claims with counterexamples, then set up direct, contrapositive, case-by-case and contradiction arguments.

  1. Disproving with a Counterexample
  2. Direct Proof
  3. Proof by Contrapositive
  4. Proof by Cases
  5. Proof by Contradiction

Unit 3 Sets and Functions

6 topics

Describe collections precisely, combine them, and study functions between them.

  1. Sets and Set-Builder Notation
  2. Set Operations
  3. Power Sets and Cartesian Products
  4. Functions Between Sets
  5. One-to-One and Onto Functions
  6. Bijections and Inverse Functions

Unit 4 Relations

3 topics

Describe how elements are related, sort them into classes, and put them in order.

  1. Relations and Their Properties
  2. Equivalence Relations and Partitions
  3. Partial Orders and Hasse Diagrams

Unit 5 Counting

9 topics

Count arrangements and selections without listing them: rules, complements, inclusion–exclusion, stars and bars, and pigeonholes.

  1. The Sum and Product Rules
  2. Counting the Complement
  3. Inclusion–Exclusion
  4. The Division Rule: Repeated Letters and Round Tables
  5. Pascal's Identity and Counting Arguments
  6. Lattice Paths and Binary Strings
  7. Stars and Bars
  8. The Pigeonhole Principle
  9. Derangements

Unit 6 Induction, Recursion and Growth

7 topics

Prove statements for every whole number, set up and solve recurrence relations, and compare how fast functions grow.

  1. Induction for Divisibility and Inequalities
  2. Strong Induction
  3. Setting Up Recurrence Relations
  4. Solving Recurrences by Unrolling
  5. Linear Recurrences with Distinct Roots
  6. Linear Recurrences with a Repeated Root
  7. Growth Rates and Big-O

Unit 7 Graph Theory

12 topics

Model connections with graphs: degrees, paths and circuits, trees, shortest routes, coloring and planarity.

  1. Graphs, Degrees and the Handshake Lemma
  2. Complete, Bipartite and Cycle Graphs
  3. Walks, Paths, Cycles and Connectivity
  4. Adjacency Matrices and Counting Walks
  5. Graph Isomorphism
  6. Euler Paths and Circuits
  7. Hamilton Paths and Cycles
  8. Trees
  9. Minimum Spanning Trees
  10. Shortest Paths with Dijkstra's Algorithm
  11. Graph Coloring
  12. Planar Graphs and Euler's Formula
@teddyrookbook GitHub