| Day | Topics | Preparation |
|---|---|---|
| Wed. 1/23 | Introduction to course. Definitions | Sec. 1 |
| Fri. 1/25 | Truth and theorems. Logic: not, and, or |
Sec. 2 |
| Mon. 1/28 | Logic: implication and equivalence
Proof: our first one! |
Sec. 2,3 |
| Wed 1/30 | Proof templates. Disproof by counterexample | Sec. 3,4 |
| Fri. 2/1 | Questions on proof problems assigned Boolean Algebra |
Sec. 3,4,5 |
| Mon. 2/4 | Boolean Algebra | Sec. 5 |
| Wed. 2/6 | Lists and counting | Sec. 6 |
| Fri. 2/8 | More counting, factorials | Sec. 6,7 |
| Mon. 2/11 | Sets, subsets, the power set | Sec. 8 |
| Wed. 2/13 | Unions and intersections | Sec. 10 |
| Fri. 2/15 | Difference and symmetric difference, Cardinality formulas |
Sec. 10 |
| Mon. 2/18 | More on sets | Sec. 10 |
| Wed. 2/20 | Counting, binomial coefficients | Sec. 14 |
| Fri. 2/22 | Poker hands, some formulas with binomial coefficients | Sec. 14 |
| Mon. 2/25 | Questions? Multi-sets | Sec. 15 |
| Wed. 2/27 | Exam: logic, sets, combinatorial problems | . |
| Fri. 3/1 | Multi-sets | Sec. 15 |
| Mon. 3/4 | Predicates and quantifiers | Sec. 9 |
| Wed. 3/6 | Relations | Sec. 11 |
| Fri. 3/8 | Equivalence relations | Sec. 12 |
| Mon. 3/11 | Congruence mod n | Sec. 12 |
| Wed. 3/13 | Congruence classes, Partitions | Sec. 12 |
| Fri. 3/15 | Questions? Partitions and counting problems |
Sec. 13 |
| Mon. 3/18 | Functions | Sec. 20 |
| Wed. 3/20 | Functions, into, onto, bijection |
Secs. 20 |
| Fri. 3/22 | Composition of functions | Sec. 22 |
| Mon. 3/25 | Pigeonhole principle | Sec. 21 |
| Wed. 3/27 | Questions?, counting functions, permutations | Sec. 20-23 |
| Fri. 3/29 | Exam: Relations and functions | Secs. 9, 11, 12, 13, 20, 21, 22 |
| Mon. 4/8 | Prrof by contrapositive, contradiction | Sec. 17 |
| Wed. 4/10 | Reductio ad absurdem | Sec. 17 |
| Fri. 4/12 | Smallest conterexample | Sec. 18 |
| Mon. 4/15 | Well ordering, induction | Sec. 18 |
| Wed. 4/17 | Some classic induction proofs Fibonacci numbers |
Secs. 18, 19 |
| Fri. 4/19 | Strong induction, recursive computer programs | Sec. 19 |
| Mon. 4/22 | Probability spaces | Sec. 26 |
| Wed. 4/24 | Probability spaces: some formulas and examples | Sec. 27 |
| Fri. 4/26 | EXAM: Proof by induction, proof by contrapositive, proof by contradiction |
Secs. 17-19 |
| Mon. 4/29 | Conditional probability and independence. | Sec. 28 |
| Wed. 5/1 | Random variables | Sec. 29 |
| Fri. 5/3 | Expectation of a random variable | Secs. 29, 30 |
| Mon. 5/6 | Review of relations, partially ordered sets | Sec. 50 |
| Wed. 5/8 | More on posets | Sec. 51 |
| Wed. 5/15 10:00 | Review | . |
| Fri. 5/17 8:00 | Final | . |
| Due Date | Section | Problems |
|---|---|---|
| Mon. 1/28 | 1 | 3 a,b,c, 6, 8 c,e,h |
| . | 2 | 6, 7 |
| Mon. 2/4 | 2 | 2,4 |
| . | 3 | 8, 13, 14 |
| . | 4 | 3, 4, 5, 7, 9 |
| . | 5 | 7, 8, 9 |
| Mon. 2/11 | 5 | 5 (a De Morgan law), 10c, 11e, 12b, 14, 15b |
| . | 6 | 4, 5, 9c-g, 10 |
| . | 7 | 1, 5, 7c,d, 10 |
| Mon. 2/18 | 6 | 14 |
| . | 8 | 1e,f, 2b,e-h, 3f,g, 6, 8 |
| . | 10 | 1a-f, 2(distributivity), 3, 5 |
| Mon. 2/25 | 10 | 16b,c, 17a,b, 18, 22, 23 |
| . | 14 | 4, 6, 12, 28c-e |
| Mon. 3/11 | Sec. 15 | 1, 2, 4, 5, 6 |
| . | Sec. 9 | 1d-f, 2d-f, 4, 5c-e |
| . | Sec 11 | 2, 4, 7, 8, 12b,c,e |
| Mon. 3/18 | Sec. 11 | 11 |
| . | 12 | 3, 4, 5a-d, 8, 10, 12 |
| . | 13 | 1, 2d, 7, 8, 10, 13 |
| Mon. 3/25 | Sec. 20 | 1d-h, 2, 5, 6, 9, 14 |
| . | Sec. 22 | 1d-j, 6, 9b,c, 10, 11b,c |
| Mon. 4/15 | 17 | 1c,d, 2, 3, 4e,f, 5, 10, 11 |
| . | 18 | 2, 3, 4 |
| Mon. 4/22 | 18 | 5, 6, 7 |
| . | 19 | 3a,b,c, 4c, 8a |
| WED. 5/1 | 26 | 5, 6 |
| . | 27 | 8, 11, 14, 15 |
| Mon. 5/6 | 28 | 1d-f, 2, 3 |
| . | 29 | 1, 2, 4, 5 |
| . | 30 | 1, 2, 3 |