CS2742 -- Logic for Computer Science

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

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.

Assignments

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.

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.

COMP 2742 -- Logic for Computer Science, Winter 2013

Announcements

Course information

Assignments

Lecture notes