Announcements | | Course information | | Assignments and tests | | Lecture notes |

12/12/2009 The final exams are now marked. The final exam mark and a preliminary course marks are posted in the updated marks file . Please let me know before Monday 2pm if there are any problems with it!

04/12/2009 Please check the marks file to ensure that all of your assignments and test marks are entered correctly. Let me know before the final exam if anything is amiss! If you were sick and made special arrangements with me for some assignments and/or tests, the corresponding cells are marked green: if you made the arrangements but I didn't mark the cell, please email me as soon as possible!

03/12/2009 Study guide for the final exam is now posted.

02/12/2009 Solutions for assignment 5 are now posted.

02/12/2009 The office hours before the final exam will be Tuesday, Dec 8th, 2pm-
5pm. The final exam itself is Dec 9th, 3-5pm, usual classroom.

27/11/2009 Typo in the code for the last question: A[f]=m should be A[f]=x. Corrected version now posted.

27/11/2009 To make question 1c easier, assume that A(2,n)=3+2n.

27/11/2009 For question 1b, assume, as a base case, that for every prime number p>2, p=2k+1 for some k

27/11/2009 Assignment 5 is postponed until Dec 2nd (Wednesday).

22/11/2009 Study guide for the second test is now posted here .

22/11/2009 Assignment 5 is now posted. Tentatively due Nov 30th.

21/11/2009 Solutions for assignment 4 are now posted.

16/11/2009 The second test, test 2, will be on Wed Nov 25th. Monday Nov 23rd will be a review for the test.

13/11/2009 Assignment 4 due date is posponed till Wednesday Nov 18. No office hours today, but there will be office hours on Monday 2-3.

04/11/2009 Solutions for assignment 3 are now posted.

04/11/2009 No office hours next Monday and Wednesday; office hours Friday 13th 1pm-3pm.

04/11/2009 Assignment 4 is now posted. Due Nov 16th.

30/10/2009 Assignment 3 postponed till Monday.

30/10/2009 There will be a long class next Wednesday, Nov 4th, to make up for cancelled lecture on Nov 9th. So no lecture Nov 9th, lecture till 1:40pm on Nov 4th.

28/10/2009 Typo: there is a missing parenthesis in 2c in the assignment: the part of the formula from exists z ... to the end of the formula should be within parentheses.

23/10/2009 Assignment 3 is now posted. Due Oct 30th.

19/10/2009 Some typos in assignment 2 solutions corrected. Check the new version (below).

19/10/2009 The lecture on Monday, Oct 19th is a review before the test. The test is on Wednesday, Oct 21st.

18/10/2009 Study guide for the first test is now posted here .

18/10/2009 Solutions for assignment 2 are now posted.

5/10/2009 Tentatively: first test is Oct 21st. Second test is Nov 20th.

5/10/2009 Solutions for assignment 1 are now posted.

01/10/2009 Assignment 2 is now posted. Due Oct 16th.

01/10/2009 Friday Oct 9th classed is canceled. To make up, on Wednesday Oct 14th we will have a longer class (till about 1:40pm).

23/09/2009 A comment about assignment 1: this is supposed to cover topics before resolution, so please do not use resolution to simplify formulas (use logical equivalences). The problem with using resolution is that it is a one-way implication, not a two-way equivalence.

21/09/2009 Assignment 1 is now posted (corrected version). Due Sep 30th.

** Lectures: ** 12:00-12:50 Monday, Wednesday and Friday in EN-1051

** Instructor: ** Antonina
Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.

** Instructor office hours: ** M/W 13:30-14:30
or by appointment.

** Textbook: ** There will be no textbook for this course; however, the course notes will be posted online.

** Reference book: ** Discrete Mathematics With Applications: Susanna S. Epp, Discrete Mathematics with Graph Theory: Edgar Goodaire and Michael Parmenter.

** Marking scheme ( tentative! ): ** ~5 assignments of 7% each, two midterm tests 15% each and a final exam 35%. Note
that the last assignment will be due during the last week of the
semester (to provide adequate preparation for the final exam).

Assignment1. Due Sep 30, 2009. | Assignment 2. Due Oct 16, 2009. |

Assignment 3. Due Oct 30, 2009. | Assignment 4. Due Nov 16, 2009. |

Assignment 5. Due Nov 30, 2009. |

A study guide for the first test. A study guide for the second test. A study guide for the final exam.

- 9/9/2009 Lecture 1: Introduction and beginning of propositional logic
- 11/9/2009 Lecture 2: Truth tables and evaluating propositional formulas.
- 14/9/2009 Lecture 3: Logical identities, equivalences, simplifying propositional formulas.
- 16/9/2009 Lecture 4: Logical equivalences involving implication, contrapositives, types of proofs
- 18/9/2009 Lecture 5: Valid/invalid arguments, modus ponens, rules of inference, CNFs and DNFs
- 21/9/2009 Lecture 6: More CNFs and DNFs, Resolution proof system
- 23/9/2009 Lecture 7: Resolution, converting formulas to CNF.
- 25/9/2009 Lecture 8: Boolean functions, complete set of connectives
- 28/9/2009 Lecture 9: Boolean and arithmetic circuits
- 30/9/2009 Lecture 10: introduction to predicate logic
- 02/10/2009 Lecture 11: Predicate logic: applications to databases, alternation of quantifiers
- 05/10/2009 Lecture 12: Reasoning in predicate logic
- 07/10/2009 Lecture 13: Normal forms, resolution for finite domains, limitations of first-order logic, quantifiers on empty domain.
- 14/10/2009 Lecture 14: Intro set theory, Venn diagrams
- 16/10/2009 Lecture 15: Defining numbers, Russell's paradox, barber of seville
- 19/10/2009 Lecture 16: Proving statements about sets, Boolean algebras.
- 23/10/2009 Lecture 17: Power sets, halting problem
- 26/10/2009 Lecture 18: Functions
- 28/10/2009 Lecture 19: More functions, proving equivalences with N, diagonalization
- 30/10/2009 Lecture 20: Relations, equivalences, transitivity
- 02/11/2009 Lecture 22: Partial orders
- 04/11/2009 Lecture 23: Well-ordering principle, mathematical induction
- 06/11/2009 Lecture 24: More examples of induction
- 16/11/2009 Lecture 25: Strong induction
- 18/11/2009 Lecture 27: Structural induction, recursive definition, equivalences between induction, strong induction and well-ordering
- 20/11/2009 Lecture 28: Growth of functions, recursively defined functions
- 23/11/2009 Lecture 29: Algorithm correctness, loop invariants
- 27/11/2009 Lecture 30: Recursive algorithm correctness, binary search
- 02/12/2009 Lecture 31: Hilbert's program, theories of arithmetic, Goedel's incompleteness theorems