. 2
( 107 .)


17 Advanced Topics in Propositional Logic 468
17.1 Truth assignments and truth tables . . . . . . . . . . . . . . . . 468
17.2 Completeness for propositional logic . . . . . . . . . . . . . . . 470
17.3 Horn sentences (optional) . . . . . . . . . . . . . . . . . . . . . 479
17.4 Resolution (optional ) . . . . . . . . . . . . . . . . . . . . . . . . 488

18 Advanced Topics in FOL 495
18.1 First-order structures . . . . . . . . . . . . . . . . . . . . . . . . 495
18.2 Truth and satisfaction, revisited . . . . . . . . . . . . . . . . . . 500
18.3 Soundness for fol . . . . . . . . . . . . . . . . . . . . . . . . . 509

Contents / ix

18.4 The completeness of the shape axioms (optional ) . . . . . . . . 512
18.5 Skolemization (optional) . . . . . . . . . . . . . . . . . . . . . . 514
18.6 Uni¬cation of terms (optional ) . . . . . . . . . . . . . . . . . . 516
18.7 Resolution, revisited (optional ) . . . . . . . . . . . . . . . . . . 519

19 Completeness and Incompleteness 526
19.1 The Completeness Theorem for fol . . . . . . . . . . . . . . . 527
19.2 Adding witnessing constants . . . . . . . . . . . . . . . . . . . . 529
19.3 The Henkin theory . . . . . . . . . . . . . . . . . . . . . . . . . 531
19.4 The Elimination Theorem . . . . . . . . . . . . . . . . . . . . . 534
19.5 The Henkin Construction . . . . . . . . . . . . . . . . . . . . . 540
19.6 The L¨wenheim-Skolem Theorem . .
o . . . . . . . . . . . . . . . 546
19.7 The Compactness Theorem . . . . . . . . . . . . . . . . . . . . 548
19.8 The G¨del Incompleteness Theorem
o . . . . . . . . . . . . . . . 552

Summary of Formal Proof Rules 557
Propositional rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
First-order rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559
Inference Procedures (Con Rules) . . . . . . . . . . . . . . . . . . . 561

Glossary 562

General Index 573

Exercise Files Index 585


The special role of logic in rational inquiry

What do the ¬elds of astronomy, economics, ¬nance, law, mathematics, med-
icine, physics, and sociology have in common? Not much in the way of sub-
ject matter, that™s for sure. And not all that much in the way of methodology.
What they do have in common, with each other and with many other ¬elds, is
their dependence on a certain standard of rationality. In each of these ¬elds,
it is assumed that the participants can di¬erentiate between rational argu-
mentation based on assumed principles or evidence, and wild speculation or
nonsequiturs, claims that in no way follow from the assumptions. In other
words, these ¬elds all presuppose an underlying acceptance of basic principles
of logic.
For that matter, all rational inquiry depends on logic, on the ability of logic and rational
people to reason correctly most of the time, and, when they fail to reason
correctly, on the ability of others to point out the gaps in their reasoning.
While people may not all agree on a whole lot, they do seem to be able to agree
on what can legitimately be concluded from given information. Acceptance of
these commonly held principles of rationality is what di¬erentiates rational
inquiry from other forms of human activity.
Just what are the principles of rationality presupposed by these disciplines?
And what are the techniques by which we can distinguish correct or “valid”
reasoning from incorrect or “invalid” reasoning? More basically, what is it
that makes one claim “follow logically” from some given information, while
some other claim does not?
Many answers to these questions have been explored. Some people have
claimed that the laws of logic are simply a matter of convention. If this is so, logic and convention
we could presumably decide to change the conventions, and so adopt di¬erent
principles of logic, the way we can decide which side of the road we drive
on. But there is an overwhelming intuition that the laws of logic are somehow
more fundamental, less subject to repeal, than the laws of the land, or even the
laws of physics. We can imagine a country in which a red tra¬c light means
go, and a world on which water ¬‚ows up hill. But we can™t even imagine a
world in which there both are and are not nine planets.
The importance of logic has been recognized since antiquity. After all, no

