A Quote
[...] The story suggest that assertions, or simply Boolean expressions, are really needed in programming. But it is not enough to know how to write Boolean expressions; one needs to know how to reason with them, how to simplify them, to prove that one follows from another, and to prove that one is not true in some state, and so forth. And, later on, we will see that it is necessary a kind of assertion that it is not part of the usual Boolean expression language of Pascal, PL/1 or FORTRAN, the "quantified" assertion. [...] More importantly, the study of program correctness proofs has led to the discovery and elucidation of methods for developing programs. Basically one attempts to develop a program and its proofs hand-in-hand, with the proof ideas leading the way! If the methods are practiced with care, they can lead to programs that are free of errors, that take less time to develop and debug, and that are much more easily understood (by those who have studied the subject).
David Gries: The Science of Programming.
Part O:
Why Use Logic? Why Prove Programs Correct?
The exam will consists of solving a list of problems (similar to but
easier than the ones in the homework).
You may use your class notes and a copy of the notes that I have
been posting up to now (make sure that you have the latest version
of the notes, or that you have corrected all the typos found up to now).
You are not allowed to use books or any other material. You may use
a pocket calculator to help you with computations, but you do not need
to fully carry out complicated computations - e.g., it is OK to leave
24!/(15!9!) instead of 1307504 as a final answer.
725-310-0 Mathematical Foundations of Computer Science
Basic concepts of finite and structural mathematics. Sets, axiomatic
systems, the propositional and predicate calculi, and graph
theory. Application to computer science: sequential machines, formal
grammars, and software design. Prerequisites: 725-A10 or 725-A11 and
435-B14-3. Prerequisite for: 725-C22, 725-C32, 725-C39, 725-C43,
725-C51. Course director: Brad Adelberg
Ralph P. Grimaldi: Discrete and Combinatorial Mathematics,
4th edition, Addison-Wesley.
Miguel A. Lerma:
Notes on Discrete Mathematics. (See bellow.)
The problem sessions will be held on Thursdays under the TA's
supervision.
The homework assignments will be posted on this web page.
There will be one one-hour Midterm Exam and one two-hour Final Exam.
No make-up exams will be given. In the event of an extreme and well
documented absence (such as hospitalization) the final may be weighted
to count for the missing exam. In the case of a missed exam, contact
the instructor as soon as possible.
Depending on various circumstances, the schedule shown bellow may
experiment small modifications.
The "sections" listed on the 4th column are from
Grimaldi's book.
The "Suggested Exercises" column contains some exercises from the book
that you may find useful to try. They are not homework nor need to be
turned in.
The complete set of notes is
here. However I do not recommend
to download the whole set until the end of the quarter, since
I may still make some changes to the notes.
Email:
mlerma at math dot northwestern dot edu
Announcements
Feedback
Click the following link and tell me your thoughts:
Feedback
Course Description
Teachers
Instructor
Teaching Assistant
Name
Miguel A. Lerma
Dianwen Zhu
Office
Lunt 203
Lunt B10
Phone
1-8020
7-1956
E-mail
mlerma@math.nwu.edu
zhudw@math.nwu.edu
Office Hours
by appointment
TH 2:30-4:30pm
and by appointment
Teaching in
Tech M345
Lunt 105
Class Logistics
Lectures and Homework Assignments
Note: I am going to be releasing notes ("Notes on Discrete
Mathematics", in PDF format) that you can download by clicking in the
links of the "subject" column of the syllabus bellow. The table of
contents and the introduction are here:
Related links