York University- Department of Computer Science & Engineering

SC/MATH 1090 3.00 – Introduction to Logic for Computer Science

Fall 2014


Course director:

Vida Movahedi (vida@cse.yorku.ca)


Mondays and Wednesdays, 1:00pm to 2:30pm in CLH K

Office hours:

Mondays, 2:30-4:30pm in LAS 3032 (temporary location)



Starting September 18

Thursdays, 12:00 to 13:00 in HNES 035

TA: Nada Elasal (nelassal@yorku.ca)


Additional Office Hours


TAs:     Nada Elasal (nelassal@yorku.ca)

            Reza Soltani (rts@cse.yorku.ca)

            Feng Gao (gaofeng@cse.yorku.ca)



Course Outline

Unofficial Grades- tentative, unofficial, and subject to change at the Department's or Faculty's request!


On this page:


Course Schedule

Assignments & Solutions



Page updated on Dec. 26, 2014 8:00pm

News (latest on top):

·        (Dec. 26) It has been an honour and great pleasure to teach your class this term. I wish you all the best in 2015 and in your future career. Any feedback for improving the quality of the course presentation is more than welcome.

·        (Dec. 26) Unofficial marks for assignment 4 and the final exam are posted.

·        (Dec. 19) Please note typo in Assignment 3 solutions, Question 6: First line should say <partial gen. of Ax 6> (and not Ax 5).

·        (Dec. 13) Some info about the final exam:

o   Boolean Logic: 25-30%

o   Predicate Logic: 70-75%

o   No induction!

o   Probably a bonus question

·        (Dec. 13) Office hours for next week: Mon, Dec. 15, 1pm to 3pm; and Fri. Dec. 19, 1pm-3pm.

·        (Dec. 7) Office hour for questions regarding marking of assignment 3: Monday, Dec. 5, 2014 at 12:00pm (noon) in LAS 2017. (Contact Feng: gaofeng@cse.yorku.ca)

·        (Dec. 3) Although I am planning to be in LAS 3032 at least on Mondays and Wednesdays in the following weeks, it would be better if you email me if you want to be sure.

·        (Dec. 3) I have marked medical notes with M in the grades list. Please check to make sure yours is marked, if you have given me one. Otherwise you will get a zero in your midterm test (30% of the final grade).

·        (Dec. 3) Unofficial Marks for Assignment 3 are posted. You can get your assignments in the tutorial tomorrow.

·        (Dec. 3) Please note correction of asg4, Q12! I apologize for the inconvenience! With the first universal quantifier, it is actually a valid and provable rule (done in class).

·        (Dec. 3) Deadline of Assignment 4 is extended until 1:15pm. You can hand it in at the beginning of class, or use the drop box. Assignments later than 1:15pm will not be accepted (since I will post the solutions and review them in the class).

·        (Dec. 3) Please note correction in Assignment 3 solutions, Question 4(f).

·        (Nov. 19) Assignment 4 is posted and is due on Wednesday, December 3 at 12:30pm.

·        (Nov. 11) Unofficial marks for assignment 2 are posted. You can get your assignment back at the tutorial on Thursday this week. If you have any questions with its marking, please see Feng (gaofeng@cse.yorku.ca) on Friday Nov.11, between 12pm to 1pm in LAS 2013.

·        (Nov. 10) Please note some corrections in assignment 3 (questions 5, 6, and 8).

·        (Nov. 8) Assignment 3 is posted and is due on Wednesday, Nov. 19 at 12:30pm.

·        (Nov. 5) Unofficial marks for the midterm test are posted. Good news: the last question is considered as bonus, so the marks are out of 27 (and not 31). You can see your papers at the tutorial tomorrow.

·        (Oct 24) Tutorial today in Chemistry building room 129 @12pm.

·        (Oct 22) Solutions to midterm questions are posted.

·        (Oct.21) Only this week: the tutorial will be on Friday, Oct. 24, at 12pm to 1pm in location TBA (No tutorial on Thursday this week!) If you did not collect your assignment 1 yet, you can get it during the tutorial.