2 / Introduction

science can be any more certain than its weakest link. If there is something
arbitrary about logic, then the same must hold of all rational inquiry. Thus
it becomes crucial to understand just what the laws of logic are, and even
laws of logic
more important, why they are laws of logic. These are the questions that one
takes up when one studies logic itself. To study logic is to use the methods of
rational inquiry on rationality itself.
Over the past century the study of logic has undergone rapid and im-
portant advances. Spurred on by logical problems in that most deductive of
disciplines, mathematics, it developed into a discipline in its own right, with its
own concepts, methods, techniques, and language. The Encyclopedia Brittan-
ica lists logic as one of the seven main branches of knowledge. More recently,
the study of logic has played a major role in the development of modern day
computers and programming languages. Logic continues to play an important
part in computer science; indeed, it has been said that computer science is
just logic implemented in electrical engineering.
This book is intended to introduce you to some of the most important
goals of the book
concepts and tools of logic. Our goal is to provide detailed and systematic
answers to the questions raised above. We want you to understand just how
the laws of logic follow inevitably from the meanings of the expressions we
use to make claims. Convention is crucial in giving meaning to a language,
but once the meaning is established, the laws of logic follow inevitably.
More particularly, we have two main aims. The ¬rst is to help you learn
a new language, the language of ¬rst-order logic. The second is to help you
learn about the notion of logical consequence, and about how one goes about
establishing whether some claim is or is not a logical consequence of other
accepted claims. While there is much more to logic than we can even hint at
in this book, or than any one person could learn in a lifetime, we can at least
cover these most basic of issues.

Why learn an arti¬cial language?

This language of ¬rst-order logic is very important. Like Latin, the language is
not spoken, but unlike Latin, it is used every day by mathematicians, philoso-
phers, computer scientists, linguists, and practitioners of arti¬cial intelligence.
Indeed, in some ways it is the universal language, the lingua franca, of the sym-
bolic sciences. Although it is not so frequently used in other forms of rational
inquiry, like medicine and ¬nance, it is also a valuable tool for understanding
the principles of rationality underlying these disciplines as well.
The language goes by various names: the lower predicate calculus, the
functional calculus, the language of ¬rst-order logic, and fol. The last of

Why learn an artificial language? / 3

these is pronounced ef“oh“el, not fall, and is the name we will use.
Certain elements of fol go back to Aristotle, but the language as we know
it today has emerged over the past hundred years. The names chie¬‚y associ-
ated with its development are those of Gottlob Frege, Giuseppe Peano, and
Charles Sanders Peirce. In the late nineteenth century, these three logicians
independently came up with the most important elements of the language,
known as the quanti¬ers. Since then, there has been a process of standard-
ization and simpli¬cation, resulting in the language in its present form. Even
so, there remain certain dialects of fol, di¬ering mainly in the choice of the
particular symbols used to express the basic notions of the language. We will
use the dialect most common in mathematics, though we will also tell you
about several other dialects along the way. Fol is used in di¬erent ways in
di¬erent ¬elds. In mathematics, it is used in an informal way quite exten- logic and mathematics
sively. The various connectives and quanti¬ers ¬nd their way into a great deal
of mathematical discourse, both formal and informal, as in a classroom set-
ting. Here you will often ¬nd elements of fol interspersed with English or
the mathematician™s native language. If you™ve ever taken calculus you have
probably seen such formulas as:

∀ > 0 ∃δ > 0 . . .

Here, the unusual, rotated letters are taken directly from the language fol.
In philosophy, fol and enrichments of it are used in two di¬erent ways. As logic and philosophy
in mathematics, the notation of fol is used when absolute clarity, rigor, and
lack of ambiguity are essential. But it is also used as a case study of making
informal notions (like grammaticality, meaning, truth, and proof) precise and
rigorous. The applications in linguistics stem from this use, since linguistics
is concerned, in large part, with understanding some of these same informal
In arti¬cial intelligence, fol is also used in two ways. Some researchers logic and arti¬cial
take advantage of the simple structure of fol sentences to use it as a way to
encode knowledge to be stored and used by a computer. Thinking is modeled
by manipulations involving sentences of fol. The other use is as a precise
speci¬cation language for stating axioms and proving results about arti¬cial
In computer science, fol has had an even more profound in¬‚uence. The logic and computer
very idea of an arti¬cial language that is precise yet rich enough to program
computers was inspired by this language. In addition, all extant programming
languages borrow some notions from one or another dialect of fol. Finally,
there are so-called logic programming languages, like Prolog, whose programs
are sequences of sentences in a certain dialect of fol. We will discuss the

