Allwein, G. Barker-Plummer, D. Barwise, Etchemendy, J., Liu, A. Languague, proof and...

(Parte 1 de 6)

In collaboration with Gerard Allwein Dave Barker-Plummer Albert Liu

77SEVEN BRIDGES PRESS NEW YORK • LONDON

Library of Congress Cataloging-in-Publication Data Barwise, Jon.

Language, proof and logic / Jon Barwise and John Etchemendy ; in collaboration with Gerard Allwein, Dave Barker-Plummer, and Albert Liu.

p. cm.

ISBN 1-889119-08-3 (pbk. : alk. paper)

I. Etchemendy, John, 1952- I. Allwein, Gerard, 1956- I. Barker-Plummer, Dave. IV. Liu, Albert, 1966- V. Title. IN PROCESS

	9-41113
	CIP

Copyright © 1999 CSLI Publications Center for the Study of Language and Information Leland Stanford Junior University

Acknowledgements

Our primary debt of gratitude goes to our three main collaborators on this project: Gerry Allwein, Dave Barker-Plummer, and Albert Liu. They have worked with us in designing the entire package, developing and implementing the software, and teaching from and reflning the text. Without their intelligence, dedication, and hard work, LPL would neither exist nor have most of its other good properties.

In addition to the flve of us, many people have contributed directly and indirectly to the creation of the package. First, over two dozen programmers have worked on predecessors of the software included with the package, both earlier versions of Tarski’s World and the program Hyperproof, some of whose code has been incorporated into Fitch. We want especially to mention Christopher Fuselier, Mark Greaves, Mike Lenz, Eric Ly, and Rick Wong, whose outstanding contributions to the earlier programs provided the foundation of the new software. Second, we thank several people who have helped with the development of the new software in essential ways: Rick Sanders, Rachel Farber, Jon Russell Barwise, Alex Lau, Brad Dolin, Thomas Robertson, Larry Lemmon, and Daniel Chai. Their contributions have improved the package in a host of ways.

Prerelease versions of LPL have been tested at several colleges and universities. In addition, other colleagues have provided excellent advice that we have tried to incorporate into the flnal package. We thank Selmer Bringsjord, Renssalaer Polytechnic Institute; Tom Burke, University of South Carolina; Robin Cooper, Gothenburg University; James Derden, Humboldt State University; Josh Dever, SUNY Albany; Avrom Faderman, University of Rochester; James Garson, University of Houston; Christopher Gauker, University of Cincinnati; Ted Hodgson, Montana State University; John Justice, Randolph- Macon Women’s College; Ralph Kennedy, Wake Forest University; Michael O’Rourke, University of Idaho; Greg Ray, University of Florida; Cindy Stern, California State University, Northridge; Richard Tieszen, San Jose State University; Saul Traiger, Occidental College; and Lyle Zynda, Indiana University at South Bend. We are particularly grateful to John Justice, Ralph Kennedy, and their students (as well as the students at Stanford and Indiana University), for their patience with early versions of the software and for their extensive comments and suggestions. We would also like to thank Stanford’s Center for the Study of Language vi / Acknowledgements and Information and Indiana University’s College of Arts and Sciences for their flnancial support of the project. Finally, we are grateful to our two publishers, Dikran Karagueuzian of CSLI Publications and Clay Glad of Seven Bridges Press, for their skill and enthusiasm about LPL, and to Lauri Kanerva for his dedication and skill in the preparation of the flnal manuscript.

Acknowledgements

Contents

Acknowledgements i

The special role of logic in rational inquiry	1
Why learn an artiflcial language?	2
Consequence and proof	4
Instructions about homework exercises (essential!)	5
To the instructor	10
Web address	15

Introduction 1

I Propositional Logic 17

1.1 Individual constants	19
1.2 Predicate symbols	20
1.3 Atomic sentences	23
1.4 General flrst-order languages	28
1.5 Function symbols (optional)	31
1.6 The flrst-order language of set theory (optional)	37
1.7 The flrst-order language of arithmetic (optional)	38
1.8 Alternative notation (optional)	40

1 Atomic Sentences 19

2.1 Valid and sound arguments	41
2.2 Methods of proof	46
2.3 Formal proofs	54
2.4 Constructing proofs in Fitch	58
2.5 Demonstrating nonconsequence	63
2.6 Alternative notation (optional)	6

2 The Logic of Atomic Sentences 41

3.1 Negation symbol: :	68
3.2 Conjunction symbol:	71
3.3 Disjunction symbol:	74
3.4 Remarks about the game	7

3 The Boolean Connectives 67 v

3.5 Ambiguity and parentheses	79
3.6 Equivalent ways of saying things	82
3.7 Translation	84
3.8 Alternative notation (optional)	89

vi / Contents

4.1 Tautologies and logical truth	94
4.2 Logical and tautological equivalence	106
4.3 Logical and tautological consequence	110
4.4 Tautological consequence in Fitch	114
4.5 Pushing negation around (optional)	117
4.6 Conjunctive and disjunctive normal forms (optional)	121

4 The Logic of Boolean Connectives 93

5.1 Valid inference steps	128
5.2 Proof by cases	131
5.3 Indirect proof: proof by contradiction	136
5.4 Arguments with inconsistent premises (optional)	140

5 Methods of Proof for Boolean Logic 127

6.1 Conjunction rules	143
6.2 Disjunction rules	148
6.3 Negation rules	154
6.4 The proper use of subproofs	163
6.5 Strategy and tactics	167
6.6 Proofs without premises (optional)	173

6 Formal Proofs and Boolean Logic 142

7.1 Material conditional symbol: !	178
7.2 Biconditional symbol: $	181
7.3 Conversational implicature	187
7.4 Truth-functional completeness (optional)	190
7.5 Alternative notation (optional)	196

