August 29, 2003
This course assumes you have taken and passed CSC/MTH 156 (``Discrete Structures'').
Logic is a way to come to know a fact without observing it directly. If your roommate always gets drunk on Saturday nights, and today was Saturday, you don't have to smell your roommate's breath to know that (s)he is drunk. There are, of course, many more subtle applications of logic, and frequently it's not so obvious what conclusions you can draw from what. The careful study of this question, and the field of logic itself, dates approximately to Aristotle. Aristotle's treatment of logic was so widely respected that the field changed little for two thousand years, until the 19th century when mathematicians like Boole, Frege, Peano, and Peirce cleaned it up to roughly its present state.
Since logic, like other branches of mathematics, has trouble dealing with ambiguous statements, and since English is a notoriously ambiguous language, logicians (and other mathematicians) usually work in a language of their own, in which every term and symbol has a clear, well-defined meaning -- the ``language of first-order logic'', or FOL as the textbook calls it.
We'll start by examining relations, properties that can be either true or false of specific objects. Relations can be combined using Boolean connectives such as ``not'', ``and'', ``or'', ``implies'', and ``iff'' (short for ``if and only if''), and we'll discuss how to use, prove, and disprove statements involving those connectives. Then we'll add quantifiers to the language, so we can talk about ``all'' objects or ``at least one'' object, and discuss how to use, prove, and disprove statements involving quantifiers. Finally, we'll visit some topics of particular importance in computer science: mathematical induction and, if we have time, computer theorem-proving (which underlies the Prolog programming language).
The main text for this course is Language, Proof and Logic, by Jon Barwise and John Etchemendy. We'll work through most of chapters 1-13, plus part of chapter 16, by the end of the semester. You are responsible for everything in the reading assignments, whether or not I discuss it in a lecture.
The textbook comes with a CD-ROM containing not only the full text of the book but a number of software packages which you'll need in order to do your homework. The software should run on either Macintosh or Windows; you may use whichever you prefer. One of the software packages, ``Submit'', requires Net access to submit your homework to an automatic grading program; an option in the program allows you to submit the homework to me for a grade, or to just check it so you can see what's incorrect and fix it before submitting it for a grade. Printed on the CD-ROM envelope is a ``Book ID#'', which you'll need in order to use the auto-grader, so don't lose it. Note: the Book ID# is non-transferrable, so if you buy a used copy of the book, you probably won't be able to submit your homework to the autograder. In other words, don't buy a used copy of the book!
I expect you to have read the specified chapters in the textbook before the lecture that deals with that topic; this way I can concentrate my time on answering questions and clarifying subtle or difficult points in the textbook, rather than on reading to you, which will bore both of us. Please read ahead!
As I write this, I plan to give several homework assignments, a midterm exam, and a final exam, as well as a ``brownie point'' grade which is my subjective impression of how seriously you're taking the course. The midterm and the ``brownie points'' are each weighted the same as a homework assignment, and the final exam is equivalent to two homework assignments, in determining a semester grade. You earn brownie points by asking good questions in class, coming to me for help when you need it, etc. You lose brownie points by cheating, by being lost and not doing anything about it, and by annoying the professor.
The exams must be taken at the scheduled time, unless arranged in advance or prevented by a documented medical or family emergency. If you have three or more exams scheduled on the same date, or a religious holiday that conflicts with an exam or assignment due date, please notify me in writing within the first two weeks of the semester in order to receive due consideration. Exams not taken without one of the above excuses will get a grade of 0.
Homework assignments will be accepted late, with a penalty of 20% per 24 hours or portion thereof after they're due. An hour late is 20% off, 25 hours late is 40% off, and after five days it gets a zero. Any homework turned in after the last day of class will get a zero.
Most of the assignments in this class are to be done individually. You may discuss general approaches to a problem with classmates, but you may not copy large pieces of homework solutions. If you do, all the students involved will be penalized.
All work on an exam must be entirely the work of the one person whose name is at the top of the page. If I have evidence that one student copied from another on an exam, both students will be penalized; see above.