# Instructor: Anatolii Grinshpan Office hours:  MWF 10-10:50, Korman 247, or by appointment, Korman 253.

Course information  Introduction to the course. The logical framework. Truth tables.

Reading and exercises: 1.1-1.3, 3.1-3.3. Homework 1 (due Monday,  April 8).

Apr 3.  Tautology and contradiction. Logical equivalences. Converse and contrapositive.

Apr 5. Sets. Operations on sets. Empty set. Existential and universal quantifiers.

Reading and exercises: 1.4-1.7, 2.1-2.4, 3.6, 3.7. Modus ponens.

Apr 8. Natural numbers: axioms. The principle of induction.

Reading and exercises: 4.1-4.3. Homework 2 (due Monday,  April 15).

Apr 10. Examples of inductive proofs. Reading and exercises: 4.4.

Apr 12. Quiz 1 (4.1 - 4.3). Strong induction. QED.

Apr 15. Recursive definitions and relations. Reading and exercises:  4.5-4.9.

Apr 17. Functions.  Composition. Reading and exercises: 5.1-5.5. Homework 3 (due Monday,  April 22).

Apr 19. Quiz 2 (5.1 - 5.4). The identity function. The inverse function.

Apr 22. Pigeonhole principle. Examples. Reading and exercises: 6.1, 6.2, 6.4. Homework 4 (due Monday,  April 29).

Apr 24. Monotone sublists. Size of a set. Reading and exercises: 6.2, 6.3.

Apr 26. Quiz 3 (6.1 – 6.4). Infinite sets. Reading and exercises: 6.5-6.7.

Apr 29. Midterm 1 (Chapters 1 - 6). Homework 5: none.

May 1. Midterm discussion.

May 3. Relations on a set. Equivalence relations. Reading and exercises: 7.1-7.3.

May 6.   Equivalence classes. Homework 6 (due Monday,  May 13).

May 8.   The construction of integers. Reading and exercises: 7.4, 7.5. Question.

May 10. Quiz 4 (7.1 - 7.3). Least and greatest members. Reading and exercises: 7.6, 7.7.

May 13. Quotient and remainder. Reading and exercises: 8.1, 8.2. Homework 7 (due Monday,  May 20).

May 15. The Euclidean algorithm. Reading and exercises: 8.3, 8.4.

May 17. Quiz 5 (8.1 – 8.4). A property of the greatest common divisor.

May 20. The fundamental theorem of arithmetic. Reading and exercises: 8.5-8.7. Homework 8: none.

May 22. Rational numbers. Enumeration. Reading and exercises: 9.1, 9.2, 9.7.

May 24. Quiz 6 (8.4 – 8.6). Decimal expansions. Reading and exercises: 9.3.

May 28. Questions session: 8:30-9:30AM, Korman 245.

May 29. Midterm 2 (6.5 – 9.3 and Theorem 9.7.1)

May 31. Cantor’s theorem.  Reading and exercises: 9.7. Homework 9 (due Friday, June 7).

June 3.  Real numbers and sets of natural numbers as binary strings. Reading and exercises: 9.4.

June 5.  Sperner’s lemma. Rational approximation to square roots.  Reading and exercises: 9.5, 9.6, 9.8

June 7.  The rate of convergence of the Babylonian method.

June 10. Questions session.

June 11. Final exam (Chapters 1 - 9). 3:30-5:30, PISB 108.