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

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

Contents

Introduction

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

inquiry

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

1

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

FOL

Introduction

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

notions.

In arti¬cial intelligence, fol is also used in two ways. Some researchers logic and arti¬cial

intelligence

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

agents.

In computer science, fol has had an even more profound in¬‚uence. The logic and computer

science

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

Introduction

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

counterexample

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