August 31, 2009
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 an artificial language, in which every term and symbol has a clear, well-defined meaning. In fact, we’ll look at two such languages: the language of sentential or propositional logic, which only deals statements as a whole, and the language of predicate or first-order logic, in which statements are thought of as properties of objects.
For each of these languages, we’ll talk both within the language and about it. Within a language, we need to know how to translate ordinary English sentences into the language so we can take arguments from the real world and subject them to the test of logic; we need to know what statements in the language follow logically from what others; we need to know how to construct and analyze proofs within the system.
But then we’ll step back and discuss the language and its logic from the outside: what can one say about all possible statements in the language, or about all possible proofs, or about alternative ways the language might have been designed instead? We’ll discuss what it means for a statement in a formal language to be “true”, then prove (outside the system) that anything provable in the system must be true, and conversely that anything true (and expressible within the language) must be provable in the system. All very nice and tidy.
Finally, we’ll look at the most common application of logic: to mathematics. It turns out that if your logical system is powerful enough to talk about interesting mathematics, it does not behave so nicely: one can construct statements about the natural numbers that are true but cannot be proven.
The main text for this course is Herbert Enderton’s A Mathematical Introduction to Logic. We’ll work through chapters 1, 2, and part of 3 by the end of the semester. You are responsible for everything in the reading assignments, whether or not I discuss it in a lecture.
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!
Supplementary recommended reading:
Logic, Sets, and Recursion, by Robert L. Causey. I was considering using this as the main textbook, but thought it didn’t go far enough. However, it gives more detailed explanations of some things that Enderton covers only briefly.
Logicomix: An Epic Search for Truth, by Apostolos Doxiadis, Christos Papadimitriou, Alecos Papadatos, and Annie di Donna. A “graphic novel” (comic book) presentation of the history of logic in the late 19th and early 20th century; it adds a personal, “real” note to the personalities and historical developments.
Gödel, Escher, Bach: an Eternal Golden Braid, by Douglas Hofstadter. An 800-page tour de force that reads like a novel — it was my bedtime reading for a month or so in my teens — tying together concepts of artificial intelligence, logical incompleteness, self-reference, etc.
As I write this, I plan to give four or five homework assignments and a final exam, as well as a “brownie point” grade which is my subjective impression of how seriously you’re taking the course. Each assignment, the final, and the “brownie points”, are weighted equally in determining a semester grade. You earn brownie points by asking and answering 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 exam 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.
The Adelphi University Code of Ethics applies to this course; look it up on the Web at http://academics.adelphi.edu/policies/ethics.php .
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.