Course Description

This course presents an introduction to mathematical logic with an emphasis on topics that arise from current research and practice in Computer Science. The course is mathematical in nature and it will not involve computer work.

Prerequisites Computer Science 027a/b and one full course or equivalent chosen from the following: Mathematics 030, Applied Mathematics 026, Calculus 050a/b, 051a/b, 081a/b, Linear Algebra 040a/b, or permission of the Department. Unless you have either the requisites for this course or written special permission from the Dean to enroll in it, you will be removed from this course and it will be deleted from your record. This decision may not be appealed. You will receive no adjustment to your fees in the event that you are dropped from a course for failing to have the necessary prerequisites.

Instructor

Lila Kari

Office: Middlesex College 385.

Office hours: Wednesdays, 11am-12noon, Friday 11am-12noon.

Phone: 661-2111 ext.86894

Literature

There is no textbook for this course. Students should take notes in class and work from these. The instructor's notes of the course will be available electronically as postscript files on the course website. Please be advised that these are copies of the lecture overheads, not complete course notes, and are not a substitute for attending lectures. The recommended reading is J.Rubin. Mathematical logic: applications and theory, Saunders College Publishing, 1990. There are also quite a few books on mathematical logic in the library. All these may be relevant to certain parts of the course and, for those, they could be useful background reading. However, there is no book that would actually get close to covering the whole course.

Course Website

The CS209b website is at http://www.csd.uwo.ca/~lila/209.html. Lecture notes, exercises and their solutions, sample exams and class announcements will be posted on this website. You are responsible for reading this information frequently.

Topics

Translations from English into the language of propositional logic;

Valid and invalid arguments;

Formal deduction and its role in proving validity of arguments;

Logic and Computer Science: how to build circuits from logic gates; how to minimize circuits using propositional calculus;

Refining the tools: translations from English into the language of predicate logic;

Valid and invalid arguments, formal deduction in predicate logic;

Applications of predicate calculus to Computer Science: artificial intelligence, automated theorem-provers, expert systems;

Logic and DNA Computing.

Class Schedule

The course hours -- Wednesdays and Fridays 9:00am - 11:00am -- will be used for lectures or laboratory sessions as needed. Laboratory sessions will typically involve in-class solving of problems by students or review work.

Student Evaluation

5 in-class quizzes, each worth 1%, the average of which will constitute 5% of the final grade;

5 assignments, each worth 4%, the average of which will constitute 20% of the final grade;

1 in-class midterm exam worth 25%;

the final exam worth 50%.

Late assigments cost 10% of the assignment per day late unless an extension has been granted. As we intend to return marked assignments and post their solutions in a timely manner, after a week has passed from the due-date no assignments will be accepted for marking. To obtain a passing grade in the course, a student must obtain at least 50% on the final exam.

Schedule (tentative)

The quizes and assignments are given in alternate weeks. Assignments are usually posted on Monday and are due the following Monday, at midnight, in the CS209 locker. The exact schedule of quizes and assignments as well as due dates and location of the locker will be posted on the course web-page.

The Midterm Exam is scheduled on Friday, October 22, 9am. It is an 1hr45min written in-class exam. The Final Exam will be scheduled during the exam period and it is a 3-hour written exam.

All exams and quizes are close-book. A one-sided letter-size reference sheet (no flaps) is allowed for the exams, but not for the quizes.

There will be no make-up for the Midterm Exam, except for students requesting a Special Midterm Exam for religious reasons. These students must have notified the course instructor and filed documentation with their Dean's Office at least two weeks prior to the Midterm Exam. If you miss the Midterm for any other reason, and if you present valid documentation to the Dean's Office, your Final Exam mark will be re-weighted to include the weight of the Midterm Exam. You must notify the course instructor within a week of the missed Midterm Exam, and documentation must be received by your Dean's Office within 2 weeks of the missed exam.

There will be no make-up for the quizzes, except in the situations described above for the Midterm Exam.

In case of questions regarding the marks, please note that no quizzes or exams will be accepted for re-marking later than two weeks after they have been marked. We reserve the right not to re-mark quizzes or exams that have been written in pencil.

All students are expected to attend all classes. A student found to be missing a large number of classes without acceptable reasons (see the Calendar for these) risks being denied a passing grade.

Ethical Conduct

All quizzes, assignments and exams are individual. Copying is a serious academic offense that will result in penalties ranging from the students' failing the course to being expelled from the university. You are responsible for reading and respecting the Computer Science Department's policy on Scholastic Offenses and Rules of Ethical Conduct. Unfamiliarity with these rules will not be considered a valid excuse.

Computing Facilities

Each student will be given an account on the Computer Science Department undergraduate computing facility, GAUL. In accepting the GAUL account, a student agrees to abide by the department's Rules of Ethical Conduct.

Further Information

Additional information will be given in class, by email, or posted on the course website. You should make it a habit to check the course website, use email and read it regularly. Students who prefer to use other computer accounts than their accounts in the Computer Science Department should set the latter up for appropriate forwarding of email. Losing email that you have forwarded to an alternative email address is not an excuse for not knowing about the information that was sent.

You are encouraged to ask brief questions regarding lecture material by sending email to the email address that will be provided in class. Please do not send email directly to the course instructor. You are welcome to ask your questions in person during the instructor's office hours. There will be several Teaching Assistants helping with this course. They will also have regular office hours for consulting, which will be posted on the course website.