CS2742 -- Logic for Computer Science

15/4/2014 Final exam marks are now posted. Your preliminary calculation for the course grade is under the category "raw".
Please make sure that all the marks are entered correctly! If you notice any discrepancy, or want to talk to me about your mark, please contact me no later than by Wednesday evening.
11/4/2014 Assignment 4 has been marked; please stop by my office to pick yours up.
Reminder: office hours on Friday, April 11, 1pm-4pm.
3/4/2014 Practice exam grades are now posted. I will return the exam and go over it tomorrow in the lecture.
1/3/2014 As MUN is closed this morning, I will not be there for 12pm office hours. Please email me if you have questions!
31/3/2014 Here is the study guide for the exams .
31/3/2014 Just a reminder of our practice exam this Wednesday, April 2nd. The exam will start at our usual class time (12pm), in the usual room, and will go for 2 hours.
27/3/2014 Since a number of you have asked me about an extension of the assignment due date till Monday, let's indeed make it due Monday (March 31st). But please make sure to submit it right at the start of the class, because I was planning to go over the assignment in the review.
24/3/2014 The question 4 on the assignment has been changed to a different (hopefully simpler) one. Now, in the first part you need to give a recursive definition of a set of all binary strings starting with a 1, and in the second part you would use structural induction to show that any element of your resulting set encodes a number greater than 0. A new version of the assignment has been posted.
17/3/2014 Assignment 4 is now posted. Due Friday March 28th.
12/6/2014 Because of the weather, and to have a chance to explain question 6 more, let us make the assignment 3 due on Friday (March 14) rather than today. We will talk about the assignment more in the class.
Lecture notes 13 have been updated to include the "Grandparent" example and to fix a typo on the order of quantifiers in Current(x,y). Thank you for catching this!
7/3/2014 A clarification on question 2 of assignment 3: there should be an additional condition that none of web designers are interested in grad. school unless they are interested in everything. An updated version of the assignment is now posted.
Assignment 3 is now posted. Due Wednesday March 12th
Here is the study guide for the midterm . The midterm itself will be next Wednesday, Feb 26th (there will be no lecture on Monday, Feb 24th). Note: the study guide is intended to be used for study before the midterm, not during the test.
Assignment 2 is now posted; due February 12th. There were two typos there (thank you very much for catching them!): one is that there should be a negation before x1 in the last clause of 4b (that is, (not x1 -> x4)). The other is that "u" in 6b should be "y". Sorry for that! A corrected version is now posted.
The next two Wednesdays (February 5th and February 12th) we will have extra 25 minutes of lecture time, finishing class at 1:15pm. This is to make up for February 24th class, which will be canceled. The midterm will be on February 26th.
Please let me know as soon as possible if any of these changes is a problem for you!
21/1/2014 All lecture notes from lectures 1-4 are now posted. Sorry for the delay!
19/1/2014 Next week (January 20-24) there will be three tutorials in our usual lecture time. The first tutorial, Jan 20th, will cover modular arithmetic and binary notation. The second, Jan 22nd, will cover basic combinatorics (including factorials) such as computing the number of binary strings of a given length. Finally the third tutorial, on Jan 24th, will be on the logic, and will cover examples similar to the assignment. All three tutorials will be done by Abdullah-al Mamun. Attendance at tutorials is optional -- the goal to ameliorate large discrepancy in backgrounds coming into this course.
I will be out of town that week, so there will be no office hours this Monday or Tuesday. Sorry for that!
19/1/2014 The first assignment is now posted. Due January 29th, at the beginning of the lecture.
16/1/2014 At your suggestion, I have posted the final exam study guide from COMP 2742 Winter 2013 offering . We are likely to cover a slightly different set of topics this semester, however you might find it useful for the notation, etc for the material we are covering now (it is a lot more concise than the notes). If there is any notation I am using that you have not seen before, please let me know and I will add it to the study guide.
10/1/2014 Office hours will be on Mondays 2:30-3:30pm, and Tuesdays 12-1pm.
8/1/2014 The first class will be Friday, January 10th (due to MUN closure for the first three days of the semester).
8/1/2013 The lecture notes for the first lecture are now posted below

Marking scheme ( tentative! ): 4 assignments of 10% each, a midterm test 20% and a final exam 40%. 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.

Lecture notes

I will be posting lecture notes as we go; you are welcome to check the lecture notes from the previous run of this course. At your suggestion, here is a study guide from CS2742 Winter 2013 . Please consult it for notation that you might not know. This covers all the material from the last Winter's offering of COMP 2742; it is likely that we will cover different material in a different order, etc. In any case, please do not expect that you have to know this before taking this class.

COMP 2742 -- Logic for Computer Science, Winter 2014

Announcements

Course information

Assignments

Lecture notes