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

- 10/4/2013 The last assignment is not graded yet -- so sorry for that! I will post something online if the marker gets it done before the final (but it seems that he will not be able to, unfortunately). If you have any questions, please come to my office, and I go over your solutions with you.
- 5/4/2013 Please double-check that your grades are entered correctly on D2L! If there is any problem, please email me as soon as possible -- it will be much easier to take care of corrections before the final exam. And while you are there, the CEQ (course evaluations) are online this year, and open until April 9th.
- 5/4/2013 Here is a study guide for the final exam

** older announcements...**

- 5/4/2013 The grades for the last assignment should be available by Wednesday; if all is OK, I'll be returning your last assignment during the 5-hour office hours.
- 5/4/2013 As discussed in class, there will be one 5-hour-long office hour next week on Wednesday, April 10th, from 12pm to 5pm. Please let me know if you would like to meet with me at a different time.
- 2/3/2013 For question 2d (on Fibonacci numbers), you can get the answer without using induction, just by using the recursive definition. If you did the proof this way, it is OK.
- 29/3/2013 (Old) notes on combinatorics: lecture 1, lecture 2 and lecture 3 .
- 27/3/2013 Assignment 5 is posted; due April 3rd.
- 22/3/2013 The university is closed, so no class today. See you Monday!
- 17/3/2013 A typo in the study guide (distr. law for logic reversed) corrected. Thank you for pointing it out!
- 15/3/2013 Here is a study guide for the test 2 (which will be Monday, March 18).
- 4/3/2013 Notes for all the material that we cover in class (except for resolution for predicate logic) is available on the previous year webpage; just follow the link on top of the notes. The resolution notes should be available in the next couple of days; for now, please just google for "resolution, unification, skolemization" and you will find plenty of information.
- 4/3/2013 Tentatively, midterm test 2 will be on Monday, March 18th (with a review the previous Friday). Please let me know as soon as you can if this date does not work for you.
- 4/3/2013 Assignment 4 is now posted below. Due March 11th.
- 13/2/2013 Clarification for Question 1, assignment 3: please use only AND, OR and NOT gates (otherwise some questions become much easier ;-))
- 13/2/2013 My office hours tomorrow, Feb 14, will be 1-2pm rather than the usual 12-1pm. Please email me if you were planning to come, but this time does not work for you, and we'll arrange a different time.
- 13/2/2013 Here is the Assignment 3. As discussed in class today, the due date now will be February 25th (Monday).
- 7/2/2013 I still do not have the assignments 2 graded, sorry. Please try to stop by sometime after 10:30am tomorrow, I really hope to have them by then. And you are welcome to email me any questions you have!
- 6/2/2013 The study guide for the first test is now posted. I will go over it in the review class today.
- 4/2/2013 As discussed in class, the first test will be this Friday, February 8th. It will cover the material from the first two assignments. Part of the February 6th lecture will be a review for the test.
- 30/1/2013 Lecture notes up to today posted (with different examples and sometimes material in different lectures, though -- for example, complete set of connectives notes are in the lecture 9 set, although we did them a while ago). Please let me know if you notice any mistakes!
- 25/1/2013 Assignment 2 is now posted. Since it is due February 1st which will be a tutorial going over assignments solutions, the assignments are due at the beginning of the class and no late assignments will be accepted .
- 18/1/2013 Clarification for the assignment: in the simplification problem
you may need to use the definitions of T (T <=> p \/ -p), F (F <=> p /\ -p), as well as representations of -> and <-> using /\, \/ and -.

- 18/1/2013 The lecture notes for lecture 4 are now posted below
- 16/1/2013 The lecture notes for lecture 3 are now posted below
- 16/1/2013 Office hours this semester will be Mon 4pm, Tue 2pm and Thur 12pm.
- 14/1/2013 Assignment 1 is now posted below . Due January 23rd (Wednesday).
- 13/1/2013 The lecture notes for lecture 2 are now posted below
- 8/1/2013 The lecture notes for the first lecture are now posted below

- 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).

** Tentative course description **

Logic has been called the "calculus of computer science": just as sciences
such as physics that deal with continuous realm rely on calculus techniques,
we rely on logic. Indeed, so many areas of our field are based on logic: from
designing circuits to determining complexity of problems; from verifying
correctness of algorithms and devising database queries to automated
reasoning in artificial intelligence.

This course is intended to be an introduction to mathematical logic with emphasis on Computer Science applications and methodologies. We will cover propositional and predicate logic with applications to Boolean circuits and database querying, respectively; that will also cover Resolution proof technique, which is the basis of most modern-day automated problem solvers. Then we will discuss basic proof techniques such as mathematical induction, again with computer science applications including proving algorithm correctness. Throughout the course, we will also discuss impossibility results, in particular Goedel's incompleteness theorem.

Assignment 1. ( LaTeX source ) Due Jan 23, 2013 | Assignment 2. ( LaTeX source ) Due Feb 1, 2013. |

Assignment 3. Feb 25, 2013. ( LaTeX source ) | Assignment 4. Due March 11, 2013. ( LaTeX source ) |

Assignment 5. Due Apr 3, 2013. |

You are encouraged to use LaTeX for typesetting your assignments. A good (though a bit outdated) introduction to LaTeX is "Essential LaTeX" .

** Policy on collaboration: ** The work you submit must
be your own. You may discuss problems from assignments with each
other; however, you should prepare written solutions alone.
Plagiarism is a serious academic offense and will be dealt with
accordingly.

I will be posting lecture notes as we go; you are welcome to check the lecture notes from the previous run of this course.

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

- 7/1/2013 Lecture 1: Introduction and beginning of propositional logic
- 9/1/2013 Lecture 2: Truth tables and evaluating propositional formulas.
- 14/1/2013 Lecture 3: Logical identities, equivalences.
- 16/1/2013 Lecture 4: Simplifying propositional formulas, more on "if.. then.."
- 18/1/2013 Lecture 5: Types of proofs
- 21/1/2013 Lecture 6: Valid/invalid arguments, modus ponens, rules of inference
- 23/1/2013 Lecture 7: Normal forms: CNFs and DNFs
- 25/1/2013 Lecture 8: Resolution refutations (proving with resolution proof system).
- 28/1/2013 Lecture 9: Boolean functions, complete set of connectives, Boolean and arithmetic circuits
Please see the lecture notes from the previous run of this course for the subsequent topics. Old notes on combinatorics: lecture 1, lecture 2 and lecture 3 .