CS2209A: Applied Logic for Computer Science, Fall 2017

Welcome to CS2209A, 2017!

  • Sept. 15th: The problem set for Exercise 1 has been added to OWL Location: site "COMPSCI 2209A 001 FW17" > Resources > Exercise Set > exe-1.pdf
  • Sept. 15th: Recommended reading for the lectures on Sept. 13th in Week 1 was posted under the Lecture Materials tab.
  • Sept. 14th: A feedback forum has been up at OWL. It is anonymous.
    • Are we reasoning logically?
      "If a course is required for my program, I must take it. CS2209 is a required course. Therefore, I am taking CS2209 this term."
      "If a course teaches useful knowledge, I want to take it. CS2209 teaches useful knowledge. Therefore, I want to take CS2209."

    • "CS2209 will teach very userful knowledge."
      True. Propositional and predicate logic, deductive and inductive reasoning, applications to Boolean circuit, database query, program verification, automated reasoning in artificial intelligence, ...
    • "I will have a pleasant learning experience here."
      True. Please attend classes, follow the work plan and have fun!
    • "I need to work hard in order to succeed in this course."
      True. Work hard and think smart!

Lecture Materials: lecture slides, recommended readings and supplementary materials

Logic with Fun

  • Knights and Knaves:
    Some remote island is populated by two kinds of people: knights, who always tell the truth, and knaves, who always lie.
    Suppose you met two islanders, call them A and B, and you hear A saying "at least one of us is a knave".
    Can you tell which of A and B is a knight and which is a knave?

  • "If pigs can fly, then 2 + 2 = 4."
    True or False?

    "If pigs can fly, then 2 + 2 = 5."
    True or False?

  • Bertrand Russell and the Pope:
    "If 2 + 2 = 5, then I am the Pope."
    True or False?

  • Logic and Proof FUNdamentals


  • An Illustrated Book of Bad Arguments

  • Raymond Smullyan's puzzles

Homework and Schedule

Note: Exercises and assignments will be posted via OWL.

Tentative Assignment, Quiz and Test Schedule

Assignment 1Wed. Sept. 20Tue. Oct. 3, 12:00pm5%
Quiz 1Wed. Sept. 27 8:30-9:00pm3%
Assignment 2Wed. Oct. 4Tue. Oct. 24, 12:00pm7%
Quiz 2Wed. Oct.188:30-9:00pm3%
Midterm ExamWed. Oct. 25 7:00pm-8:50pm 20%
Quiz 3Wed. Nov. 88:30-9:00pm3%
Assignment 3Wed. Nov. 8Tue. Nov. 21, 12:00pm9%
Quiz 4Wed. Nov. 228:30-9:00pm3%
Assignment 4Wed. Nov. 22Tue. Dec. 6, 12:00pm9%
Quiz 5Wed. Dec. 6 8:30-9:00pm3%
Final ExamTBA 35%

Teaching Crew and Hours

  • Instructor
    Yu Zhen Xie, PhD
    email: yxie4@uwo.ca

    Lecture hours: 3:30-4:30pm, 7:00-9:00pm on Wednesdays
    Lecture room: NS 1

    Office: Middlesex College, Room 327
    Office hours: 4:30-6:30pm on Tuesdays

  • Teaching Assistants
    NameOffice/Tutorial HoursRoom
    Andrew Bloch-HansenMonday 12:30-2:30pmMC 4A
    Mehdi SamadiehMonday 2:30-4:30pmMC 4A
    Linxiao WangThursday 1:30-3:30pmMC 4A
    Gurjit RandhawaWednesday 9:00-10:00pmNS 1
    Gurjit RandhawaTuesday 3:30-4:30pmUCC 146
    Zihao WangWednesday 9:00-10:00pmNS 1
    Zihao WangTuesday 3:30-4:30pmUCC 146


A course forum and feedback polls will be available at OWL.

CS2209A, Fall 2017
Applied Logic for Computer Science
Course Outline

Course Description

This course presents an introduction to mathematical logic with emphasis in Computer Science applications and methodologies. Topics include propositional and predicate logic, methods for deductive and inductive reasoning, applications to Boolean circuits, database queries, program verification, and automated reasoning in artificial intelligence. Concepts involving sets and other discrete structures will be used to illustrate different types of proof techniques. Throughout the course, we will also discuss impossibility results, in particular Gödel's incompleteness theorem.


Computer Science 1027A/B, 1037A/B, or Computer Science 2101A/B, in each case with at least 65%, and one full course or equivalent chosen from the following, with at least 60% in each: Applied Mathematics 1201A/B or the former Calculus 1201A/B, Applied Mathematics 1413, Calculus 1000A/B, 1100A/B, 1301A/B, 1501A/B, Mathematics 1600A/B or the former Linear Algebra 1600A/B, or permission of the Department.

Unless you have either the requisites for this course or written special permission from your 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.


Yu Zhen Xie, PhD
Email: yxie4@uwo.ca
Office: Middlesex College 327
Office hours: 4:30-6:30pm on Tuesdays

Teaching Assistants


Course Materials

There is no specific textbook for this course. Lecture notes, suggested readings and supplementary materials are available electronically on the course website (see below).
The reference books are

  • Discrete Mathematics With Applications. Susanna S. Epp
  • Logic in Computer Science: Modelling and reasoning about systems. Michael Huth and Mark Ryan

Course Website

