What discrete math topics are covered in this free course?

The course covers sets, functions, logic, proofs, sequences, induction, relations, probability, counting, Markov chains, linear programming, and graph theory.

How do truth tables help prove logical equivalence?

Two statements are logically equivalent when their truth-table columns have the same truth value in every possible case.

What proof methods are taught in the discrete mathematics course?

You will practice direct proof, proof by cases, contrapositive, contradiction, mathematical induction, strong induction, and counterexamples.

Free online course Discrete Math

Duration of the online course: 9 hours and 38 minutes

New

Build proof skills and sharp logical reasoning with this free discrete math course—sets, functions, induction, counting, and probability, plus a certificate option.

In this free course, learn about

Distinguish discrete vs continuous math and the role of rigorous reasoning
Use set notation (roster/builder), empty set, union/intersection/complement, power sets
Work with Cartesian products, ordered pairs, relations, inverses, and functions (formal tests)
Build truth tables; use equivalences, tautologies/contradictions, DeMorgan’s laws
Analyze conditionals: converse/inverse/contrapositive, vacuous truth, necessary/sufficient
Apply inference rules (e.g., modus ponens) and assess argument validity
Use predicates, truth sets, quantifiers; correctly negate quantified statements
Write formal definitions (even/odd, rational) and prove/disprove via counterexamples
Execute proof methods: direct, cases, contradiction, contrapositive, induction/strong induction
Use modular arithmetic and classic number theory proofs (e.g., infinitely many primes)
Define sequences (including recursive) and compute with sums/products; Fibonacci basics
Counting: permutations, combinations, inclusion-exclusion; connect counting to probability
Probability: conditional probability, independence, Bayes’ theorem; interpret tables/tests
Model Markov chains (transition matrices) and core graph theory (degrees, Euler paths)

About the free online course

Discrete mathematics is where careful thinking becomes a skill you can apply everywhere: in calculus-style reasoning, in computer science, in data and probability, and in any subject that depends on clear definitions and airtight arguments. This free online course is designed to help you move from intuitive math to rigorous math, building confidence with the language and tools used to write, read, and test mathematical claims.

You will start by learning how mathematicians describe collections and structure: sets, notation, the empty set, Cartesian products, and relations. From there, the course turns those building blocks into the idea of a function, showing how domain and range interact and how to decide whether a rule truly behaves like a function. Along the way, you will practice translating everyday statements into precise mathematical form, a key step toward stronger problem solving.

A major theme is logic. You will learn to analyze statements with truth tables, recognize equivalence, and work comfortably with conditionals, contrapositives, and biconditionals. You will also develop fluency with quantifiers and predicates, including how to negate complex claims correctly. These tools prepare you to judge arguments for validity and to avoid common traps such as confusing a statement with its converse or mishandling vacuous truth.

Once the logic is in place, the focus shifts to proof. You will see how definitions drive reasoning and how different strategies fit different problems: direct proof, counterexamples, proof by cases, contradiction, and contrapositive. Topics like parity, divisibility, rational numbers, modular arithmetic, and classic results about primes provide concrete practice so that proof writing becomes structured rather than mysterious.

The course then broadens into sequences and induction, including strong induction and recursion, with memorable examples that connect symbolic rules to patterns over time. Finally, you will build counting and probability intuition through permutations, combinations, conditional probability, Bayes’ theorem, and an introduction to Markov chains. You will also get a first look at graph theory and linear programming, tying discrete thinking to real decision-making and network-style problems.

By the end, you will be able to define objects precisely, translate words into symbols, test logical forms, and construct proofs that stand up to scrutiny—skills that strengthen performance in higher math and open doors to more advanced topics in computing and quantitative fields.

Course content

Video class: Intro to Discrete Math - Welcome to the Course! 05m
Exercise: What distinguishes discrete mathematics from continuous mathematics in this course context
Video class: Intro to Sets | Examples, Notation 07m
Video class: Set-Roster vs Set-Builder notation 05m
Exercise: Which set builder notation matches the roster ..., -4, -2, 0, 2, 4, ...?
Video class: The Empty Set 04m
Video class: Cartesian Product of Two Sets A x B 07m
Exercise: When are two ordered pairs equal
Video class: Relations between two sets | Definition First Examples 06m
Video class: The intuitive idea of a function 05m
Exercise: Which statement correctly defines a function in terms of domain and range?
Video class: Formal Definition of a Function using the Cartesian Product 05m
Video class: Example: Is this relation a function? 05m
Exercise: Is the relation C = {(x,y) in R×R | x^2 + y^2 = 1} a function from [-1,1] to [-1,1]?