·        (Oct. 21) Office hour for questions regarding marking of assignment 1: Thursday, Oct.23, 2014 at 9:30am to 10:30am in LAS 2013. (contact Reza: rts@cse.yorku.ca)

·        (Oct. 20) ***Important***: Students with last name starting with A to G, write their midterm in CLH K (usual class location). Students with last name starting with H to Z, write in VH B (Vari Hall B). Please bring your ID card with you, and make sure you go to the correct room. The test starts at 1pm sharp!

·        (Oct.20) Solutions to assignment 2 are posted- corrected Question 2(b).

·        (Oct. 20) Unofficial grades for assignment 1 are posted.

·        (Oct. 17) Tentative date for the final exam: Dec. 20 @7pm.

·        (Oct. 17) For sample midterm questions, see 2012 course webpage.

·        (Sep. 29) Assignment 2 is posted and is due on October 20 at 12pm.

·        (Sep. 29) Solutions to assignment 1 posted (see bottom of this page).

·        (Sep. 27) Assignment 1 is due on Monday, Sep. 29 at 2:45pm. Please drop your assignment in 1090 drop box next to main office in Lassonde building. Don’t forget your name and student number!

·        (Sep. 27) Here is the fact sheet of axioms and theorems.

·        (Sep. 18) The tutorial room has changed to HNES 035. Unfortunately there has been a double booking for the other room. I apologize for the inconvenience.

·        (Sep. 15) Assignment 1 is posted and is due on September 29. Please note that “The homework must be each individual’s own work. While consultations with the instructor, tutor, and among students, are part of the learning process and are encouraged, nevertheless, at the end of all this consultation each student will have to produce an individual report rather than a copy (full or partial) of somebody else’s report.”[ Prof. Tourlakis' course outline]

·        (Sep. 9) The location for tutorials is R S205 (Ross building south). Tutorials start Thursday, September 18 @12pm.

·        (Sep. 4) First class will be held on Monday, September 8, 2014 at 1pm. I look forward to seeing you in CLH K.


Course Schedule (tentative):




M Sep 08

W Sep 10

Course Outline and policies

Introduction to the course

Boolean Formula



M Sep 15

W Sep 17


Truth tables, tautologies



M Sep 22

W Sep 24

Axioms and rules of inference

Hilbert Proofs


M Sep 29

W Oct 1

Assignment 1 due on Sep. 29 @2:45pm

Equational proofs



M Oct 6

W Oct 8

More on Equational proofs

M Oct 13 xxx

W Oct 15

No class on Monday- Thanksgiving

Deduction theorem and Resolution


M Oct 20


W Oct 22

Assignment 2 due on Oct. 20 @12:00pm

Review of Boolean Logic

Midterm exam (Oct 22)

(1pm-2:30pm in CLH K and VH B- depending on your last name- see above news)


M Oct 27

W Oct 29 xxx

Soundness and Completeness

Co-curricular days (Oct.29-Nov.2)


Proof for a Weak Post’s Theorem

M Nov 03

W Nov 05

Predicate Logic

Axioms of first order logic


M Nov 10

W Nov 12

Generalization and Specialization

Weak and Strong Leib


M Nov 17

W Nov 19

Auxiliary Variable Metatheorem

Assignment 3 due on Nov. 19 @12:30pm


M Nov 24

W Nov 26

Interpretations, soundness and completeness in Predicate Logic

11_1st Order Semantics

M Dec 01

W Dec 03

Review of Predicate Logic

Last Day of class

December 20

Final Exam: Sat., Dec. 20, 7pm-10pm in TC REXALL




·        Assignment 1 due on Sep. 29 @2pm – Please drop your assignment in the course drop box on first floor of Lassonde building, next to main office

·        Assignment 2 due on Oct. 20 @12:00pm

·        Assignment 3 due on Nov. 19 @12:30pm

·        Assignment 4 due on Dec. 3 @ 12:30pm



·        Solutions to assignment 1

·        Solutions to assignment 2

·        Solutions to midterm test

·        Solutions to assignment 3

·        Solutions to assignment 4