First-Order Logic and Automated Theorem Proving

by Melvin Fitting

This monograph on classical logic presents fundamental concepts and results in a rigorous mathematical style. Applications to automated theorem proving are considered and usable programs in Prolog are provided. This material can be used both as a first text in formal logic and as an introduction to automation issues, and is intended for those interested in computer science and mathematics at the beginning graduate level. The book begins with propositional logic, then treats first-order logic, and finally, first-order logic with equality. In each case the initial presentation is Boolean valuations for propositional logic, models for first-order logic, and normal models when equality is added. This defines the intended subjects independently of a particular choice of proof mechanism. Then many kinds of proof procedures are tableau, resolution, natural deduction, Gentzen sequent and axiom systems. Completeness issues are centered in a model existence theorem, which permits the coverage of a variety of proof procedures without repetition of detail. In addition, results such as compactness, interpolation, and the Beth definability theorem are easily established. Implementations of tableau theorem provers are given in Prolog, and resolution is left as a project for the student.

Genres: Logic, Philosophy

257 pages, Paperback

First published April 28, 1990

About the author

Melvin "Mel" Fitting (born January 24, 1942) is a logician with special interests in philosophical logic and tableau proof systems. He was a Professor at City University of New York, Lehman College and the Graduate Center from 1968 to 2013. At the Graduate Center he was in the departments of Computer Science, Philosophy, and Mathematics, and at Lehman College he was in the department of Mathematics and Computer Science. He is now Professor emeritus.

Fitting was born in Troy, New York. His undergraduate degree is from Rensselaer Polytechnic Institute, and his doctorate is from Yeshiva University, both in mathematics. His thesis advisor was Raymond Smullyan.

In June 2012 Melvin Fitting was given the Herbrand Award by CADE, for distinguished contributions to automated deduction.

A loose motivation for much of Melvin Fitting's work can be formulated succinctly as follows. There are many logics. Our principles of reasoning vary with context and subject matter. Multiplicity is one of the glories of modern formal logic. The common thread tying logics together is a concern for what can be said (syntax), what that means (semantics), and relationships between the two. A philosophical position that can be embodied in a formal logic has been shown to be coherent, not correct. Logic is a tool, not a master, but it is an enjoyable tool to use