Lassonde School of Engineering Course Outline (Fall 2017) |
SC/MATH 1090 3.0 A | Introduction to Logic for Computer Science |
Professor George Tourlakis | Classes: CLH H 13:00-14:30, Mondays and Wednesdays. First Class: September 11, 2017 |
DON'T PANIC :-) (This course is very similar to a
serious programming
course; but easier)
Course Description: Note: This course is a degree program
requirement for
Computer Science, Computer
Security, and Computer and Software Engineering
majors. It is expected
and recommended
to be taken in the second
year of your studies as it is a prerequisite for a
number of core (=
required) 3rd year EECS 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 EECS 1021 3.0
or EECS1022 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 spends the rest of the
course on
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 learn 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 readily agree 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 engineering. Besides, any science that requires you to reason correctly to reach conclusions uses logic. Prerequisite:
MATH 1190 3.00 or EECS/MATH 1019 3.00. Course work and evaluation: There will be several (>= 4) homework assignments worth 24% 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. Follow these links to
familiarise
yourselves with Senate's and Lassonde School's
expectations regarding Academic
Honesty, and Academic
Integrity. Please also familiarise yourself
with many other Senate
policies, in particular, with those about Academic
Accommodation
for
Students
with Disabilities, Religious
Accommodation, Repeating
Passed
or
Failed
Courses for Academic Credit. Please also check these
two links! Student
Rights
and Responsibilities and Counseling
and
Disabiliy Services.
The
concept of "late assignments" does not
exist in this course
(because full solutions are posted on the due
date). Last date
to drop a Fall 2017
(3-credit) course without receiving a grade is
Nov.
10, 2017. There will also be one
mid-term (in-class) test worth 33% Note
Date/Time: Monday,
October
30, 2017.
13:00-14:20. 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 acceptable reason are deemed to have been
written and failed and are graded "0"
(F).
Finally, there will be a Final Exam during the University's Exam period. It will be worth 43%. Text: G. Tourlakis, Mathematical Logic, John Wiley & Sons, 2008. ISBN 978-0-470-28074-4 Learning Objectives: Students are expected to:
If time permits:
We will attempt
to make time to cover a very brief
introduction to computability
from the Appendix of
the text. Last changed: Aug. 21,
2017 |