Video class: Intro to Logical Statements 06m
Video class: Intro to Truth Tables | Negation, Conjunction, and Disjunction 05m
Exercise: When is the conjunction P and Q true?
Video class: Truth Table Example: ~p V ~q 03m
Video class: Logical Equivalence of Two Statements 03m
Exercise: Identify a logical equivalence using truth tables
Video class: Tautologies and Contradictions 03m
Video class: 3 Ways to Show a Logical Equivalence | Ex: DeMorgan's Laws 05m
Exercise: Simplify the expression: ¬(p ∨ ¬q) ∧ T using logical equivalences

Video class: Conditional Statements: if p then q 07m
Video class: Vacuously True Statements 02m
Exercise: Understanding vacuous truth in implications
Video class: Negating a Conditional Statement 02m
Video class: Contrapositive of a Conditional Statement 05m
Exercise: Which statement is logically equivalent to the conditional P → Q?
Video class: The converse and inverse of a conditional statement 05m
Video class: Biconditional Statements | if and only if 02m
Exercise: Which option is logically equivalent to p iff q
Video class: Logical Arguments - Modus Ponens 08m
Video class: Logical Argument Forms: Generalizations, Specialization, Contradiction 03m
Exercise: Which inference rule is used in the step From P infer P ∨ Q
Video class: Analyzing an argument for validity 02m

Video class: Predicates and their Truth Sets 06m
Exercise: Which set is the truth set of the predicate P(x): x is a factor of 12, with domain the positive integers?
Video class: Universal and Existential Quantifiers, ? For All and ? There Exists 09m
Video class: Negating Universal and Existential Quantifiers 08m
Exercise: Negate the statement For all x in Z+, x > 3
Video class: Negating Logical Statements with Multiple Quantifiers 08m
Video class: Universal Conditionals P(x) implies Q(x) 03m
Exercise: Which formalization correctly expresses the statement Every president of the United States is a US citizen given domain all people, P x means x is president of the United States, C x means x is a US citizen
Video class: Necessary and Sufficient Conditions 07m
Video class: Formal Definitions in Math | Ex: Even 03m
Exercise: Formal definition of odd integers

Video class: How to Prove Math Theorems | 1st Ex: Even Odd = Odd 08m
Video class: Step-By-Step Guide to Proofs | Ex: product of two evens is even 18m
Exercise: Choose the correct formalization of the statement The product of two even integers is even
Video class: Rational Numbers | Definition First Proof 06m
Video class: Proving that divisibility is transitive 11m
Exercise: Transitivity of Divisibility
Video class: Disproving implications with Counterexamples 08m
Video class: Proof by Division Into Cases 05m
Exercise: Which proof strategy shows that for any integer n, n squared has the same parity as n by analyzing the even and odd cases separately?
Video class: Proof by Contradiction | Method 09m
Video class: Proof by Contrapositive | Method 03m
Exercise: Which statement is the contrapositive of the claim If n^2 is even then n is even?
Video class: Quotient-Remainder Theorem and Modular Arithmetic 09m
Video class: Proof: There are infinitely many primes numbers 07m
Exercise: Infinitely Many Primes via Product Plus One

Video class: Introduction to sequences 06m
Video class: The formal definition of a sequence. 03m
Exercise: Formal definition of a sequence
Video class: The sum and product of finite sequences 09m
Video class: Intro to Mathematical Induction 12m
Exercise: Identify the two required components of a valid mathematical induction proof for statements Pn for all n greater or equal to a
Video class: Induction Proofs Involving Inequalities. 06m
Video class: Strong Induction // Intro and Full Example 10m
Exercise: What is the inductive hypothesis used in strong induction to prove P(n) for n ≥ a?
Video class: Recursive Sequences 07m
Video class: The Miraculous Fibonacci Sequence 06m
Exercise: Given F1=1, F2=1 and for n>=3, F_n = F_{n-1} + F_{n-2}, what is F6?

