Math 1090 Course Syllabus

Introduction to Logic for Computer Science

Announcements:

Any additional information added to this syllabus during the term can be found here at this web page http://www.math.yorku.ca/~zabrocki/math1090
There are three sections for this course
Mondays 10:30-11:30 Ross N501
Tuesdays 11:30-12:30 Ross N501
Wednesdays 12:30-1:30 Ross N501
You can go here to get help on the problems.
Wednesday, November 13th I will not be able to make office hours, if you need to see me we can reschedule for later that day
The final exam is Tuesday December 10 from 7pm to 9pm. Details will follow
Need a copy of the theorem list? Versions small meduim and large.
There is class Monday, December 2 and Tuesday, December 3. For the most part, these days will be review material for the course.
I will have office hours on Friday, December 6 from 2:00-3:00 and Tuesday December 10 from 5-6pm. My Wednesday office hours for December 4 are cancelled.


Lecturer: Mike Zabrocki
Office: South 615 Ross
Telephone: 736-2100 Ext 33955
E-mail: zabrocki@mathstat.yorku.ca
WWW: http://www.math.yorku.ca/~zabrocki
Normal Office hours: W 10a.m. - 11a.m. (except Wed, Nov 13), F 2pm - 3pm and by appointment.

Lectures: MWF 3:30 - 4:20 in CLH-A

Tutorials: T.B.A.

Text: Gries and Schneider, A Logical Approach to Discrete Math.

Syllabus: The core consists of Chapters 1, 2, 3, 4, 6.2, 8, 9 of the text.

Purpose of this course:

To learn the syntax and semantics of propositional and predicate logic.  The proper understanding of propositional logic is fundamental to the most basic levels of computer programming, while the ability to correctly use variables, scope and quantifiers is crucial in the use of loops, subroutines, and modules, and in software design. Logic is used in many diverse areas of computer science including digital design, program verification, databases, artificial intelligence, algorithm analysis, and software specification. We will not follow a classical treatment of logic. Instead we will use an "equational'' treatment. This equational approach will also be the basis for the topics in discrete mathematics treated in MATH 2090.

We will learn a notion of proof within the context of a system of propositional logic.  You will need to be able to translate certain types of statements in English into logical statements as well as understand the concept of a propositional statement being valid or satisfiable.  By the end of the course you should be able to deduce theorems using a system of proofs based on rules of deduction using logical equivalence.  We will also try to relate these notions to logical puzzles, arguments made in English, digital circuits and computer programing.

Homework:
Homework will be assigned on a weekly basis and posted on to this web site as well as announced in class.  These problems will be preparation for the quizzes and tests that you will have during class so I will do my best to encourge that you do them.
Quizzes:
There will be an in class quiz approximately once a week during the Friday class. The quiz will be 15 minutes long and consist of one or two questions to try to help you make sure that you are on track and understand the material for the week. A component of your grade will be based on the best 5 of the 8 in class quizzes. If you are unable to make a few of them, it is not a cause for worry since you will be able to drop the lowest 3. I will not offer makeup quizzes, you are responsible for attending the Friday classes when the quizzes are offered. They will be on the following dates:
September 13, 20, 27;  October 4, 25;  November 8, 15, 29;
Tests:
There will be two in class tests and a final exam.  The two in class tests are on Friday, October 18 and Friday, November 22.  The final exam will be scheduled by the university system at a later date.

Evaluation:

Quizzes various dates (see above) 15% (best 5 of 8)
Class Tests October 18, November 22 40%
Final Exam Examination Period 45% 

Note: If you miss a test and provide a certificate indicating clearly that you were unable to write the test for reasons beyond your personal control, the weight of the test will be transferred to the final exam. Otherwise, the mark for the missed test will be 0.

The last date to drop the course without academic penalty is November 8 It is extremely important to realistically assess your course performance prior to this date.

Lecture information:

Week
Sections
Exercises Solutions Quiz
1
Ch1.1,1.2,1.3,1.5, Ch 2
1.7, 1.8, 1.9, 2.2, 2.7 hw week 1 Quiz 1
2
Ch2, start Ch 3
2.2, 2.7, 3.2, 3.3, 3.7 hw week 2 Quiz 2
3
Ch 3
3.8, 3.9, 3.11, 3.17, 3.18 hw week 3 Quiz 3
4
Ch 3
do proofs! (all of 'em) slns in class Quiz 4
5
Ch 3
do proofs! (all of 'em)
esp. (3.46), (3.52) and (3.55)
hw week 5 No quiz this week
6
Ch 3
do proofs! (all of 'em) slns in class, Midterm 1
7
Ch 3, Ch4?
do proofs! (all of 'em) 3.76-3.82c Quiz 5
8
Ch4
some problems hw week 8 No quiz this week
9
Ch8
some problems hw week 9 Quiz 6
10
Ch8
some problems hw week 10 Quiz 7
11
Ch 9
Do all theorems in Ch 9 in class Midterm 2
12
Ch 9
midterm 2 from 2001 1090,
proof of (*x,y|R:P) = (*y,x|R:P)
Quiz 8
13
Ch 9
review questions, more review solutions, 9.29 Mon and Tues class
No quiz.

Important dates to remember:

Friday, September 20, 2002: the last day to add a course in the fall term without the permission of the instructor
Friday, October 4, 2002: the last day to add a course for the fall term with the written permission of the instructor
Friday, November 8, 2002:  the last day to drop a fall course without receiving a grade
Friday, November 22, 2002:  Midterm 2
Tuesday, December 3, 2002:  the last day of classes for the fall term
Tuesday, December 10, 2002: Final exam
 

Resources:

  • A Model Proof in the Logic E in (html) and (postscript) and (pdf).
  • Professor Ganong's notes supplementing the text's treatment of CONtextual substitution and the extended Leibniz rules. CONtextual substitution supplement and Leibniz supplement
  • A reference for the material in chapter 2, Kemeny, Snell, Thompson supplement.
  • Professor Kemeny's 1983 Lectures are available in RealPlayer format.