Subject Matter

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", 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 computer theorem-proving (which underlies the Prolog programming language).