Video class: Prove A is a subset of B with the ELEMENT METHOD 06m
Video class: Proving equalities of sets using the element method 03m
Exercise: Which set identity is correct based on logical equivalences?
Video class: The union of two sets 05m
Video class: The Intersection of Two Sets 05m
Exercise: Find A ∩ B where A = {n in Z : n = 2p} and B = {n in Z : n = 3q}
Video class: Universes and Complements in Set Theory 02m
Video class: Using the Element Method to prove a Set Containment w/ Modus Tollens 03m
Exercise: Given A ⊆ B, which containment must be true?
Video class: Power Sets and the Cardinality of the Continuum 14m
Video class: Relations and their Inverses 02m
Exercise: Definition of an Inverse Relation
Video class: Reflexive, Symmetric, and Transitive Relations on a Set 06m
Video class: Equivalence Relations - Reflexive, Symmetric, and Transitive 04m
Exercise: Transitivity in Modular Arithmetic Equivalence
Video class: You need to check EVERY spot for reflexivity, symmetry, and transitivity 03m

Video class: Introduction to probability // Events, Sample Space, Formula, Independence 08m
Exercise: Probability of exactly one head in two fair coin flips
Video class: Example: Computing Probabilities using P(E)=N(E)/N(S) 02m
Video class: What is the probability of guessing a 4 digit pin code? 06m
Exercise: What is the probability of correctly guessing a 4-digit PIN on the first try?
Video class: Counting with Triple Intersections // Example 11m
Video class: Permutations: How many ways to rearrange the letters in a word? 06m
Exercise: How many length-4 permutations can be formed from 7 distinct letters without repetition?
Video class: The summation rule for disjoint unions 05m
Video class: Counting formula for two intersecting sets: N(A union B)=N(A) N(B)-N(A intersect B) 07m
Exercise: How many integers from 1 to 100 are multiples of 4 or 6?
Video class: Combinations Formula: Counting the number of ways to choose r items from n items. 06m
Video class: How many ways are there to reorder the word MISSISSIPPI? // Choose Formula Example 07m
Exercise: How many distinct rearrangements of the letters in MISSISSIPPI are there?
Video class: Counting and Probability Walkthrough 17m

Video class: Intro to Conditional Probability 06m
Exercise: Compute conditional probability from intersection and event probability
Video class: Two Conditional Probability Examples (what's the difference???) 06m
Video class: Conditional Probability With Tables | Chance of an Orange M 09m
Exercise: Compute a conditional probability from a count table
Video class: Bayes' Theorem - The Simplest Case 05m
Video class: Bayes' Theorem Example: Surprising False Positives 12m
Exercise: Bayes theorem: Interpreting a positive medical test
Video class: Bayes' Theorem - Example: A disjoint union 08m
Video class: IS CHESS A GAME OF CHANCE? Classical vs Frequentist vs Bayesian Probability 13m
Exercise: Which interpretation fits estimating P(heart) by repeated draws from an unknown deck?
Video class: Intro to Markov Chains 11m
Video class: Markov Chains 06m
Exercise: Given a transition matrix P and an initial state vector s0, which expression gives the state vector after n iterations in a Markov chain

Video class: Intro to Linear Programming 14m
Video class: Intro to Graph Theory | Definitions 05m
Exercise: Why is the edge collection modeled as a multiset in the bridge graph?
Video class: Properties in Graph Theory: Complete, Connected, Subgraph, Induced Subgraph 04m
Video class: Degree of Vertices | Definition, Theorem 04m
Exercise: Effect of adding an edge on sum of degrees
Video class: Euler Paths 06m

Video class: The End of Discrete Math - Congrats! Some final thoughts... 04m
Exercise: Which statement best captures the core skill emphasized in a discrete mathematics course focused on rigorous thinking?

Learn aboutLinear algebra

Discover free online linear algebra courses that include a certificate and master vectors, matrices, systems of equations, determinants, eigenvalues, and vector spaces. Learn at your own pace with flexible lessons for beginners, students, and professionals, then earn a certificate to showcase your new math skills and advance your studies or career.

Free online courses on Discrete Mathematics

Learn aboutDiscrete Mathematics

Explore free online Discrete Mathematics courses, each including a certificate, and build essential skills in logic, set theory, combinatorics, graph theory, relations, proofs, and algorithms. Learn at your own pace with accessible lessons for students, programmers, and career changers seeking practical knowledge and a valuable credential.