Symbolic Logic

Dr. Stephen Bloch

office 203 Post Hall

phone 877-4483

email`sbloch@adelphi.edu`

Web page`http://www.adelphi.edu/sbloch/`

Class Web page`http://www.adelphi.edu/sbloch/class/355/`

Office hours: TTh 1:30-4:00; W 2:30-4:00; other times by appointment.

office 203 Post Hall

phone 877-4483

Web page

Class Web page

Office hours: TTh 1:30-4:00; W 2:30-4:00; other times by appointment.

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.

Last modified: Monday, August 31st, 2009 3:55:10pm

HTML conversion by TeX2page 20070609