Why learn an artificial language?
4 / Introduction

logical basis of Prolog a bit in Part III of this book.
Fol serves as the prototypical example of what is known as an arti¬cial
arti¬cial languages
language. These are languages that were designed for special purposes, and
are contrasted with so-called natural languages, languages like English and
Greek that people actually speak. The design of arti¬cial languages within the
symbolic sciences is an important activity, one that is based on the success of
fol and its descendants.
Even if you are not going to pursue logic or any of the symbolic sciences,
the study of fol can be of real bene¬t. That is why it is so widely taught. For
one thing, learning fol is an easy way to demystify a lot of formal work. It will
also teach you a great deal about your own language, and the laws of logic it
supports. First, fol, while very simple, incorporates in a clean way some of the
logic and ordinary
language important features of human languages. This helps make these features much
more transparent. Chief among these is the relationship between language
and the world. But, second, as you learn to translate English sentences into
fol you will also gain an appreciation of the great subtlety that resides in
English, subtlety that cannot be captured in fol or similar languages, at least
not yet. Finally, you will gain an awareness of the enormous ambiguity present
in almost every English sentence, ambiguity which somehow does not prevent
us from understanding each other in most situations.

Consequence and proof
Earlier, we asked what makes one claim follow from others: convention, or
something else? Giving an answer to this question for fol takes up a signif-
icant part of this book. But a short answer can be given here. Modern logic
teaches us that one claim is a logical consequence of another if there is no way
logical consequence
the latter could be true without the former also being true.
This is the notion of logical consequence implicit in all rational inquiry.
All the rational disciplines presuppose that this notion makes sense, and that
we can use it to extract consequences of what we know to be so, or what we
think might be so. It is also used in discon¬rming a theory. For if a particular
claim is a logical consequence of a theory, and we discover that the claim is
false, then we know the theory itself must be incorrect in some way or other.
If our physical theory has as a consequence that the planetary orbits are
circular when in fact they are elliptical, then there is something wrong with our
physics. If our economic theory says that in¬‚ation is a necessary consequence
of low unemployment, but today™s low employment has not caused in¬‚ation,
then our economic theory needs reassessment.
Rational inquiry, in our sense, is not limited to academic disciplines, and so

Essential instructions about homework exercises / 5

neither are the principles of logic. If your beliefs about a close friend logically
imply that he would never spread rumors behind your back, but you ¬nd that
he has, then your beliefs need revision. Logical consequence is central, not
only to the sciences, but to virtually every aspect of everyday life.
One of our major concerns in this book is to examine this notion of logical
consequence as it applies speci¬cally to the language fol. But in so doing, we
will also learn a great deal about the relation of logical consequence in natural
languages. Our main concern will be to learn how to recognize when a speci¬c
claim follows logically from others, and conversely, when it does not. This is
an extremely valuable skill, even if you never have occasion to use fol again
after taking this course. Much of our lives are spent trying to convince other
people of things, or being convinced of things by other people, whether the
issue is in¬‚ation and unemployment, the kind of car to buy, or how to spend
the evening. The ability to distinguish good reasoning from bad will help you
recognize when your own reasoning could be strengthened, or when that of
others should be rejected, despite super¬cial plausibility.
It is not always obvious when one claim is a logical consequence of oth-
ers, but powerful methods have been developed to address this problem, at
least for fol. In this book, we will explore methods of proof”how we can proof and
prove that one claim is a logical consequence of another”and also methods
for showing that a claim is not a consequence of others. In addition to the


. 2
( 107 .)