Students should check the course website http://www.csd.uwo.ca/courses/CS2209a as well as OWL (http://owl.uwo.ca) on a regular basis for news and updates. These are the primary method by which information will be disseminated to all students in the class. The missing of critical information due to your failure to check the course website or OWL cannot be used as a basis for appeal.

Class Schedule

There are three lecture hours, on Wednesdays, 3:30pm - 4:30pm and 7:00pm - 9:00pm at NS 1. There is one tutorial hour, offered in two sessions but with the exact content be delivered. One is on Wednesdays, 9:00pm - 10:00pm at NS 1, right after the lecture. The other one is on Tuesdays, 3:30pm - 4:30pm at UCC 146. A student may choose to go to either one. Tutorial hours will typically involve in-class solving of problems by students or review work.

Course Work Evaluation

The overall course grade, out of 100, will be calculated as follows:

  • 5 in-class quizzes about key concepts and principles, each worth 3%, the sum of which will constitute 15% of the final grade;
  • 4 assignments, worth 5%, 7%, 9%, 9% respectively, the sum of which will constitute 30% of the final grade;
  • 1 in-class midterm exam worth 20%;
  • the final exam worth 35%.

None of the components will be dropped, and it is not possible to have the components reweighted unless they were legitimately missed.

It is Faculty of Science policy that a student who chooses to write a test or exam deems themselves fit enough to do so, and the student must accept the mark obtained. Claims of medical, physical, or emotional distress after the fact will not be considered.

Scholastic offences are taken seriously and students are directed to read the appropriate policy, specifically, the definition of what constitutes a Scholastic Offence, at this website: http://www.uwo.ca/univsec/pdf/academic_policies/appeals/scholastic_discipline_undergrad.pdf.

Computer-marked, multiple-choice tests and exams may be subject to submission for similarity review by software that will check for unusual coincidences in answer patterns that may indicate cheating.

Late assigments cost 10% of the assignment per day late unless an extension has been granted. 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.

Every effort will be made to have assignments, quizzes and tests marked and handed back within 2 weeks of the hand-in date.

Tentative Assignment, Quiz and Test Schedule, and Other Test and Exam Rules

Assignment 1Wed. Sept. 20Tue. Oct. 3, 12:00pm5%
Quiz 1Wed. Sept. 27 8:30-9:00pm3%
Assignment 2Wed. Oct. 4Tue. Oct. 24, 12:00pm7%
Quiz 2Wed. Oct.188:30-9:00pm3%
Midterm ExamWed. Oct. 25 7:00pm-8:50pm 20%
Quiz 3Wed. Nov. 88:30-9:00pm3%
Assignment 3Wed. Nov. 8Tue. Nov. 21, 12:00pm9%
Quiz 4Wed. Nov. 228:30-9:00pm3%
Assignment 4Wed. Nov. 22Tue. Dec. 6, 12:00pm9%
Quiz 5Wed. Dec. 6 8:30-9:00pm3%
Final ExamTBA 35%

  • If for any reason the assignment and quiz schedules cannot be adhered to, the marks will be pro-rated.
  • The submission of assignments is hard-copy. Lockers will be provided.
  • No electronic devices may be in your possession during tests and exams.
  • The Midterm Test is an 1hour 50min written in-class exam. The 3-hour written Final Exam will be scheduled during the exam period.
  • All exams, tests and quizzes are close-book. A reference sheet (provided by the instructor) is allowed for the Midterm Test and Final Exam, but not for the quizzes.
  • 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 risks being denied a passing grade.

Missed Test or Final Exam

If you are unable to meet a course requirement due to illness or other serious circumstances, you must provide valid medical or supporting documentation to the Academic Counselling Office of your home faculty as soon as possible.

If you are a science student, the Academic Counselling Office of the Faculty of Science is located in WSC 191, and can be contacted at 519-661-3040 or scibmsac@uwo.ca. Their website is http://www.uwo.ca/sci/undergrad/academic_counselling/index.html.

A student requiring academic accommodation due to illness is recommended to follow the policy on Accommodation for Illness http://www.uwo.ca/univsec/pdf/academic_policies/appeals/accommodation_illness.pdf (which includes a link to the Student Medical Certificate)

There are no make-up tests or quizzes. If your faculty's Academic Counselling Office has approved your circumstances, the value of the missed test or quiz will be reallocated.

If you miss the Final Exam, contact your faculty's Academic Counselling Office as soon as possible. They will assess your eligibility to write the Special Exam (the name given by the university to a makeup Final Exam).

You may also be eligible to write the Special Exam if you are in a "Multiple Exam Situation": http://www.registrar.uwo.ca/examinations/exam_schedule.html.


Please contact the course instructor if you require lecture or printed material in an alternate format or if any other arrangements can make this course more accessible to you. You may also wish to contact Services for Students with Disabilities (SSD) at 661-2111 ext. 82147 if you have questions regarding accommodation.

Support Services

Learning-skills counsellors at the Student Development Centre (http://www.sdc.uwo.ca) are ready to help you improve your learning skills. They offer presentations on strategies for improving time management, multiple-choice exam preparation/writing, textbook reading, and more. Individual support is offered throughout the Fall/Winter terms in the drop-in Learning Help Centre, and year-round through individual counselling.

Students who are in emotional/mental distress should refer to Mental Health@Western: http://www.health.uwo.ca/mental_health.

for a complete list of options about how to obtain help. Additional student-run support services are offered by the USC http://westernusc.ca/services.

The website for Registrarial Services is http://www.registrar.uwo.ca.