8.1 Informal methods of proof	198
8.2 Formal rules of proof for ! and $	206
8.3 Soundness and completeness (optional)	214
8.4 Valid arguments: some review exercises	2

8 The Logic of Conditionals 198 Contents

Contents / vii

I Quantiflers 225

9.1 Variables and atomic wfis	228
9.2 The quantifler symbols: 8; 9	230
9.3 Wfis and sentences	231
9.4 Semantics for the quantiflers	234
9.5 The four Aristotelian forms	239
9.6 Translating complex noun phrases	243
9.7 Quantiflers and function symbols (optional)	251
9.8 Alternative notation (optional)	255

9 Introduction to Quantiflcation 227

10.1 Tautologies and quantiflcation	257
10.2 First-order validity and consequence	266
10.3 First-order equivalence and DeMorgan’s laws	275
10.4 Other quantifler equivalences (optional)	280
10.5 The axiomatic method (optional)	283

10 The Logic of Quantiflers 257

1.1 Multiple uses of a single quantifler	289
1.2 Mixed quantiflers	293
1.3 The step-by-step method of translation	298
1.4 Paraphrasing English	300
1.5 Ambiguity and context sensitivity	304
1.6 Translations using function symbols (optional)	308
1.7 Prenex form (optional)	31
1.8 Some extra translation problems	315

1 Multiple Quantiflers 289

12.1 Valid quantifler steps	319
12.2 The method of existential instantiation	322
12.3 The method of general conditional proof	323
12.4 Proofs involving mixed quantiflers	329
12.5 Axiomatizing shape (optional)	338

12 Methods of Proof for Quantiflers 319

13.1 Universal quantifler rules	342
13.2 Existential quantifler rules	347
13.3 Strategy and tactics	352
13.4 Soundness and completeness (optional)	361

13 Formal Proofs and Quantiflers 342 Contents

13.5 Some review exercises (optional)

361

viii / Contents

14.1 Numerical quantiflcation	366
14.2 Proving numerical claims	374
14.3 The, both, and neither	379
14.4 Adding other determiners to fol	383
14.5 The logic of generalized quantiflcation	389
14.6 Other expressive limitations of flrst-order logic	397

14 More about Quantiflcation (optional) 364

I Applications and Metatheory 403

15.1 Naive set theory	406
15.2 Singletons, the empty set, subsets	412
15.3 Intersection and union	415
15.4 Sets of sets	419
15.5 Modeling relations in set theory	422
15.6 Functions	427
15.7 The powerset of a set (optional)	429
15.8 Russell’s Paradox (optional)	432
15.9 Zermelo Frankel set theory zfc (optional)	433

15 First-order Set Theory 405

16.1 Inductive deflnitions and inductive proofs	443
16.2 Inductive deflnitions in set theory	451
16.3 Induction on the natural numbers	453
16.4 Axiomatizing the natural numbers (optional)	456
16.5 Proving programs correct (optional)	458

16 Mathematical Induction 442

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

17 Advanced Topics in Propositional Logic 468

18.1 First-order structures	495
18.2 Truth and satisfaction, revisited	500
18.3 Soundness for fol	509

18 Advanced Topics in FOL 495 Contents

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

Contents / ix

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 Lowenheim-Skolem Theorem	546
19.7 The Compactness Theorem	548
19.8 The Godel Incompleteness Theorem	552

19 Completeness and Incompleteness 526

Propositional rules	557
First-order rules	559
Inference Procedures (Con Rules)	561

Summary of Formal Proof Rules 557

Glossary 562 General Index 573 Exercise Files Index 585

Contents

To Sol Feferman and Pat Suppes, teachers, colleagues, and friends.

Introduction

The special role of logic in rational inquiry

What do the flelds of astronomy, economics, flnance, law, mathematics, medicine, physics, and sociology have in common? Not much in the way of subject 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 flelds, is their dependence on a certain standard of rationality. In each of these flelds, it is assumed that the participants can difierentiate between rational argumentation based on assumed principles or evidence, and wild speculation or nonsequiturs, claims that in no way follow from the assumptions. In other words, these flelds 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 inquirypeople 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 difierentiates 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 difierent 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 evenlaws 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 important 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 Brittanica 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 importantgoals 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 flrst is to help you learn a new language, the language of flrst-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 artiflcial language?

This language of flrst-order logic is very important. Like Latin, the language is not spoken, but unlike Latin, it is used every day by mathematicians, philosophers, computer scientists, linguists, and practitioners of artiflcial intelligence. Indeed, in some ways it is the universal language, the lingua franca, of the symbolic sciences. Although it is not so frequently used in other forms of rational inquiry, like medicine and flnance, 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 flrst-order logic, and fol. The last ofFOL

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 associated 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 quantiflers. Since then, there has been a process of standardization and simpliflcation, resulting in the language in its present form. Even so, there remain certain dialects of fol, difiering 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 difierent ways in difierent flelds. In mathematics, it is used in an informal way quite exten- logic and mathematics sively. The various connectives and quantiflers flnd their way into a great deal of mathematical discourse, both formal and informal, as in a classroom setting. Here you will often flnd 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:

Here, the unusual, rotated letters are taken directly from the language fol.

In philosophy, fol and enrichments of it are used in two difierent 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 artiflcial intelligence, fol is also used in two ways. Some researchers logic and artiflcial intelligencetake 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 speciflcation language for stating axioms and proving results about artiflcial agents.

In computer science, fol has had an even more profound in°uence. The logic and computer sciencevery idea of an artiflcial 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 I of this book.

Fol serves as the prototypical example of what is known as an artiflcialartiflcial 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 artiflcial 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 beneflt. 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 thelogic 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 significant 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 waylogical 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 disconflrming 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

(Parte 1 de 6)