1
Logic
24 lessonsStatements, how they combine, and what follows from what.
1.1And and or: conjunction and disjunctionDiscrete Mathematics and Proof
1.2Logic
1.3Statements and negationGeometry
1.5For allDiscrete Mathematics and Proof
1.6BiconditionalGeometry
1.7Building a truth table for a compound statementDiscrete Mathematics and Proof
1.8De Morgan's laws for statementsDiscrete Mathematics and Proof
1.10Modus ponens, chaining, and a common fallacyDiscrete Mathematics and Proof
1.11Tautologies and contradictionsDiscrete Mathematics and Proof
1.12Testing an argument with a truth tableDiscrete Mathematics and Proof
1.13Truth table for the conditionalDiscrete Mathematics and Proof
1.14Truth tables
1.15Valid and sound argumentsDiscrete Mathematics and Proof
1.17A conditional and its contrapositiveDiscrete Mathematics and Proof
1.18There exists, and there is exactly oneDiscrete Mathematics and Proof
1.19Modus tollens, ruling out, and a common fallacyDiscrete Mathematics and Proof
1.20Negating a quantified statementDiscrete Mathematics and Proof
1.21Quantifiers
1.22Exclusive or and logic circuitsDiscrete Mathematics and Proof
1.23Saying a conditional without if-thenDiscrete Mathematics and Proof
1.24Nested quantifiersDiscrete Mathematics and Proof
2
Sets
20 lessonsCollections of things, and the ways they combine.
2.1Elements and membershipAlgebra 1
2.2Writing sets: roster, rule and the empty setAlgebra 1
2.3Cardinality of a finite setAlgebra 2
2.4Venn diagrams and counting a unionAlgebra 2
2.5Subsets, proper subsets and equal setsDiscrete Mathematics and Proof
2.6Sets
2.7Cartesian productDiscrete Mathematics and Proof
2.8Power setDiscrete Mathematics and Proof
2.9Union, intersection and complementAlgebra 1
2.10Infinite sets
2.11Matching two sets one to oneDiscrete Mathematics and Proof
2.12Set identities: distributive and De Morgan lawsDiscrete Mathematics and Proof
2.13One-to-one, onto and bijective functionsDiscrete Mathematics and Proof
2.14Proving a set identityDiscrete Mathematics and Proof
2.15Relations and their properties: reflexive, symmetric, antisymmetric, transitiveDiscrete Mathematics and Proof
2.16Countable setsDiscrete Mathematics and Proof
2.17Composing functions between sets, and when an inverse existsDiscrete Mathematics and Proof
2.18Relations, equivalence classes and partitionsDiscrete Mathematics and Proof
2.19Uncountable sets and the diagonal argumentDiscrete Mathematics and Proof
2.20Cantor's theorem: no set matches its power setDiscrete Mathematics and Proof
3
Proof techniques
19 lessonsThe standard ways of showing something must be true.
3.1Axioms, definitions and theoremsGeometry
3.2Conjecture, and why a pattern is not a proofGeometry
3.4CounterexampleGeometry
3.5Direct proof
3.6What may be assumed and what must be shownDiscrete Mathematics and Proof
3.7Proving an if and only ifDiscrete Mathematics and Proof
3.8Proving statements about even and odd numbersDiscrete Mathematics and Proof
3.9Writing a proof as proseDiscrete Mathematics and Proof
3.10Existence proofDiscrete Mathematics and Proof
3.11Proof by casesDiscrete Mathematics and Proof
3.12Proof by contrapositionDiscrete Mathematics and Proof
3.13Proving statements about divisibilityDiscrete Mathematics and Proof
3.14The pigeonhole principleDiscrete Mathematics and Proof
3.15How induction works: base case, hypothesis and stepPrecalculus
3.16Proof by contradictionGeometry
3.17Combinatorial proof: counting one set two waysDiscrete Mathematics and Proof
3.19Strong induction and well-orderingDiscrete Mathematics and Proof
4
Recurrence relations
7 lessonsA rule that builds each term of a sequence out of the terms that came before it.
4.1Generating a sequence from a ruleAlgebra 1
4.2The Fibonacci sequenceDiscrete Mathematics and Proof
4.4Closed form versus recursive formAlgebra 1
4.5Solving and checking a two-term recurrenceDiscrete Mathematics and Proof
4.6Setting up a recurrence from a counting problemDiscrete Mathematics and Proof
4.7Two-term recurrences with a repeated rootDiscrete Mathematics and Proof
5
Introductory graph theory
15 lessonsDots and lines, and the puzzles they solve.
5.1Degree, the handshake lemma and complete graphsDiscrete Mathematics and Proof
5.2Walks, paths, cycles and connected graphsDiscrete Mathematics and Proof
5.3Weighted and directed graphsDiscrete Mathematics and Proof
5.4Hamiltonian paths and cyclesDiscrete Mathematics and Proof
5.5Planar graphs and Euler's formulaDiscrete Mathematics and Proof
5.6Euler paths and circuitsDiscrete Mathematics and Proof
5.7Graph coloringDiscrete Mathematics and Proof
5.8Bipartite graphsDiscrete Mathematics and Proof
5.9TreesDiscrete Mathematics and Proof
5.12Spanning trees and minimum spanning treesDiscrete Mathematics and Proof
5.13Finding a shortest pathDiscrete Mathematics and Proof
5.14Graph isomorphism: when two drawings are the same graphDiscrete Mathematics and Proof
5.15Adjacency matrices and their powersDiscrete Mathematics and Proof
6
Introductory number theory
16 lessonsProperties of the integers, proved.
6.1Divisibility as a relationDiscrete Mathematics and Proof
6.2The division algorithmDiscrete Mathematics and Proof
6.3Numbers in other basesDiscrete Mathematics and Proof
6.4The Euclidean algorithm and coprime numbersDiscrete Mathematics and Proof
6.5Triangular numbersDiscrete Mathematics and Proof
6.6Congruence modulo n and its arithmeticDiscrete Mathematics and Proof
6.7Where the divisibility tests come fromDiscrete Mathematics and Proof
6.8There are infinitely many primesDiscrete Mathematics and Proof
6.11Powers modulo nDiscrete Mathematics and Proof
6.12Fermat's little theoremDiscrete Mathematics and Proof
6.13Bezout's identity and the extended Euclidean algorithmDiscrete Mathematics and Proof
6.14Modular inverses and linear congruencesDiscrete Mathematics and Proof
6.15RSA public-key encryptionDiscrete Mathematics and Proof
6.16The Chinese remainder theoremDiscrete Mathematics and Proof