Preface

This book is a first course in Formal Logic. It is intended primarily for use at the college level. However, it can also be used for advanced secondary school students, and it can be used at the start of graduate school for those who have not yet seen the material.

There are just two prerequisites. The book presumes that the student understands sets and set operations, such as union, intersection, and so forth. It also presumes that the student is comfortable with symbolic manipulation, as used, for example, in solving high-school algebra problems. Nothing else is required.

The approach to teaching Logic used here emerged from more than 10 years of experience in teaching the logical foundations of Artificial Intelligence and more than 20 years of experience in teaching Logic for Computer Scientists. The result of this experience is an approach that differs from that taken by other books in Logic in two essential ways, one having to do with content, the other with form.

The primary difference in content concerns that semantics of the logic that is taught. Like many other books on Logic, this one covers first-order syntax and first-order proof theory plus induction. However, unlike other books, this book starts with Herbrand semantics rather than the more traditional Tarskian semantics.

In Tarskian semantics, we define an interpretation as a universe of discourse together with a function (1) that maps the object constants of our language to objects in a universe of discourse and (2) that maps relation constants to relations on that universe. We define variable assignments as assignments to variables. We define the semantics of quantified expressions as variations on variable assignments, saying, for example, that a universally quantified sentence is true for a given interpretation if and only if it is true for every variation of the given variable assignment. It is a mouthful to say and even harder for students to understand.

In Herbrand semantics, we start with the object constants, function constants, and relation constants of our language; we define the Herbrand base (i.e. the set of all ground atoms that can be formed from these components); and we define a model to be an arbitrary subset of the Herbrand base. That is all. In Herbrand semantics, an arbitrary logical sentence is logically equivalent to the set of all of its instances. A universally quantified sentence is true if and only if all of its instances are true. There are no interpretations and no variable assignments and no variations of variable assignments.

Although both approaches ultimately end up with the same deductive mechanism, we get there in two different ways. Deciding to use Herbrand semantics was not an easy to choice to make. It took years to get the material right and, even then, it took years to use it in teaching Logic. Although there are some slight disadvantages to this approach, experience suggests that the advantages significantly outweigh those disadvantages. This approach is considerably easier for students to understand and leaves them with a deeper understanding of what Logic is all about. That said, there are some differences between Herbrand semantics and Tarskian semantics that some educators and theoreticians may find worrisome.

First of all, Herbrand semantics is not compact - there are infinite sets of sentences that are inconsistent while every finite subset is consistent. The upshot of this is that there are infinite sets of sentences where we cannot demonstrate unsatisfiability with a finite argument within the language itself. Fortunately, this does not cause any practical difficulties, since in all cases of practical interest we are working with finite sets of premises.

One significant deficiency of Herbrand semantics vis a vis Tarskian semantics is that with Herbrand semantics there are restrictions on the cardinality of the worlds that can be axiomatized. Since there is no external universe, the cardinality of the structures that can be axiomatized is equal to the number of ground terms in the language. (To make things easy, we can always choose a countable language. We can even choose an uncountable language, though doing so would ruin some of the nice properties of the logic. On the positive side, it is worth noting that in many practical applications we do not care about uncountable sets. Although there are uncountably many real numbers, remember that there are only countably many floating point numbers.) More significantly, recall that the Lowenheim-Skolem Theorem for Tarskian semantics assures us that even with Tarskian semantics we cannot write sentences that distinguish models of different infinite cardinalities. So, it is unclear whether this restriction has any real significance for the vast majority of students.

Herbrand semantics shares most important properties with Tarskian semantics. In the absence of function constants, the deductive calculus is complete for all finite axiomatizations. In fact, the calculus derives the exact same set of sentences. When we add functions, we lose this nice property. However, we get some interesting benefits in return. For one, it is possible with Herbrand semantics (with functions) to finitely axiomatize arithmetic. As we know from Godel, this is not possible in a first-order language with Tarskian semantics. The downside is that we lose completeness. However, it is nice to know that we can at least define things, even though we cannot prove them. Moreover, as mentioned above, we do not actually lose any consequences that we are able to deduce with Tarskian semantics.

That's all for what makes the content of this book different from other books. There is also a difference in form. In addition to the text of the book in print and online, there are also online exercises (with automated grading), some online Logic tools and applications, online videos of lectures, and an online forum for discussion.

The online offering of the course began with an experimental version early in the 2000s. While it was moderately successful, we were at that time unable to combine the online materials and tools and grading program with videos and an online forum, and so we discontinued the experiment. Recently, it was revived when Sebastian Thrun, Daphne Koller, and Andrew Ng created technologies for comprehensive offering online courses and began offering highly successful online courses of their own. With their technology and the previous materials, it was easy to create a comprehensive online course in Logic. And this led to completion of this book.

Thanks also to Pat Suppes, Jon Barwise, John Etchemendy, David-Barker Plummer, and others at the Stanford Center for the Study of Language and Information for their pioneering work on online education in Logic. Language, Proof, and Logic (LPL) in particular is a wonderful introduction to Logic and is widely used around the world. Although there are differences between that volume and this one in theory (especially semantics) and implementation (notably the use here of browser-based exercises and applications), this volume is in many ways similar to LPL. In particular, this volume shamelessly copies the LPL tactic of using online worlds (like Tarski's World) as a teaching tool for Logic.

And thanks as well to the thousands of students who over the years have had to endure early versions of this material, in many cases helping to get it right by suffering through experiments that were not always successful. It is a testament to the intelligence of these students that they seem to have learned the material despite multiple bumbling mistakes on our part. Their patience and constructive comments were invaluable in helping us to understand what works and what does not.

Finally, we need to acknowledge the enormous contributions of a former graduate student - Tim Hinrichs. He is a co-discoverer of many of the results about Herbrand semantics, without which this book would not have been written.