York University- Department of Computer Science & Engineering

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

Fall 2012


Course director:

Vida Movahedi (vida@cse.yorku.ca)


Tuesdays and Thursdays, 10:00am to 11:30am in VH C

Office hours:

Thursdays, 12:00-14:00 in LAS 3026



Starting September 19

Wednesdays, 12:30 to 13:30 in Winters 118

TA: Stephen Voland (svoland@cse.yorku.ca)


Additional Office Hours

Starting September 17, except Oct 8 and Oct 29

Mondays, 12:00 to 13:00 in TA room (LAS 2013)

Also on Wednesday, Oct 10, 2:00-3:00pm

TAs:     Jianhui Chen (Jianhui@cse.yorku.ca)

            Stephen Voland (svoland@cse.yorku.ca)

            Elliott Tsai [elliott@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. 17, 2012 7:30pm

News (latest on top):

·         It was a great pleasure to teach your class. Thank you for every day of it! My best wishes for each and every one of you.

·         Assignment 4 marks are posted.

·         Unofficial marks for the final exam are posted. I have office hours on Friday, Dec. 14, 11am to 1pm, in case you have any questions.

·         I have office hours on Tuesday, Dec. 4, 12pm to 2pm in LAS 3026.

·         In the final exam, you will have 4 questions (about 35% of the marks) from Boolean Logic (Chapters 1-3), and 6 questions (about 65% of the marks) from Predicate Logic (Chapters 4-8). See you on Wednesday, December 5, at 9am in Accolade Building East, room ACE 001.

·         Solutions to assignment 4 are posted.

·         Please see this correction for what we were discussing in class on Nov 29!

·         Unofficial marks for assignment 3 are posted.

·         Correction for question 11, assignment 4: Please add the condition that x dnof in B.

·         Assignment 4 is posted. Due December 3, 2:00pm.

·         Solutions to Assignment 3 are posted.

·         I have updated the fact sheet.

·         The marks for the assignment 2 are posted.

·         The marks for the midterm test are posted.

·         I have changed slide #11 of 08-Predicate (Part 1).

·         Assignment 3 is posted. Due November 15, 2:00pm.

·         Solutions to the midterm are posted.

·         Midterm exam: next Tuesday, October 23 at 10am in class.

·         Solutions to assignment 2 are posted.

·         Here is a fact sheet with axioms and some important theorems, to help you study the book and do the assignment. I will keep updating this file as we proceed.

·         Unofficial marks for Assignment 1 are posted. See link above.

·         Assignment 2 is posted. Due October 16, 2:00 pm.

·         Solutions to assignment 1 are posted.

·         Tutorials start tomorrow, September 19, at 12:30 in Winters College room 118.

·         Office hours for Mondays are changed to 12:00 to 1:00pm, due to TA room booking conflicts.

·         Assignment 1 is posted. Due September 25, 2:00pm. Please include a cover page, with your name, course number and assignment number. Drop in course assignment box (right next to CSE main office, main floor in LAS building) before deadline. Make sure you drop it in the correct drop box!

·         Your TA will hold office hours in LAS 2013 on Monday, September 17. Bring your questions!

·         First class will be held on September 6, 2012 at 10am. I look forward to seeing you in VH C.


Course Schedule (tentative):




R Sep 6

Course Outline and policies

Introduction to the course

Introduction to MATH1090

T Sep 11

R Sep 13

Boolean Formula


01-Boolean Formulae

02- Induction

T Sep 18

R Sep 20

Truth tables, tautologies

03- Truth Tables

T Sep 25

R Sep 27

Assignment 1 (Due Sep. 25, 2:00pm)

Axioms and rules of inference, Hilbert Proofs

04- Theorem Calculation

T Oct 2

R Oct 4

Equational proofs

05- Equational Proofs

T Oct 9

R Oct 11

Deduction theorem & Resolution

06- Deduction & Resolution

T Oct 16

R Oct 18

Assignment 2 (Due Oct. 16, 2:00pm)

Review of Boolean Logic

T Oct 23

R Oct 25

Midterm exam (Oct.23)

(10am-11:30am in class)

Soundness and Completeness

 Predicate Logic




07- Boolean Semantics

08-Predicate Logic (part 1)

T Oct 30

More on Predicate Logic

Co-curricular days (Oct.31-Nov.4)

08-Predicate Logic (part 2)

Reading: Proof for a Weak Post's Theorem

T Nov 6

R Nov 8

Axioms of first order logic

Generalization and Specialization

09- Generalization and Leibniz

T Nov 13

R Nov 15

Weak and Strong Leib

Assignment 3 (Due Nov. 15, 2:00pm)



T Nov 20

R Nov 22

Auxiliary Variable Metatheorem

Interpretations, soundness and completeness in Predicate Logic

Course Evaluation (please come to evaluate this course, my TAs, and my teaching)

10- Existential Quantifier

11- First Order Semantics

T Nov 27

R Nov 29

Review of Predicate Logic

Last Day of class (Nov. 29)


Assignment 4 (Due Dec. 3, 2:00pm)

Final exam (Dec. 5, 9am-12pm in ACE001)




·         Assignment 1- Posted September 14, 2012, Due September 25,2012, at 2:00pm in course assignment box

·         Assignment 2- Posted September 25, 2012, Due October 16, 2012, at 2:00 pm in course assignment box

·         Assignment 3- Posted November 1, 2012, Due November 15, 2012, at 2:00 pm in course assignment box

·         Assignment 4- Posted November 18, 2012, Due December 3, 2012, at 2:00 pm in course assignment box




·         Solutions to assignment 1 – Posted September 25, 2012

·         Solutions to assignment 2– Posted October 16, 2012

·         Solutions to midterm test– Posted October 25, 2012

·         Solutions to assignment 3– Posted November 15, 2012

·         Solutions to assignment 4– Posted December 03, 2012