|
Faculty of Arts and Faculty of Pure and Applied Science Course Outline (Fall 2005) |
| AS/SC/AK/ MATH 1090 3.0 | Introduction to Logic for Computer Science |
| Professor George Tourlakis | Classes: TR 10:00am-11:30am
CLH K |
|
DON'T PANIC :-) (This course is very similar to a serious programming
course; but easier)
Course Description: (See also the departmental course outline) Note: This course is a degree program requirement
for Computer Science and Computer Engineering majors. It is expected to
be taken not later than the second year of your studies as it is a
prerequisite for a number of core (= required) 3rd year CSE courses. Learning to use Logic, which is what this
course is about, is like learning to use a programming language. In the latter case,
familiar to you from courses such as CSE 1020 3.0, one learns the
correct syntax of programs, and also learns what the various
syntactic
constructs do and mean, that is, their semantics.
After that, one
embarks, for
the rest
of the course, on sets of increasingly challenging programming
exercises, so that the
student becomes proficient in programming in said language. We will do the exact same
thing in MATH1090: We will learn the syntax of the logical language,
that is, what syntactically correct proofs look like. We will
learn what various syntactic constructs "say" (semantics). We will be
pleased to know that correctly written proofs are concise and
"checkable" means toward discovering mathematical "truths". We will
also learn
via a lot of practice how to
write a large variety of proofs that
certify all sorts of useful "truths" of mathematics. While the above is our main
aim, to equip you with a Toolbox
that you can use to discover truths,
we will
also look at the Toolbox as an object
of study and study
some of its properties (this is similar to someone explaining to you
what a hammer is good for before you take up carpentry). This study
belongs to the "metatheory" of
Logic. The content of the course
will thus be: The syntax and semantics of propositional and predicate logic and how to build "counterexamples" to expose fallacies. Some basic and important "metatheorems" that employ induction on numbers, but also on the complexity of terms, formulas, and proofs will be also considered. A judicious choice of a few topics in the "metatheory" will be instrumental toward your understanding of "what's going on here". The mastery of these metatheoretical topics will make you better "users of Logic" and will separate the "scientists" from the mere "technicians". There are a number of methodologies for writing proofs, and we will aim to gain proficiency in two of them. The Equational methodology and the Hilbert methodology. In both methodologies an important required component is the systematic annotation of the proof steps. Such annotation explains why we do what we do and has a function similar to comments in a program.OK, one can grant that a computer science student needs to learn programming. But Logic? Well, 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, computability, complexity, and software specification. Besides, any science that requires you to reason correctly to reach conclusions uses logic. Prerequisite: One
OAC
in mathematics or equivalent, or AK/MATH 1710 6.0.
Course work and evaluation: There will be several homework assignments worth 40% of the total final grade. 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. See http://www.yorku.ca/secretariat/legislation/senate/acadhone.htm
to
familiarise yourselves with Senate's expectations regarding Academic
Honesty. The
concept of late assignments does not exist. Last date to drop a Fall 2005 (3
credit) course without receiving a grade is Nov. 11, 2005. There will also be one
mid-term
(in-class) test worth 20% <<<<
Date/Time: Tuesday,
October 11, 2005. 10:00am-11:20am. Note:
Missed tests with good reason
(normally medical, and well documented) will have their weight
transferred to the final exam. There are no "make up" tests.
Tests
missed for no reason are deemed to be written and marked "0" (F).
Finally, there will be a Final Exam worth 40% that will be common to the two sections. Text: David Gries and F.B. Schneider, A logical approach to Discrete Math. Springer, latest edition. Syllabus: Our
choice of topics corresponds to
Gries and Schneider, Chapters 3, 4, 6.1 (Hilbert proofs), 8
and 9. However, these chapters will be supplemented and drasticaly amended through web notes.
The authoritative
source of the How and Why will be these web notes, not the
text! The text on the other hand will provide us with a wealth of
valuable exercises. The first installment of the web notes, dated
August 23, 2005, was posted here
(PDF format).
These notes cover and amend Chapters 3, 4, and 6.1 of Gries and Schneider. There have been be periodic augmentations (and
"maintenance",
e.g., attention to typos) of the web notes, and such augmentations were
announced here under "News". The material
that corresponds to Chapters 8 and 9
is under construction, a construction that is progressing rapidly. The text is not available
for download as of Oct. 14, 2007. Last changed: Sep. 8, 2005 Last changed (text info) Oct. 15, 2007 |