COMP 2742 -- Logic for Computer Science, Winter 2014
- 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
Lectures: 12:00-12:50 Monday, Wednesday and Friday in EN-1052
Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.
Instructor office hours: Monday 2:30-2:30pm and Tuesday 12-1pm,
or by appointment.
Textbook: There will be no textbook for this course; the course notes will be posted online.
- Discrete Mathematics With Applications: Susanna S. Epp
- Discrete Mathematics with Graph Theory: Edgar Goodaire and Michael Parmenter.
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
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
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
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.
- 10/1/2014 Lecture 1: Introduction and beginning of propositional logic
- 13/1/2014 Lecture 2: Truth tables and evaluating propositional formulas.
- 15/1/2014 Lecture 3: Logical identities, equivalences.
- 17/1/2014 Lecture 4: Simplifying propositional formulas, more on "if.. then.."
- 27/1/2014 Lecture 5: Types of proofs
- 29/1/2014 Lecture 6: Valid/invalid arguments, modus ponens, rules of inference
- 31/1/2014 Lecture 7: Normal forms: CNFs and DNFs; Resolution.
- 3/2/2014 Lecture 8: More examples of Resolution. Limits of Resolution. Complete set of connectives
- 5/2/2014 Lecture 9: Boolean functions, Boolean and arithmetic circuits
- 7/2/2014 Lecture 10: Intro set theory
- 10/2/2014 Lecture 11: More sets, Boolean algebras
- 12/2/2014 Lecture 12: Relations, introduction to predicate logic
- 14/2/2014 Lecture 13: Predicate logic: applications to databases, alternation of quantifiers
- 21/2/2014 Review for the midterm.
- 28/02/2014 Lecture 14: Reasoning in predicate logic
- 03/03/2014 Lecture 15: Normal forms, resolution for finite domains, limitations of first-order logic, quantifiers on empty domain.
- 5/3/2014 Lecture 16: Functions
- 7/3/2014 Lecture 17: Proving equivalences with N, diagonalization
- 10/3/2014 Lecture 18: Order relations, well-ordering principle, mathematical induction
- 12/3/2014 Lecture 19: Examples of proofs by induction
- 14/3/2014 Lecture 20: "All horses are white", strong induction
- 17/3/2014 Lecture 21: Strong induction examples: divisibility by prime, existence of binary representation
- 19/3/2014 Lecture 22: Equivalence between induction, strong induction and well-ordering principle. Recursive definitions.
- 21/3/2014 Lecture 23: Structural induction
- 24/3/2014 Lecture 24: Growth of functions, defining functions recursively, recurrences.
- 26/3/2014 Lecture 25: Correctness of algorithms
- 28/3/2014 Lecture 26: Logic theories; Goedel incompleteness theorem