math.wiki
College › Discrete Mathematics and Proof
Open on the map
College

Discrete Mathematics and Proof

10 chapters76 lessons
Show on the map
1

Statements, truth tables and logical equivalence

8 lessons

Compound statements, their truth tables, when two statements say the same thing, and logic built into circuits.

Review first: Statements and negation Conditionals, converse, inverse, contrapositive Biconditional
1.1And and or: conjunction and disjunction
1.2Building a truth table for a compound statement
1.3Truth table for the conditional
1.4Tautologies and contradictions
1.5De Morgan's laws for statements
1.6A conditional and its contrapositive
1.7Saying a conditional without if-then
1.8Exclusive or and logic circuits
2

Quantifiers and valid arguments

8 lessons

For all and there exists, negating them, and telling a valid argument from a fallacy.

Review first: Counterexample
2.1For all
2.2There exists, and there is exactly one
2.3Negating a quantified statement
2.4Nested quantifiers
2.5Valid and sound arguments
2.6Modus ponens, chaining, and a common fallacy
2.7Modus tollens, ruling out, and a common fallacy
2.8Testing an argument with a truth table
3

Direct proof, contrapositive and contradiction

10 lessons

Writing complete proofs about numbers by direct argument, cases, contraposition and contradiction.

Review first: Axioms, definitions and theorems Conjecture, and why a pattern is not a proof Counterexample Proof by contradiction
3.1What may be assumed and what must be shown
3.2Writing a proof as prose
3.3Proving statements about even and odd numbers
3.4Divisibility as a relation
3.5Proving statements about divisibility
3.6Proof by cases
3.7Proof by contraposition
3.8Proving an if and only if
3.9There are infinitely many primes
3.10Existence proof
4

Mathematical induction

3 lessons

Proving a statement for every whole number: the first induction proofs taught again for students who skipped Precalculus, then divisibility, inequalities and strong induction.

Review first: Arithmetic series and partial sums
4.1Triangular numbers
4.2Strong induction and well-ordering
4.3How induction works: base case, hypothesis and stepretaught
5

Sets, relations and functions

8 lessons

Subsets, power sets and set identities proved the way logical identities are, then relations and functions between sets.

Review first: Elements and membership Writing sets: roster, rule and the empty set Union, intersection and complement Cardinality of a finite set Definition of a function
5.1Subsets, proper subsets and equal sets
5.2Power set
5.3Set identities: distributive and De Morgan laws
5.4Proving a set identity
5.5Cartesian product
5.6Relations and their properties: reflexive, symmetric, antisymmetric, transitive
5.7One-to-one, onto and bijective functions
5.8Composing functions between sets, and when an inverse exists
6

Infinite sets

4 lessons

Comparing the sizes of infinite sets by matching, and why some infinities are bigger.

6.1Matching two sets one to one
6.2Countable sets
6.3Uncountable sets and the diagonal argument
6.4Cantor's theorem: no set matches its power set
7

Counting

5 lessons

Counting arguments that go beyond formulas: the pigeonhole principle, stars and bars, inclusion-exclusion and counting one set two ways.

Review first: The fundamental counting principle Permutations Combinations The binomial theorem Venn diagrams and counting a union
7.1The pigeonhole principle
7.2Combinations with repetition: stars and bars
7.3Inclusion-exclusion for three or more sets, and derangements
7.4Combinatorial proof: counting one set two ways
7.5Pascal's triangleretaught
8

Number theory and modular arithmetic

13 lessons

Division with remainder, greatest common divisors, primes, arithmetic modulo n, and the RSA code built on it.

8.1The division algorithm
8.2Numbers in other bases
8.3The Euclidean algorithm and coprime numbers
8.4Bezout's identity and the extended Euclidean algorithm
8.5Congruence modulo n and its arithmetic
8.6Relations, equivalence classes and partitions
8.7Where the divisibility tests come from
8.8Powers modulo n
8.9Modular inverses and linear congruences
8.10The Chinese remainder theorem
8.11Fermat's little theorem
8.12RSA public-key encryption
8.13Every number has exactly one prime factorizationretaught
9

Recurrence relations

4 lessons

Sequences defined by earlier terms, setting them up from counting problems, and finding and proving closed forms for them.

Review first: Recursive formulas Arithmetic sequences and the explicit formula Closed form versus recursive form
9.1The Fibonacci sequence
9.2Setting up a recurrence from a counting problem
9.3Solving and checking a two-term recurrence
9.4Two-term recurrences with a repeated root
10

Graphs

13 lessons

Vertices and edges, paths and circuits, trees, planarity, coloring and shortest routes.

10.1Degree, the handshake lemma and complete graphs
10.2Walks, paths, cycles and connected graphs
10.3Graph isomorphism: when two drawings are the same graph
10.4Euler paths and circuits
10.5Hamiltonian paths and cycles
10.6Trees
10.7Planar graphs and Euler's formula
10.8Graph coloring
10.9Bipartite graphs
10.10Weighted and directed graphs
10.11Finding a shortest path
10.12Spanning trees and minimum spanning trees
10.13Adjacency matrices and their powers