Allwein, G. Barker-Plummer, D. Barwise, Etchemendy, J., Liu, A. Languague, proof and logic (textbook), Notas de estudo de Ciências da Educação

Baixe Allwein, G. Barker-Plummer, D. Barwise, Etchemendy, J., Liu, A. Languague, proof and logic (textbook) e outras Notas de estudo em PDF para Ciências da Educação, somente na Docsity! LANGUAGE, PROOF AND LOGIC JON BARWISE & JOHN ETCHEMENDY In collaboration with Gerard Allwein Dave Barker-Plummer Albert Liu 7 7 SEVEN 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- II. Allwein, Gerard, 1956- III. Barker-Plummer, Dave. IV. Liu, Albert, 1966- V. Title. IN PROCESS 99-41113 CIP Copyright © 1999 CSLI Publications Center for the Study of Language and Information Leland Stanford Junior University 03 02 01 00 99 5 4 3 2 1 Contents Acknowledgements iii Introduction 1 The special role of logic in rational inquiry . . . . . . . . . . . . . . 1 Why learn an artificial language? . . . . . . . . . . . . . . . . . . . . 2 Consequence and proof . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Instructions about homework exercises (essential! ) . . . . . . . . . . 5 To the instructor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Web address . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 I Propositional Logic 17 1 Atomic Sentences 19 1.1 Individual constants . . . . . . . . . . . . . . . . . . . . . . . . 19 1.2 Predicate symbols . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3 Atomic sentences . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.4 General first-order languages . . . . . . . . . . . . . . . . . . . 28 1.5 Function symbols (optional ) . . . . . . . . . . . . . . . . . . . . 31 1.6 The first-order language of set theory (optional ) . . . . . . . . 37 1.7 The first-order language of arithmetic (optional) . . . . . . . . 38 1.8 Alternative notation (optional ) . . . . . . . . . . . . . . . . . . 40 2 The Logic of Atomic Sentences 41 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 ) . . . . . . . . . . . . . . . . . . 66 3 The Boolean Connectives 67 3.1 Negation symbol: ¬ . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.2 Conjunction symbol: ∧ . . . . . . . . . . . . . . . . . . . . . . . 71 3.3 Disjunction symbol: ∨ . . . . . . . . . . . . . . . . . . . . . . . 74 3.4 Remarks about the game . . . . . . . . . . . . . . . . . . . . . 77 v vi / Contents 3.5 Ambiguity and parentheses . . . . . . . . . . . . . . . . . . . . 79 3.6 Equivalent ways of saying things . . . . . . . . . . . . . . . . . 82 3.7 Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 3.8 Alternative notation (optional ) . . . . . . . . . . . . . . . . . . 89 4 The Logic of Boolean Connectives 93 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 5 Methods of Proof for Boolean Logic 127 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 6 Formal Proofs and Boolean Logic 142 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 7 Conditionals 176 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 The Logic of Conditionals 198 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 . . . . . . . . . . . . . . 222 Contents Contents / vii II Quantifiers 225 9 Introduction to Quantification 227 9.1 Variables and atomic wffs . . . . . . . . . . . . . . . . . . . . . 228 9.2 The quantifier symbols: ∀, ∃ . . . . . . . . . . . . . . . . . . . . 230 9.3 Wffs and sentences . . . . . . . . . . . . . . . . . . . . . . . . . 231 9.4 Semantics for the quantifiers . . . . . . . . . . . . . . . . . . . . 234 9.5 The four Aristotelian forms . . . . . . . . . . . . . . . . . . . . 239 9.6 Translating complex noun phrases . . . . . . . . . . . . . . . . 243 9.7 Quantifiers and function symbols (optional ) . . . . . . . . . . . 251 9.8 Alternative notation (optional ) . . . . . . . . . . . . . . . . . . 255 10 The Logic of Quantifiers 257 10.1 Tautologies and quantification . . . . . . . . . . . . . . . . . . . 257 10.2 First-order validity and consequence . . . . . . . . . . . . . . . 266 10.3 First-order equivalence and DeMorgan’s laws . . . . . . . . . . 275 10.4 Other quantifier equivalences (optional ) . . . . . . . . . . . . . 280 10.5 The axiomatic method (optional) . . . . . . . . . . . . . . . . . 283 11 Multiple Quantifiers 289 11.1 Multiple uses of a single quantifier . . . . . . . . . . . . . . . . 289 11.2 Mixed quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . 293 11.3 The step-by-step method of translation . . . . . . . . . . . . . . 298 11.4 Paraphrasing English . . . . . . . . . . . . . . . . . . . . . . . . 300 11.5 Ambiguity and context sensitivity . . . . . . . . . . . . . . . . 304 11.6 Translations using function symbols (optional ) . . . . . . . . . 308 11.7 Prenex form (optional ) . . . . . . . . . . . . . . . . . . . . . . . 311 11.8 Some extra translation problems . . . . . . . . . . . . . . . . . 315 12 Methods of Proof for Quantifiers 319 12.1 Valid quantifier steps . . . . . . . . . . . . . . . . . . . . . . . . 319 12.2 The method of existential instantiation . . . . . . . . . . . . . . 322 12.3 The method of general conditional proof . . . . . . . . . . . . . 323 12.4 Proofs involving mixed quantifiers . . . . . . . . . . . . . . . . 329 12.5 Axiomatizing shape (optional ) . . . . . . . . . . . . . . . . . . 338 13 Formal Proofs and Quantifiers 342 13.1 Universal quantifier rules . . . . . . . . . . . . . . . . . . . . . 342 13.2 Existential quantifier rules . . . . . . . . . . . . . . . . . . . . . 347 13.3 Strategy and tactics . . . . . . . . . . . . . . . . . . . . . . . . 352 13.4 Soundness and completeness (optional ) . . . . . . . . . . . . . . 361 Contents To Sol Feferman and Pat Suppes, teachers, colleagues, and friends. Introduction The special role of logic in rational inquiry What do the fields of astronomy, economics, finance, 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 fields, is their dependence on a certain standard of rationality. In each of these fields, it is assumed that the participants can differentiate 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 fields 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 differentiates 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 different 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 traffic light means go, and a world on which water flows 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 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 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 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 first is to help you learn a new language, the language of first-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 artificial language? This language of first-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 artificial 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 finance, 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 first-order logic, and fol. The last ofFOL 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 find 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 specifically 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 specific 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 inflation 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 superficial 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 counterexampleprove 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 language fol itself, these two methods, the method of proof and the method of counterexample, form the principal subject matter of this book. Essential instructions about homework exercises This book came packaged with software that you must have to use the book. In the software package, you will find a CD-ROM containing four computer applications—Tarski’s World, Fitch, Boole and Submit—and a manual that Tarski’s World, Fitch, Boole and Submitexplains how to use them. If you do not have the complete package, you will not be able to do many of the exercises or follow many of the examples used in the book. The CD-ROM also contains an electronic copy of the book, in case you prefer reading it on your computer. When you buy the package, you also get access to the Grade Grinder, an Internet grading service that can check the Grade Grinder whether your homework is correct. About half of the exercises in the first two parts of the book will be com- pleted using the software on the CD-ROM. These exercises typically require that you create a file or files using Tarski’s World, Fitch or Boole, and then submit these solution files using the program Submit. When you do this, your solutions are not submitted directly to your instructor, but rather to our grad- Essential instructions about homework exercises 6 / Introduction ing server, the Grade Grinder, which assesses your files and sends a report to both you and your instructor. (If you are not using this book as a part of a formal class, you can have the reports sent just to you.) Exercises in the book are numbered n.m, where n is the number of the chapter and m is the number of the exercise in that chapter. Exercises whose solutions consist of one or more files that you are to submit to the Grade Grinder are indicated with an arrow (➶), so that you know the solutions are➶ vs. ✎ to be sent off into the Internet ether. Exercises whose solutions are to be turned in (on paper) to your instructor are indicated with a pencil (✎). For example, Exercises 36 and 37 in Chapter 6 might look like this: 6.36 ➶ Use Tarski’s World to build a world in which the following sentences are all true. . . . 6.37 ✎ Turn in an informal proof that the following argument is logically valid. . . . The arrow on Exercise 6.36 tells you that the world you create using Tarski’s World is to be submitted electronically, and that there is nothing else to turn in. The pencil on Exercise 6.37 tells you that your solution should be turned in directly to your instructor, on paper. Some exercises ask you to turn in something to your instructor in addition to submitting a file electronically. These are indicated with both an arrow and a pencil (➶|✎). This is also used when the exercise may require a file to be submitted, but may not, depending on the solution. For example, the next problem in Chapter 6 might ask: 6.38 ➶|✎ Is the following argument valid? If so, use Fitch to construct a formal proof of its validity. If not, explain why it is invalid and turn in your explanation to your instructor. Here, we can’t tell you definitely whether you’ll be submitting a file or turning something in without giving away an important part of the exercise, so we mark the exercise with both symbols. By the way, in giving instructions in the exercises, we will reserve the word “submit” for electronic submission, using the Submit program. We use “turnsubmitting vs. turning in exercises in” when you are to turn in the solution to your instructor. When you create files to be submitted to the Grade Grinder, it is important that you name them correctly. Sometimes we will tell you what to name the files, but more often we expect you to follow a few standard conventions. Our naming conventions are simple. If you are creating a proof using Fitch, thennaming solution files you should name the file Proof n.m, where n.m is the number of the exercise. If you are creating a world or sentence file in Tarski’s World, then you should call Introduction Essential instructions about homework exercises / 7 it either World n.m or Sentences n.m, where n.m is the number of the exercise. Finally, if you are creating a truth table using Boole, you should name it Table n.m. The key thing is to get the right exercise number in the name, since otherwise your solution will be graded incorrectly. We’ll remind you of these naming conventions a few times, but after that you’re on your own. When an exercise asks you to construct a formal proof using Fitch, you will find a file on your disk called Exercise n.m. This file contains the proof set starting proofs up, so you should open it and construct your solution in this file. This is a lot easier for you and also guarantees that the Grade Grinder will know which exercise you are solving. So make sure you always start with the packaged Exercise file when you create your solution. Exercises may also have from one to three stars (?, ??, ???), as a rough ? stars indication of the difficulty of the problem. For example, this would be an exercise that is a little more difficult than average (and whose solution you turn in to your instructor): 6.39 ✎? Design a first-order language that allows you to express the following English sentences. . . . Remember 1. The arrow (➶) means that you submit your solution electronically. 2. The pencil (✎) means that you turn in your solution to your instruc- tor. 3. The combination (➶|✎) means that your solution may be either a submitted file or something to turn in, or possibly both. 4. Stars (?, ??, ???) indicate exercises that are more difficult than average. 5. Unless otherwise instructed, name your files Proof n.m, World n.m, Sentences n.m, or Table n.m, where n.m is the number of the exercise. 6. When using Fitch to construct Proof n.m, start with the exercise file Exercise n.m, which contains the problem setup. Throughout the book, you will find a special kind of exercise that we call You try it exercises. These appear as part of the text rather than in You try it sections the exercise sections because they are particularly important. They either illustrate important points about logic that you will need to understand later or teach you some basic operations involving one of the computer programs Essential instructions about homework exercises 10 / Introduction results just to you or also to your instructor. In this case, select Just Me. When you are submitting finished homework exercises, you should select Instructor Too. Once you’ve chosen who the results should go to, click the Proceed button and your submission will be sent. (With real home- work, you can always do a trial submission to see if you got the answers right, asking that the results be sent just to you. When you are satisfied with your solutions, submit the files again, asking that the results be sent to the instructor too. But don’t forget the second submission!) I 8. In a moment, you will get a dialog box that will tell you if your submission has been successful. If so, it will give you a “receipt” message that you can save, if you like. If you do not get this receipt, then your submission has not gone through and you will have to try again. I 9. A few minutes after the Grade Grinder receives your file, you should get an email message saying that it has been received. If this were a real home- work exercise, it would also tell you if the Grade Grinder found any errors in your homework solutions. You won’t get an email report if you put in the wrong, or a misspelled, email address. If you don’t get a report, try submitting again with the right address. I 10. When you are done, choose Quit from the File menu. Congratulations on submitting your first file. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations Here’s an important thing for you to know: when you submit files to the Grade Grinder, Submit sends a copy of the files. The original files are stillwhat gets sent on the disk where you originally saved them. If you saved them on a public computer, it is best not to leave them lying around. Put them on a floppy disk that you can take with you, and delete any copies from the public computer’s hard disk. To the instructor Students, you may skip this section. It is a personal note from us, the authors, to instructors planning to use this package in their logic courses. Practical matters We use the Language, Proof and Logic package (LPL) in two very different sorts of courses. One is a first course in logic for undergraduates with no previous background in logic, philosophy, mathematics, or computer science. Introduction To the instructor / 11 This important course, sometimes disparagingly referred to as “baby logic,” is often an undergraduate’s first and only exposure to the rigorous study of reasoning. When we teach this course, we cover much of the first two parts of the book, leaving out many of the sections indicated as optional in the table of contents. Although some of the material in these two parts may seem more advanced than is usually covered in a traditional introductory course, we find that the software makes it completely accessible to even the relatively unprepared student. At the other end of the spectrum, we use LPL in an introductory graduate- level course in metatheory, designed for students who have already had some exposure to logic. In this course, we quickly move through the first two parts, thereby giving the students both a review and a common framework for use in the discussions of soundness and completeness. Using the Grade Grinder, students can progress through much of the early material at their own pace, doing only as many exercises as is needed to demonstrate competence. There are no doubt many other courses for which the package would be suitable. Though we have not had the opportunity to use it this way, it would be ideally suited for a two-term course in logic and its metatheory. Our courses are typically listed as philosophy courses, though many of the students come from other majors. Since LPL is designed to satisfy the logical needs of students from a wide variety of disciplines, it fits naturally into logic courses taught in other departments, most typically mathematics and com- puter science. Instructors in different departments may select different parts of the optional material. For example, computer science instructors may want to cover the sections on resolution in Part III, though philosophy instructors generally do not cover this material. If you have not used software in your teaching before, you may be con- cerned about how to incorporate it into your class. Again, there is a spectrum of possibilities. At one end is to conduct your class exactly the way you always do, letting the students use the software on their own to complete homework assignments. This is a perfectly fine way to use the package, and the students will still benefit significantly from the suite of software tools. We find that most students now have easy access to computers and the Internet, and so no special provisions are necessary to allow them to complete and submit the homework. At the other end are courses given in computer labs or classrooms, where the instructor is more a mentor offering help to students as they proceed at their own pace, a pace you can keep in step with periodic quizzes and exams. Here the student becomes a more active participant in the learning, but such a class requires a high computer:student ratio, at least one:three. For a class To the instructor 12 / Introduction of 30 or fewer students, this can be a very effective way to teach a beginning logic course. In between, and the style we typically use, is to give reasonably traditional presentations, but to bring a laptop to class from time to time to illustrate important material using the programs. This requires some sort of projection system, but also allows you to ask the students to do some of the computer problems in class. We encourage you to get students to operate the computer themselves in front of the class, since they thereby learn from one another, both about strategies for solving problems and constructing proofs, and about different ways to use the software. A variant of this is to schedule a weekly lab session as part of the course. The book contains an extremely wide variety of exercises, ranging from solving puzzles expressed in fol to conducting Boolean searches on the World Wide Web. There are far more exercises than you can expect your students to do in a single quarter or semester. Beware that many exercises, especially those using Tarski’s World, should be thought of as exercise sets. They may, for example, involve translating ten or twenty sentences, or transforming several sentences into conjunctive normal form. Students can find hints and solutions to selected exercises on our web site. You can download a list of these exercises from the same site. Although there are more exercises than you can reasonably assign in a semester, and so you will have to select those that best suit your course, we do urge you to assign all of the You try it exercises. These are not difficult and do not test students’ knowledge. Instead, they are designed to illustrate important logical concepts, to introduce students to important features of the programs, or both. The Grade Grinder will check any files that the students create in these sections. We should say a few words about the Grade Grinder, since it is a truly innovative feature of this package. Most important, the Grade Grinder will free you from the most tedious aspect of teaching logic, namely, grading those kinds of problems whose assessment can be mechanized. These include formal proofs, translation into fol, truth tables, and various other kinds of exercises. This will allow you to spend more time on the more rewarding parts of teaching the material. That said, it is important to emphasize two points. The first is that the Grade Grinder is not limited in the way that most computerized grading programs are. It uses sophisticated techniques, including a powerful first-order theorem prover, in assessing student answers and providing intelligent reports on those answers. Second, in designing this package, we have not fallen into the trap of tailoring the material to what can be mechanically assessed. We Introduction Web address / 15 soundness and completeness. Tarski’s World also plays a significant role in our discussion of proof, along with Fitch, by providing an environment for showing that one claim does not follow from another. With LPL, students learn not just how to prove consequences of premises, but also the equally important technique of showing that a given claim does not follow logically from its premises. To do this, they learn how to give counterexamples, which are really proofs of nonconsequence. These will often be given using Tarski’s World. The approach we take in LPL is also unusual in two other respects. One is our emphasis on languages in which all the basic symbols are assumed to be meaningful. This is in contrast to the so-called “uninterpreted languages” (surely an oxymoron) so often found in logic textbooks. Another is the inclu- sion of various topics not usually covered in introductory logic books. These include the theory of conversational implicature, material on generalized quan- tifiers, and most of the material in Part III. We believe that even if these topics are not covered, their presence in the book illustrates to the student the rich- ness and open-endedness of the discipline of logic. Web address In addition to the book, software, and grading service, additional material can be found on the Web at the following address: http://www-csli.stanford.edu/LPL/ Note the dash (-) rather than the more common period (.) after “www” in this address. Web address 16 Part I Propositional Logic 17 20 / Atomic Sentences language takes the letters a through f plus n1, n2, . . . as its names. The main difference between names in English and the individual constants of fol is that we require the latter to refer to exactly one object. Obviously,names in fol the name Max in English can be used to refer to many different people, and might even be used twice in a single sentence to refer to two different people. Such wayward behavior is frowned upon in fol. There are also names in English that do not refer to any actually existing object. For example Pegasus, Zeus, and Santa Claus are perfectly fine names in English; they just fail to refer to anything or anybody. We don’t allow such names in fol.1 What we do allow, though, is for one object to have more than one name; thus the individual constants matthew and max might both refer to the same individual. We also allow for nameless objects, objects that have no name at all. Remember In fol, ◦ Every individual constant must name an (actually existing) object. ◦ No individual constant can name more than one object. ◦ An object can have more than one name, or no name at all. Section 1.2 Predicate symbols Predicate symbols are symbols used to express some property of objects or some relation between objects. Because of this, they are also sometimes calledpredicate or relation symbols relation symbols. As in English, predicates are expressions that, when com- bined with names, form atomic sentences. But they don’t correspond exactly to the predicates of English grammar. Consider the English sentence Max likes Claire. In English grammar, this is analyzed as a subject-predicate sentence. It consists of the subject Max followed by the predicate likes Claire. In fol, by contrast, we view this as a claim involving two “logical subjects,” the names Max and Claire, and alogical subjects 1There is, however, a variant of first-order logic called free logic in which this assumption is relaxed. In free logic, there can be individual constants without referents. This yields a language more appropriate for mythology and fiction. Chapter 1 Predicate symbols / 21 predicate, likes, that expresses a relation between the referents of the names. Thus, atomic sentences of fol often have two or more logical subjects, and the predicate is, so to speak, whatever is left. The logical subjects are called the “arguments” of the predicate. In this case, the predicate is said to be binary, arguments of a predicatesince it takes two arguments. In English, some predicates have optional arguments. Thus you can say Claire gave, Claire gave Scruffy, or Claire gave Scruffy to Max. Here the predicate gave is taking one, two, and three arguments, respectively. But in fol, each predicate has a fixed number of arguments, a fixed arity as it is arity of a predicate called. This is a number that tells you how many individual constants the predicate symbol needs in order to form a sentence. The term “arity” comes from the fact that predicates taking one argument are called unary, those taking two are binary, those taking three are ternary, and so forth. If the arity of a predicate symbol Pred is 1, then Pred will be used to express some property of objects, and so will require exactly one argument (a name) to make a claim. For example, we might use the unary predicate symbol Home to express the property of being at home. We could then combine this with the name max to get the expression Home(max), which expresses the claim that Max is at home. If the arity of Pred is 2, then Pred will be used to represent a relation between two objects. Thus, we might use the expression Taller(claire, max) to express a claim about Max and Claire, the claim that Claire is taller than Max. In fol, we can have predicate symbols of any arity. However, in the blocks language used in Tarski’s World we restrict ourselves to predicates with arities 1, 2, and 3. Here we list the predicates of that language, this time with their arity. Arity 1: Cube, Tet, Dodec, Small, Medium, Large Arity 2: Smaller, Larger, LeftOf, RightOf, BackOf, FrontOf, SameSize, Same- Shape, SameRow, SameCol, Adjoins, = Arity 3: Between Tarski’s World assigns each of these predicates a fixed interpretation, one reasonably consistent with the corresponding English verb phrase. For exam- ple, Cube corresponds to is a cube, BackOf corresponds to is in back of, and so forth. You can get the hang of them by working through the first set of exercises given below. To help you learn exactly what the predicates mean, Table 1.1 lists atomic sentences that use these predicates, together with their interpretations. In English, predicates are sometimes vague. It is often unclear whether vagueness Section 1.2 22 / Atomic Sentences Table 1.1: Blocks language predicates. Atomic Sentence Interpretation Tet(a) a is a tetrahedron Cube(a) a is a cube Dodec(a) a is a dodecahedron Small(a) a is small Medium(a) a is medium Large(a) a is large SameSize(a, b) a is the same size as b SameShape(a,b) a is the same shape as b Larger(a, b) a is larger than b Smaller(a,b) a is smaller than b SameCol(a, b) a is in the same column as b SameRow(a, b) a is in the same row as b Adjoins(a, b) a and b are located on adjacent (but not diagonally) squares LeftOf(a, b) a is located nearer to the left edge of the grid than b RightOf(a, b) a is located nearer to the right edge of the grid than b FrontOf(a, b) a is located nearer to the front of the grid than b BackOf(a, b) a is located nearer to the back of the grid than b Between(a, b, c) a, b and c are in the same row, col- umn, or diagonal, and a is between b and c an individual has the property in question or not. For example, Claire, who is sixteen, is young. She will not be young when she is 96. But there is no determinate age at which a person stops being young: it is a gradual sort of thing. Fol, however, assumes that every predicate is interpreted by a deter- minate property or relation. By a determinate property, we mean a propertydeterminate property for which, given any object, there is a definite fact of the matter whether or not the object has the property. This is one of the reasons we say that the blocks language predicates are Chapter 1 Atomic sentences / 25 to modify the world to make some of them true. As you do this, you will notice that large blocks cannot adjoin other blocks. J6. In doing this exercise, you will no doubt notice that Between does not mean exactly what the English between means. This is due to the necessity of interpreting Between as a determinate predicate. For simplicity, we insist that in order for b to be between c and d, all three must be in the same row, column, or diagonal. J7. When you are finished, close the files, but do not save the changes you have made to them. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations Remember In fol, ◦ Atomic sentences are formed by putting a predicate of arity n in front of n names (enclosed in parentheses and separated by commas). ◦ Atomic sentences are built from the identity predicate, =, using infix notation: the arguments are placed on either side of the predicate. ◦ The order of the names is crucial in forming atomic sentences. Exercises You will eventually want to read the entire chapter of the user’s manual on how to use Tarski’s World. To do the following problems, you will need to read at least the first four sections. Also, if you don’t remember how to name and submit your solution files, you should review the section on essential instructions in the Introduction, starting on page 5. 1.1 If you skipped the You try it section, go back and do it now. This is an easy but crucial exercise that will familiarize you with the atomic sentences of the blocks language. There is nothing you need to turn in or submit, but don’t skip the exercise! 1.2 ➶ (Copying some atomic sentences) This exercise will give you some practice with the Tarski’s World keyboard window, as well as with the syntax of atomic sentences. The following are all atomic sentences of our language. Start a new sentence file and copy them into it. Have Tarski’s World check each formula after you write it to see that it is a sentence. If you make a mistake, edit it before going on. Make sure you use the Add Sentence command between sentences, Section 1.3 26 / Atomic Sentences not the return key. If you’ve done this correctly, the sentences in your list will be numbered and separated by horizontal lines. 1. Tet(a) 2. Medium(a) 3. Dodec(b) 4. Cube(c) 5. FrontOf(a,b) 6. Between(a, b, c) 7. a = d 8. Larger(a, b) 9. Smaller(a, c) 10. LeftOf(b, c) Remember, you should save these sentences in a file named Sentences 1.2. When you’ve finished your first assignment, submit all of your solution files using the Submit program. 1.3 ➶ (Building a world) Build a world in which all the sentences in Exercise 1.2 are simultaneously true. Remember to name and submit your world file as World 1.3. 1.4 ➶ (Translating atomic sentences) Here are some simple sentences of English. Start a new sentence file and translate them into fol. 1. a is a cube. 2. b is smaller than a. 3. c is between a and d. 4. d is large. 5. e is larger than a. 6. b is a tetrahedron. 7. e is a dodecahedron. 8. e is right of b. 9. a is smaller than e. 10. d is in back of a. 11. b is in the same row as d. 12. b is the same size as c. After you’ve translated the sentences, build a world in which all of your translations are true. Submit your sentence and world files as Sentences 1.4 and World 1.4. 1.5 ➶ (Naming objects) Open Lestrade’s Sentences and Lestrade’s World. You will notice that none of the objects in this world has a name. Your task is to assign the objects names in such a way that all the sentences in the list come out true. Remember to save your solution in a file named World 1.5. Be sure to use Save World As. . . , not Save World. Chapter 1 Atomic sentences / 27 1.6 ➶? (Naming objects, continued) Not all of the choices in Exercise 1.5 were forced on you. That is, you could have assigned the names differently and still had the sentences come out true. Change the assignment of as many names as possible while still making all the sentences true, and submit the changed world as World 1.6. In order for us to compare your files, you must submit both World 1.5 and World 1.6 at the same time. 1.7 ➶|✎ (Context sensitivity of predicates) We have stressed the fact that fol assumes that every predicate is interpreted by a determinate relation, whereas this is not the case in natural languages like English. Indeed, even when things seem quite determinate, there is often some form of context sensitivity. In fact, we have built some of this into Tarski’s World. Consider, for example, the difference between the predicates Larger and BackOf. Whether or not cube a is larger than cube b is a determinate matter, and also one that does not vary depending on your perspective on the world. Whether or not a is back of b is also determinate, but in this case it does depend on your perspective. If you rotate the world by 90◦, the answer might change. Open Austin’s Sentences and Wittgenstein’s World. Evaluate the sentences in this file and tabulate the resulting truth values in a table like the one below. We’ve already filled in the first column, showing the values in the original world. Rotate the world 90◦ clockwise and evaluate the sentences again, adding the results to the table. Repeat until the world has come full circle. Original Rotated 90◦ Rotated 180◦ Rotated 270◦ 1. false 2. false 3. true 4. false 5. true 6. false You should be able to think of an atomic sentence in the blocks language that would produce a row across the table with the following pattern: true false true false Add a seventh sentence to Austin’s Sentences that would display the above pattern. Are there any atomic sentences in the language that would produce a row with this pattern? false true false false If so, add such a sentence as sentence eight in Austin’s Sentences. If not, leave sentence eight blank. Are there any atomic sentences that would produce a row in the table containing exactly three true’s? If so, add such a sentence as number nine. If not, leave sentence nine blank. Submit your modified sentence file as Sentences 1.7. Turn in your completed table to your instructor. Section 1.3 30 / Atomic Sentences Table 1.2: Names and predicates for a language. English fol Comment Names: Max max Claire claire Folly folly The name of a certain dog. Carl carl The name of another dog. Scruffy scruffy The name of a certain cat. Pris pris The name of another cat. 2 pm, Jan 2, 2001 2:00 The name of a time. 2:01 pm, Jan 2, 2001 2:01 One minute later. ... ... Similarly for other times. Predicates: x is a pet Pet(x) x is a person Person(x) x is a student Student(x) t is earlier than t′ t < t′ Earlier-than for times. x was hungry at time t Hungry(x, t) x was angry at time t Angry(x, t) x owned y at time t Owned(x, y, t) x gave y to z at t Gave(x, y, z, t) x fed y at time t Fed(x, y, t) 1.9 ➶ We will be giving a number of problems that use the symbols explained in Table 1.2. Start a new sentence file in Tarski’s World and translate the following into fol, using the names and predicates listed in the table. (You will have to type the names and predicates in by hand. Make sure you type them exactly as they appear in the table; for example, use 2:00, not 2:00 pm or 2 pm.) All references to times are assumed to be to times on January 2, 2001. 1. Claire owned Folly at 2 pm. 2. Claire gave Pris to Max at 2:05 pm. 3. Max is a student. 4. Claire fed Carl at 2 pm. 5. Folly belonged to Max at 3:05 pm. 6. 2:00 pm is earlier than 2:05 pm. Name and submit your file in the usual way. Chapter 1 Function symbols / 31 1.10 ✎ Translate the following into natural sounding, colloquial English, consulting Table 1.2. 1. Owned(max, scruffy,2:00) 2. Fed(max, scruffy, 2:30) 3. Gave(max, scruffy, claire, 3:00) 4. 2:00 < 2:00 1.11 ✎? For each sentence in the following list, suggest a translation into an atomic sentence of fol. In addition to giving the translation, explain what kinds of objects your names refer to and the intended meaning of the predicate you use. 1. Max shook hands with Claire. 2. Max shook hands with Claire yesterday. 3. AIDS is less contagious than influenza. 4. Spain is between France and Portugal in size. 5. Misery loves company. Section 1.5 Function symbols Some first-order languages have, in addition to names and predicates, other expressions that can appear in atomic sentences. These expressions are called function symbols. Function symbols allow us to form name-like terms from function symbols names and other name-like terms. They allow us to express, using atomic sentences, complex claims that could not be perspicuously expressed using just names and predicates. Some English examples will help clarify this. English has many sorts of noun phrases, expressions that can be combined with a verb phrase to get a sentence. Besides names like Max and Claire, other noun phrases include expressions like Max’s father, Claire’s mother, Every girl who knows Max, No boy who knows Claire, Someone and so forth. Each of these combines with a singular verb phrase such as likes unbuttered popcorn to make a sentence. But notice that the sentences that result have very different logical properties. For example, Claire’s mother likes unbuttered popcorn implies that someone likes unbuttered popcorn, while No boy who knows Claire likes unbuttered popcorn does not. Since these noun phrases have such different logical properties, they are terms treated differently in fol. Those that intuitively refer to an individual are Section 1.5 32 / Atomic Sentences called “terms,” and behave like the individual constants we have already dis- cussed. In fact, individual constants are the simplest terms, and more complex terms are built from them using function symbols. Noun phrases like No boy who knows Claire are handled with very different devices, known as quanti- fiers, which we will discuss later. The fol analog of the noun phrase Max’s father is the term father(max). It is formed by putting a function symbol, father, in front of the individual constant max. The result is a complex term that we use to refer to the fathercomplex terms of the person referred to by the name max. Similarly, we can put the function symbol mother together with the name claire and get the term mother(claire), which functions pretty much like the English term Claire’s mother. We can repeat this construction as many times as we like, forming more and more complex terms: father(father(max)) mother(father(claire)) mother(mother(mother(claire))) The first of these refers to Max’s paternal grandfather, the second to Claire’s paternal grandmother, and so forth. These function symbols are called unary function symbols, because, like unary predicates, they take one argument. The resulting terms function just like names, and can be used in forming atomic sentences. For instance, the fol sentence Taller(father(max),max) says that Max’s father is taller than Max. Thus, in a language containing function symbols, the definition of atomic sentence needs to be modified to allow complex terms to appear in the argument positions in addition to names. Students often confuse function symbols with predicates, because bothfunction symbols vs. predicates take terms as arguments. But there is a big difference. When you combine a unary function symbol with a term you do not get a sentence, but another term: something that refers (or should refer) to an object of some sort. This is why function symbols can be reapplied over and over again. As we have seen, the following makes perfectly good sense: father(father(max)) This, on the other hand, is total nonsense: Dodec(Dodec(a)) To help prevent this confusion, we will always capitalize predicates of fol and leave function symbols and names in lower case. Chapter 1 Function symbols / 35 6. SameRow(rm(c), c) 7. bm(lm(c)) = lm(bm(c)) 8. SameShape(lm(b),bm(rm(e))) 9. d = lm(fm(rm(bm(d)))) 10. Between(b, lm(b), rm(b)) Fill in the following table with true’s and false’s according to whether the indicated sentence is true or false in the indicated world. Since Tarski’s World does not understand the function symbols, you will not be able to check your answers. We have filled in a few of the entries for you. Turn in the completed table to your instructor. Leibniz’s Bolzano’s Boole’s Wittgenstein’s 1. true 2. 3. 4. 5. false 6. true 7. 8. false 9. 10. 1.14 ➶ As you probably noticed in doing Exercise 1.13, three of the sentences came out true in all four worlds. It turns out that one of these three cannot be falsified in any world, because of the meanings of the predicates and function symbols it contains. Your goal in this problem is to build a world in which all of the other sentences in Exercise 1.13 come out false. When you have found such a world, submit it as World 1.14. 1.15 ✎ Suppose we have two first-order languages for talking about fathers. The first, which we’ll call the functional language, contains the names claire, melanie, and jon, the function symbol father, and the predicates = and Taller. The second language, which we will call the relational language, has the same names, no function symbols, and the binary predicates =, Taller, and FatherOf, where FatherOf(c, b) means that c is the father of b. Translate the following atomic sentences from the relational language into the functional language. Be careful. Some atomic sentences, such as claire = claire, are in both languages! Such a sentence counts as a translation of itself. 1. FatherOf(jon, claire) 2. FatherOf(jon, melanie) Section 1.5 36 / Atomic Sentences 3. Taller(claire, melanie) Which of the following atomic sentences of the functional language can be translated into atomic sentences of the relational language? Translate those that can be and explain the problem with those that can’t. 4. father(melanie) = jon 5. father(melanie) = father(claire) 6. Taller(father(claire), father(jon)) When we add connectives and quantifiers to the language, we will be able to translate freely back and forth between the functional and relational languages. 1.16 ✎ Let’s suppose that everyone has a favorite movie star. Given this assumption, make up a first- order language for talking about people and their favorite movie stars. Use a function symbol that allows you to refer to an individual’s favorite actor, plus a relation symbol that allows you to say that one person is a better actor than another. Explain the interpretation of your function and relation symbols, and then use your language to express the following claims: 1. Harrison is Nancy’s favorite actor. 2. Nancy’s favorite actor is better than Sean. 3. Nancy’s favorite actor is better than Max’s. 4. Claire’s favorite actor’s favorite actor is Brad. 5. Sean is his own favorite actor. 1.17 ✎? Make up a first-order language for talking about people and their relative heights. Instead of using relation symbols like Taller, however, use a function symbol that allows you to refer to people’s heights, plus the relation symbols = and <. Explain the interpretation of your function symbol, and then use your language to express the following two claims: 1. George is taller than Sam. 2. Sam and Mary are the same height. Do you see any problem with this function symbol? If so, explain the problem. [Hint: What happens if you apply the function symbol twice?] 1.18 ✎? For each sentence in the following list, suggest a translation into an atomic sentence of fol. In addition to giving the translation, explain what kinds of objects your names refer to and the intended meaning of the predicates and function symbols you use. 1. Indiana’s capital is larger than California’s. 2. Hitler’s mistress died in 1945. 3. Max shook Claire’s father’s hand. 4. Max is his father’s son. 5. John and Nancy’s eldest child is younger than Jon and Mary Ellen’s. Chapter 1 The first-order language of set theory / 37 Section 1.6 The first-order language of set theory Fol was initially developed for use in mathematics, and consequently the most familiar first-order languages are those associated with various branches of mathematics. One of the most common of these is the language of set theory. This language has only two predicates, both binary. The first is the predicates of set theory identity symbol, =, which we have already encountered, and the second is the symbol ∈, for set membership. It is standard to use infix notation for both of these predicates. Thus, in set theory, atomic sentences are always formed by placing individual constants on either side of one of the two predicates. This allows us to make identity claims, of the form a = b, and membership claims, of the form a ∈ b (where a and b are individual constants). A sentence of the form a ∈ b is true if and only if the thing named by b is membership (∈) a set, and the thing named by a is a member of that set. For example, suppose a names the number 2 and b names the set {2, 4, 6}. Then the following table tells us which membership claims made up using these names are true and which are false.2 a ∈ a false a ∈ b true b ∈ a false b ∈ b false Notice that there is one striking difference between the atomic sentences of set theory and the atomic sentences of the blocks language. In the blocks language, you can have a sentence, like LeftOf(a,b), that is true in a world, but which can be made false simply by moving one of the objects. Moving an object does not change the way the name works, but it can turn a true sentence into a false one, just as the sentence Claire is sitting down can go from true to false in virtue of Claire’s standing up. In set theory, we won’t find this sort of thing happening. Here, the analog of a world is just a domain of objects and sets. For example, our domain might consist of all natural numbers, sets of natural numbers, sets of sets of natural numbers, and so forth. The difference between these “worlds” and those of Tarski’s World is that the truth or falsity of the atomic sentences is determined entirely once the reference of the names is fixed. There is nothing that corresponds to moving the blocks around. Thus if the universe contains 2For the purposes of this discussion we are assuming that numbers are not sets, and that sets can contain either numbers or other sets as members. Section 1.6 40 / Atomic Sentences Section 1.8 Alternative notation As we said before, fol is like a family of languages. But, as if that were not enough diversity, even the very same first-order language comes in a variety of dialects. Indeed, almost no two logic books use exactly the same notational conventions in writing first-order sentences. For this reason, it is important to have some familiarity with the different dialects—the different notational conventions—and to be able to translate smoothly between them. At the end of most chapters, we discuss common notational differences that you are likely to encounter. Some notational differences, though not many, occur even at the level of atomic sentences. For example, some authors insist on putting parentheses around atomic sentences whose binary predicates are in infix position. So (a = b) is used rather than a = b. By contrast, some authors omit parentheses surrounding the argument positions (and the commas between them) when the predicate is in prefix position. These authors use Rab instead of R(a,b). We have opted for the latter simply because we use predicates made up of several letters, and the parentheses make it clear where the predicate ends and the arguments begin: Cubed is not nearly as perspicuous as Cube(d). What is important in these choices is that sentences should be unambigu- ous and easy to read. Typically, the first aim requires parentheses to be used in one way or another, while the second suggests using no more than is necessary. Chapter 1 Chapter 2 The Logic of Atomic Sentences A major concern in logic is the concept of logical consequence: When does one sentence, statement, or claim follow logically from others? In fact, one of the main motivations in the design of fol was to make logical consequence as perspicuous as possible. It was thought that by avoiding the ambiguities and complexities of ordinary language, we would be able to recognize the consequences of our claims more easily. This is, to a certain extent, true; but it is also true that we should be able to recognize the consequences of our claims whether or not they are expressed in fol. In this chapter, we will explain what we mean by “logical consequence,” or equivalently, what we mean when we say that an argument is “logically valid.” This is a fairly simple concept to understand, but it can also be devilishly dif- ficult to apply in specific cases. Indeed, in mathematics there are many, many examples where we do not know whether a given claim is a consequence of other known truths. Mathematicians may work for years or decades trying to answer such questions. After explaining the notion of consequence, we will describe the principal techniques for showing that a claim is or is not a con- sequence of other claims, and begin presenting what is known as a formal system of deduction, a system that allows us to show that a sentence of fol is a consequence of others. We will continue developing this system as we learn more about fol in later chapters. Section 2.1 Valid and sound arguments Just what do we mean by logical consequence? Or rather, since this phrase is sometimes used in quite different contexts, what does a logician mean by logical consequence? A few examples will help. First, let’s say that an argument is any series arguments, premises, and conclusionsof statements in which one (called the conclusion) is meant to follow from, or be supported by, the others (called the premises). Don’t think of two people arguing back and forth, but of one person trying to convince another of some conclusion on the basis of mutually accepted premises. Arguments in our sense may appear as part of the more disagreeable sort of “arguments”— the kind parents have with their children—but our arguments also appear 41 42 / The Logic of Atomic Sentences in newspaper editorials, in scholarly books, and in all forms of scientific and rational discourse. Name calling doesn’t count. There are many devices in ordinary language for indicating premises and conclusions of arguments. Words like hence, thus, so, and consequently areidentifying premises and conclusions used to indicate that what follows is the conclusion of an argument. The words because, since, after all, and the like are generally used to indicate premises. Here are a couple of examples of arguments: All men are mortal. Socrates is a man. So, Socrates is mortal. Lucretius is a man. After all, Lucretius is mortal and all men are mortal. One difference between these two arguments is the placement of the con- clusion. In the first argument, the conclusion comes at the end, while in the second, it comes at the start. This is indicated by the words so and after all, respectively. A more important difference is that the first argument is good, while the second is bad. We will say that the first argument is logically valid, or that its conclusion is a logical consequence of its premises. The reason welogical consequence say this is that it is impossible for this conclusion to be false if the premises are true. In contrast, our second conclusion might be false (suppose Lucretius is my pet goldfish), even though the premises are true (goldfish are notoriously mortal). The second conclusion is not a logical consequence of its premises. Roughly speaking, an argument is logically valid if and only if the conclu-logically valid arguments sion must be true on the assumption that the premises are true. Notice that this does not mean that an argument’s premises have to be true in order for it to be valid. When we give arguments, we naturally intend the premises to be true, but sometimes we’re wrong about that. We’ll say more about this possi- bility in a minute. In the meantime, note that our first example above would be a valid argument even if it turned out that we were mistaken about one of the premises, say if Socrates turned out to be a robot rather than a man. It would still be impossible for the premises to be true and the conclusion false. In that eventuality, we would still say that the argument was logically valid, but since it had a false premise, we would not be guaranteed that the conclusion was true. It would be a valid argument with a false premise. Here is another example of a valid argument, this time one expressed in the blocks language. Suppose we are told that Cube(c) and that c = b. Then it certainly follows that Cube(b). Why? Because there is no possible way for the premises to be true—for c to be a cube and for c to be the very same object as b—without the conclusion being true as well. Note that we can recognize that the last statement is a consequence of the first two without knowing that Chapter 2 Valid and sound arguments / 45 3. Open Wittgenstein’s World and fill in the third column of the table. 4. For each argument that you have marked invalid in the table, construct a world in which the argument’s premises are all true but the conclusion is false. Submit the world as World 2.1.x, where x is the number of the argument. (If you have trouble doing this, you may want to rethink your assessment of the argument’s validity.) Turn in your completed table to your instructor. This problem makes a very important point, one that students of logic sometimes forget. The point is that the validity of an argument depends only on the argument, not on facts about the specific world the statements are about. The soundness of an argument, on the other hand, depends on both the argument and the world. 2.2 ✎ (Classifying arguments) For each of the arguments below, identify the premises and conclusion by putting the argument into Fitch format. Then say whether the argument is valid. For the first five arguments, also give your opinion about whether they are sound. (Remember that only valid arguments can be sound.) If your assessment of an argument depends on particular interpretations of the predicates, explain these dependencies. 1. Anyone who wins an academy award is famous. Meryl Streep won an academy award. Hence, Meryl Streep is famous. 2. Harrison Ford is not famous. After all, actors who win academy awards are famous, and he has never won one. 3. The right to bear arms is the most important freedom. Charlton Heston said so, and he’s never wrong. 4. Al Gore must be dishonest. After all, he’s a politician and hardly any politicians are honest. 5. Mark Twain lived in Hannibal, Missouri, since Sam Clemens was born there, and Mark Twain is Sam Clemens. 6. No one under 21 bought beer here last night, officer. Geez, we were closed, so no one bought anything last night. 7. Claire must live on the same street as Laura, since she lives on the same street as Max and he and Laura live on the same street. 2.3 ✎ For each of the arguments below, identify the premises and conclusion by putting the argument into Fitch format, and state whether the argument is valid. If your assessment of an argument depends on particular interpretations of the predicates, explain these dependencies. 1. Many of the students in the film class attend film screenings. Consequently, there must be many students in the film class. 2. There are few students in the film class, but many of them attend the film screenings. So there are many students in the film class. Section 2.1 46 / The Logic of Atomic Sentences 3. There are many students in the film class. After all, many students attend film screen- ings and only students in the film class attend screenings. 4. There are thirty students in my logic class. Some of the students turned in their homework on time. Most of the students went to the all-night party. So some student who went to the party managed to turn in the homework on time. 5. There are thirty students in my logic class. Some student who went to the all-night party must have turned in the homework on time. Some of the students turned in their homework on time, and they all went to the party. 6. There are thirty students in my logic class. Most of the students turned in their home- work on time. Most of the students went to the all-night party. Thus, some student who went to the party turned in the homework on time. 2.4 ✎ (Validity and truth) Can a valid argument have false premises and a false conclusion? False premises and a true conclusion? True premises and a false conclusion? True premises and a true conclusion? If you answer yes to any of these, give an example of such an argument. If your answer is no, explain why. Section 2.2 Methods of proof Our description of the logical consequence relation is fine, as far as it goes. But it doesn’t give us everything we would like. In particular, it does not tell us how to show that a given conclusion S follows, or does not follow, from some premises P, Q, R, . . . . In the examples we have looked at, this may not seem very problematic, since the answers are fairly obvious. But when we are dealing with more complicated sentences or more subtle reasoning, things are sometimes far from simple. In this course you will learn the fundamental methods of showing when claims follow from other claims and when they do not. The main technique for doing the latter, for showing that a given conclusion does not follow from some premises, is to find a possible circumstance in which the premises are true but the conclusion false. In fact we have already used this method to show that the argument about Lucretius was invalid. We will use the method repeatedly, and introduce more precise versions of it as we go on. What methods are available to us for showing that a given claim is a logical consequence of some premises? Here, the key notion is that of a proof. A proof is a step-by-step demonstration that a conclusion (say S) followsproof from some premises (say P,Q,R). The way a proof works is by establishing a series of intermediate conclusions, each of which is an obvious consequence of Chapter 2 Methods of proof / 47 the original premises and the intermediate conclusions previously established. The proof ends when we finally establish S as an obvious consequence of the original premises and the intermediate conclusions. For example, from P,Q, R it might be obvious that S1 follows. And from all of these, including S1, it might be obvious that S2 follows. Finally, from all these together we might be able to draw our desired conclusion S. If our individual steps are correct, then the proof shows that S is indeed a consequence of P, Q, R. After all, if the premises are all true, then our intermediate conclusions must be true as well. And in that case, our final conclusion must be true, too. Consider a simple, concrete example. Suppose we want to show that Socrates sometimes worries about dying is a logical consequence of the four premises Socrates is a man, All men are mortal, No mortal lives forever, and Everyone who will eventually die sometimes worries about it. A proof of this conclusion might pass through the following intermediate steps. First we note that from the first two premises it follows that Socrates is mortal. From this intermedi- ate conclusion and the third premise (that no mortal lives forever), it follows that Socrates will eventually die. But this, along with the fourth premise, gives us the desired conclusion, that Socrates sometimes worries about dying. By the way, when we say that S is a logical consequence of premises P,Q, . . . , we do not insist that each of the premises really play an essen- tial role. So, for example, if S is a logical consequence of P then it is also a logical consequence of P and Q. This follows immediately from the definition of logical consequence. But it has a corollary for our notion of proof: We do not insist that each of the premises in a proof actually be used in the proof. A proof that S follows from premises P1, . . . , Pn may be quite long and complicated. But each step in the proof is supposed to provide absolutely incontrovertible evidence that the intermediate conclusion follows from things already established. Here, the logician’s standards of rigor are extreme. It is demand for rigor not enough to show that each step in a purported proof almost certainly follows from the ones that come before. That may be good enough for getting around in our daily life, but it is not good enough if our aim is to demonstrate that S must be true provided P1, . . . , Pn are all true. There is a practical reason for this demand for rigor. In ordinary life, we frequently reason in a step-by-step fashion, without requiring absolute certainty at each step. For most purposes, this is fine, since our everyday “proofs” generally traverse only a small number of intermediate conclusions. But in many types of reasoning, this is not the case. Think of what you did in high school geometry. First you started with a small number of axioms that stated the basic premises of Euclidean geometry. You then began to prove conclusions, called theorems, from these axioms. As Section 2.2 50 / The Logic of Atomic Sentences nation, abbreviated = Elim. The reason for this name is that an application of this rule “eliminates” a use of the identity symbol when we move from the premises of the argument to its conclusion. We will have another rule that introduces the identity symbol. The principle of identity elimination is used repeatedly in mathematics. For example, the following derivation uses the principle in conjunction with the well-known algebraic identity x2 − 1 = (x − 1)(x + 1): x2 > x2 − 1 so x2 > (x − 1)(x + 1) We are all familiar with reasoning that uses such substitutions repeatedly. Another principle, so simple that one often overlooks it, is the so-called reflexivity of identity. The formal rule corresponding to it is called Identityreflexivity of identity or identity elimination Introduction, or = Intro, since it allows us to introduce identity statements into proofs. It tells us that any sentence of the form a = a can be validly inferred from whatever premises are at hand, or from no premises at all. This is because of the assumption made in fol that names always refer to one and only one object. This is not true about English, as we have noted before. But it is in fol, which means that in a proof you can always take any name a that is in use and assert a = a, if it suits your purpose for some reason. (As a matter of fact, it is rarely of much use.) Gertrude Stein was surely referring to this principle when she observed “A rose is a rose is a rose.” Another principle, a bit more useful, is that of the symmetry of identity. Itsymmetry of identity allows us to conclude b = a from a = b. Actually, if we wanted, we could derive this as a consequence of our first two principles, by means of the following proof. Proof: Suppose that a = b. We know that a = a, by the reflexivity of identity. Now substitute the name b for the first use of the name a in a = a, using the indiscernibility of identicals. We come up with b = a, as desired. The previous paragraph is another example of an informal proof. In an informal proof, we often begin by stating the premises or assumptions of the proof, and then explain in a step-by-step fashion how we can get from these assumptions to the desired conclusion. There are no strict rules about how detailed the explanation needs to be. This depends on the sophistication of the intended audience for the proof. But each step must be phrased in clear and unambiguous English, and the validity of the step must be apparent. In the next section, we will see how to formalize the above proof. Chapter 2 Methods of proof / 51 A third principle about identity that bears noting is its so-called transitivity. transitivity of identity If a = b and b = c are both true, then so is a = c. This is so obvious that there is no particular need to prove it, but it can be proved using the indiscernibility of identicals. (See Exercise 2.5.) If you are using a language that contains function symbols (introduced in the optional Section 1.5), the identity principles we’ve discussed also hold for complex terms built up using function symbols. For example, if you know that Happy(john) and john = father(max), you can use identity elimination to conclude Happy(father(max)), even though father(max) is a complex term, not a name. In fact, the example where we substituted (x − 1)(x + 1) for x2 − 1 also applied the indiscernibility of identicals to complex terms. Remember There are four important principles that hold of the identity relation: 1. = Elim: If b = c, then whatever holds of b holds of c. This is also known as the indiscernibility of identicals. 2. = Intro: Sentences of the form b = b are always true (in fol). This is also known as the reflexivity of identity. 3. Symmetry of Identity: If b = c, then c = b. 4. Transitivity of Identity: If a = b and b = c, then a = c. The latter two principles follow from the first two. Proofs involving other predicates and relations Sometimes there will be logical dependencies among the predicate symbols in a first-order language, dependencies similar to those just discussed involving the identity symbol. This is the case, for example, in the blocks language. When this is so, proofs may need to exploit such relationships. For example, the sentence Larger(a, c) is a consequence of Larger(a,b) and Larger(b, c). This is because the larger-than relation, like the identity relation, is transitive. It is other transitive relationsbecause of this that any world where the latter two sentences are true will also be one in which the first is true. Similar examples are given in the problems. Another example of this sort that is used frequently in mathematics in- volves the transitivity of the less-than relation. You frequently encounter Section 2.2 52 / The Logic of Atomic Sentences proofs written in the following form: k1 < k2 k2 < k3 k3 < k4 so k1 < k4 This proof contains two implicit uses of the transitivity of <. There is no way to catalog all the legitimate inferences involving predicate and relation symbols in all the languages we might have occasion to deal with. But the example of identity gives us a few things to look for. Many relations besides identity are transitive: larger than and less than are just two examples. And many are reflexive and/or symmetric: being the same size as and being inreflexive and symmetric relations the same row as are both. But you will run across other logical dependencies that don’t fall under these headings. For instance, you might be told that b is larger than c and want to infer that c is smaller than b. This holds because larger than and smaller than are what is known as “inverses”: they refer toinverse relations the same relation but point, so to speak, in opposite directions. Usually, you will have no trouble spotting the logical dependencies among predicates, but in giving a proof, you need to make explicit the ones you are assuming. Let’s look at one final example before trying our hand at some exercises. Suppose we were asked to give an informal proof of the following argument: RightOf(b, c) LeftOf(d, e) b = d LeftOf(c, e) Our informal proof might run like this: Proof: We are told that b is to the right of c. So c must be to the left of b, since right of and left of are inverses of one another. And since b = d, c is left of d, by the indiscernibility of identicals. But we are also told that d is left of e, and consequently c is to the left of e, by the transitivity of left of. This is our desired conclusion. Chapter 2 Formal proofs / 55 Notice that on the right of every step below the Fitch bar, we give a justification of the step. In our deductive system, a justification indicates justification which rule allows us to make the step, and which earlier steps (if any) the rule is applied to. In giving an actual formal proof, we will number the steps, so we can refer to them in justifying later steps. We already gave one example of a formal proof in the system F , back on page 48. For another example, here is a formalization of our informal proof of the symmetry of identity. 1. a = b 2. a = a = Intro 3. b = a = Elim: 2, 1 In the right hand margin of this proof you find a justification for each step below the Fitch bar. These are applications of rules we are about to introduce. The numbers at the right of step 3 show that this step follows from steps 2 and 1 by means of the rule cited. The first rule we use in the above proof is Identity Introduction. This = Intro rule allows you to introduce, for any name (or complex term) n in use in the proof, the assertion n = n. You are allowed to do this at any step in the proof, and need not cite any earlier step as justification. We will abbreviate our statement of this rule in the following way: Identity Introduction (= Intro): . n = n We have used an additional graphical device in stating this rule. This is the symbol . . We will use it in stating rules to indicate which step is being licensed by the rule. In this example there is only one step mentioned in the rule, but in other examples there will be several steps. The second rule of F is Identity Elimination. It tells us that if we have = Elim proven a sentence containing n (which we indicate by writing P(n)) and a sentence of the form n = m, then we are justified in asserting any sentence which results from P(n) by replacing some or all of the occurrences of n by m. Section 2.3 56 / The Logic of Atomic Sentences Identity Elimination (= Elim): P(n) ... n = m ... . P(m) When we apply this rule, it does not matter which of P(n) and n = m occurs first in the proof, as long as they both appear before P(m), the inferred step. In justifying the step, we cite the name of the rule, followed by the steps in which P(n) and n = m occur, in that order. We could also introduce rules justified by the meanings of other predicates besides = into the system F . For example, we could introduce a formal rule of the following sort: Bidirectionality of Between: Between(a,b, c) ... . Between(a, c, b) We don’t do this because there are just too many such rules. We could state them for a few predicates, but certainly not all of the predicates you will encounter in first-order languages. There is one rule that is not technically necessary, but which will makeReiteration some proofs look more natural. This rule is called Reiteration, and simply allows you to repeat an earlier step, if you so desire. Reiteration (Reit): P ... . P To use the Reiteration rule, just repeat the sentence in question and, on the right, write “Reit: x,” where x is the number of the earlier occurrence of the sentence. Chapter 2 Formal proofs / 57 Reiteration is obviously a valid rule of inference, since any sentence is a logical consequence of itself. The reason for having the rule will become clear as proofs in the system F become more complicated. For now, let’s just say that it is like remarking, in the course of giving an informal proof, “we have already shown that P.” This is often a helpful reminder to the person reading the proof. Now that we have the first three rules of F , let’s try our hand construct- ing a formal proof. Suppose we were asked to prove SameRow(b, a) from the premises SameRow(a, a) and b = a. We might begin by writing down the premises and the conclusion, leaving space in between to fill in the inter- mediate steps in our proof. 1. SameRow(a, a) 2. b = a ... ?. SameRow(b, a) It might at first seem that this proof should be a one step application of = Elim. But notice that the way we have stated this rule requires that we replace the first name in the identity sentence, b, for the second, a, but we want to substitute the other way around. So we need to derive a = b as an intermediate conclusion before we can apply = Elim. 1. SameRow(a, a) 2. b = a ... ?. a = b ?. SameRow(b, a) = Elim: 1, ? Since we have already seen how to prove the symmetry of identity, we can now fill in all the steps of the proof. The finished proof looks like this. Make sure you understand why all the steps are there and how we arrived at them. 1. SameRow(a, a) 2. b = a 3. b = b = Intro 4. a = b = Elim: 3, 2 5. SameRow(b, a) = Elim: 1, 4 Section 2.3 60 / The Logic of Atomic Sentences I 9. Add another step at the very end of your proof. Here’s a trick you will find handy: Click on the goal sentence at the very bottom of the window. This puts the focus on the goal sentence. Choose Copy from the Edit menu, and then click back on the empty step at the end of your proof. Choose Paste from the Edit menu and the goal sentence will be entered into this step. This time, justify the new step using = Elim and citing just the two premises. You will see that the step checks out. I 10. Save your proof as Proof Identity 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations Since the proof system F does not have any rules for atomic predicates other than identity, neither does Fitch. However, Fitch does have a mecha- nism that, among other things, lets you check for consequences among atomic sentences that involve many of the predicates in the blocks world language.1 This is a rule we call Analytic Consequence or Ana Con for short. AnaAnalytic Consequence Con is not restricted to atomic sentences, but that is the only application of the rule we will discuss at the moment. This rule allows you to cite some sentences in support of a claim if any world that makes the cited sentences true also makes the conclusion true, given the meaning of the predicates as used in Tarski’s World. Let’s get a feeling for Ana Con with some examples. You try it. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I 1. Use Fitch to open the file Ana Con 1. In this file you will find nine premises followed by six conclusions that are consequences of these premises. Indeed, each of the conclusions follows from three or fewer of the premises. I 2. Position the focus slider (the little triangle) at the first conclusion following the Fitch bar, SameShape(c,b). We have invoked the rule Ana Con but we have not cited any sentences. This conclusion follows from Cube(b) and Cube(c). Cite these sentences and check the step. I 3. Now move the focus slider to the step containing SameRow(b, a). Since the relation of being in the same row is symmetric and transitive, this follows from SameRow(b, c) and SameRow(a, c). Cite these two sentences and check the step. 1This mechanism does not handle the predicates Adjoins and Between, due to the com- plexity of the ways the meanings of these predicates interact with the others. Chapter 2 Constructing proofs in Fitch / 61 J4. The third conclusion, BackOf(e, c), follows from three of the premises. See if you can find them. Cite them. If you get it wrong, Fitch will give you an X when you try to check the step. J5. Now fill in the citations needed to make the fourth and fifth conclusions check out. For these, you will have to invoke the Ana Con rule yourself. (You will find the rule on the Con submenu of the Rule? popup.) J6. The final conclusion, SameCol(b,b), does not require that any premises be cited in support. It is simply an analytic truth, that is, true in virtue of its meaning. Specify the rule and check this step. J7. When you are done, choose Verify Proof to see that all the goals check out. Save your work as Proof Ana Con 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations The Ana Con mechanism is not really a rule, technically speaking, though rules vs. Con mechanismswe will continue to call it that since it appears on the Rule? menu in Fitch. This mechanism, along with the two others appearing on the Con submenu, apply complicated procedures to see whether the sentence in question follows from the cited sentences. As we will explain later, these three items try to find proofs of the sentence in question “behind the scenes,” and then give you a checkmark if they succeed. The proof they find may in fact apply many, many different rules in getting from the cited steps to the target sentence. The main difference you will run into between the genuine rules in Fitch and the mechanisms appearing on the Con menu is that the latter “rules” will sometimes fail even though your step is actually correct. With the genuine rules, Fitch will always give your step either a checkmark or an X, depending on whether the rule is applied correctly. But with the Con mechanisms, Fitch will sometimes try to find a proof of the target sentence but fail. In these cases, Fitch will give the step a question mark rather than a check or an X, since there might be a complicated proof that it just couldn’t find. To mark the difference between the genuine rules of F and the three con- sequence mechanisms, Fitch displays the rule names in green and the conse- quence mechanisms in blue. Because the Con mechanisms look for a proof behind the scenes, we will often ask you not to use them in giving solutions to homework problems. After all, the point is not to have Fitch do your home- work for you! In the following problems, you should only use the Ana Con rule if we explicitly say you can. To see whether a problem allows you to use any of the Con mechanisms, double click on the goal or choose See Goal Constraints from the Goal menu. Section 2.4 62 / The Logic of Atomic Sentences Remember The deductive system you will be learning is a Fitch-style deductive sys- tem, named F . The computer application that assists you in constructing proofs in F is therefore called Fitch. If you write out your proofs on paper, you are using the system F , but not the program Fitch. Exercises 2.15 ➶ If you skipped the You try it sections, go back and do them now. Submit the files Proof Identity 1 and Proof Ana Con 1. 2.16 ➶ Use Fitch to give a formal version of the informal proof you gave in Exercise 2.5. Remember, you will find the problem setup in the file Exercise 2.16. You should begin your proof from this saved file. Save your completed proof as Proof 2.16. In the following exercises, use Fitch to construct a formal proof that the conclusion is a consequence of the premises. Remember, begin your proof by opening the corresponding file, Exercise 2.x, and save your solution as Proof 2.x. We’re going to stop reminding you. 2.17 ➶ SameCol(a, b) b = c c = d SameCol(a, d) 2.18 ➶ Between(a, d,b) a = c e = b Between(c, d, e) 2.19 ➶ Smaller(a,b) Smaller(b, c) Smaller(a, c) You will need to use Ana Con in this proof. This proof shows that the pred- icate Smaller in the blocks language is transitive. 2.20 ➶ RightOf(b, c) LeftOf(d, e) b = d LeftOf(c, e) Make your proof parallel the informal proof we gave on page 52, using both an identity rule and Ana Con (where necessary). Chapter 2 Demonstrating nonconsequence / 65 J3. Arrange the blocks so that the conclusion is false. Check the premises. If any of them are false, rearrange the blocks until they are all true. Is the conclusion still false? If not, keep trying. J4. If you have trouble, try putting them in the order d, a, b, c. Now you will find that all the premises are true but the conclusion is false. This world is a counterexample to the argument. Thus we have demonstrated that the conclusion does not follow from the premises. J5. Save your counterexample as World Counterexample 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations Remember To demonstrate the invalidity of an argument with premises P1, . . . , Pn and conclusion Q, find a counterexample: a possible circumstance that makes P1, . . . ,Pn all true but Q false. Such a counterexample shows that Q is not a consequence of P1, . . . , Pn. Exercises 2.21 ➶ If you have skipped the You try it section, go back and do it now. Submit the world file World Counterexample 1. 2.22 ✎ Is the following argument valid? Sound? If it is valid, give an informal proof of it. If it is not valid, give an informal counterexample to it. All computer scientists are rich. Anyone who knows how to program a computer is a computer scientist. Bill Gates is rich. Therefore, Bill Gates knows how to program a computer. 2.23 ✎ Is the following argument valid? Sound? If it is valid, give an informal proof of it. If it is not valid, give an informal counterexample to it. Philosophers have the intelligence needed to be computer scientists. Anyone who be- comes a computer scientist will eventually become wealthy. Anyone with the intelli- gence needed to be a computer scientist will become one. Therefore, every philosopher will become wealthy. Section 2.5 66 / The Logic of Atomic Sentences Each of the following problems presents a formal argument in the blocks language. If the argument is valid, submit a proof of it using Fitch. (You will find Exercise files for each of these in the usual place.) Important: if you use Ana Con in your proof, cite at most two sentences in each application. If the argument is not valid, submit a counterexample world using Tarski’s World. 2.24 ➶ Larger(b, c) Smaller(b, d) SameSize(d, e) Larger(e, c) 2.25 ➶ FrontOf(a, b) LeftOf(a, c) SameCol(a, b) FrontOf(c,b) 2.26 ➶ SameRow(b, c) SameRow(a,d) SameRow(d, f) LeftOf(a, b) LeftOf(f, c) 2.27 ➶ SameRow(b, c) SameRow(a,d) SameRow(d, f) FrontOf(a, b) FrontOf(f, c) Section 2.6 Alternative notation You will often see arguments presented in the following way, rather than in Fitch format. The symbol .·. (read “therefore”) is used to indicate the conclusion: All men are mortal. Socrates is a man. .·. Socrates is mortal. There is a huge variety of formal deductive systems, each with its own notation. We can’t possibly cover all of these alternatives, though we describe one, the resolution method, in Chapter 17. Chapter 2 Chapter 3 The Boolean Connectives So far, we have discussed only atomic claims. To form complex claims, fol pro- vides us with connectives and quantifiers. In this chapter we take up the three simplest connectives: conjunction, disjunction, and negation, corresponding to simple uses of the English and, or, and it is not the case that. Because they Boolean connectives were first studied systematically by the English logician George Boole, they are called the Boolean operators or Boolean connectives. The Boolean connectives are also known as truth-functional connectives. truth-functional connectivesThere are additional truth-functional connectives which we will talk about later. These connectives are called “truth functional” because the truth value of a complex sentence built up using these connectives depends on nothing more than the truth values of the simpler sentences from which it is built. Because of this, we can explain the meaning of a truth-functional connective in a couple of ways. Perhaps the easiest is by constructing a truth table, a truth table table that shows how the truth value of a sentence formed with the connec- tive depends on the truth values of the sentence’s immediate parts. We will give such tables for each of the connectives we introduce. A more interesting Henkin-Hintikka game way, and one that can be particularly illuminating, is by means of a game, sometimes called the Henkin-Hintikka game, after the logicians Leon Henkin and Jaakko Hintikka. Imagine that two people, say Max and Claire, disagree about the truth value of a complex sentence. Max claims it is true, Claire claims it is false. The two repeatedly challenge one another to justify their claims in terms of simpler claims, until finally their disagreement is reduced to a simple atomic claim, one involving an atomic sentence. At that point they can simply examine the world to see whether the atomic claim is true—at least in the case of claims about the sorts of worlds we find in Tarski’s World. These successive challenges can be thought of as a game where one player will win, the other will lose. The legal moves at any stage depend on the form of the sentence. We will explain them below. The one who can ultimately justify his or her claims is the winner. When you play this game in Tarski’s World, the computer takes the side opposite you, even if it knows you are right. If you are mistaken in your initial assessment, the computer will be sure to win the game. If you are right, though, the computer plugs away, hoping you will blunder. If you slip up, the computer will win the game. We will use the game rules as a second way of explaining the meanings of the truth-functional connectives. 67 70 / The Boolean Connectives Exercises 3.1 If you skipped the You try it section, go back and do it now. There are no files to submit, but you wouldn’t want to miss it. 3.2 ➶ (Assessing negated sentences) Open Boole’s World and Brouwer’s Sentences. In the sentence file you will find a list of sentences built up from atomic sentences using only the negation symbol. Read each sentence and decide whether you think it is true or false. Check your assessment. If the sentence is false, make it true by adding or deleting a negation sign. When you have made all the sentences in the file true, submit the modified file as Sentences 3.2 3.3 ➶ (Building a world) Start a new sentence file. Write the following sentences in your file and save the file as Sentences 3.3. 1. ¬Tet(f) 2. ¬SameCol(c, a) 3. ¬¬SameCol(c,b) 4. ¬Dodec(f) 5. c 6= b 6. ¬(d 6= e) 7. ¬SameShape(f, c) 8. ¬¬SameShape(d, c) 9. ¬Cube(e) 10. ¬Tet(c) Now start a new world file and build a world where all these sentences are true. As you modify the world to make the later sentences true, make sure that you have not accidentally falsified any of the earlier sentences. When you are done, submit both your sentences and your world. 3.4 ✎ Let P be a true sentence, and let Q be formed by putting some number of negation symbols in front of P. Show that if you put an even number of negation symbols, then Q is true, but that if you put an odd number, then Q is false. [Hint: A complete proof of this simple fact would require what is known as “mathematical induction.” If you are familiar with proof by induction, then go ahead and give a proof. If you are not, just explain as clearly as you can why this is true.] Now assume that P is atomic but of unknown truth value, and that Q is formed as before. No matter how many negation symbols Q has, it will always have the same truth value as a literal, namely either the literal P or the literal ¬P. Describe a simple procedure for determining which. Chapter 3 Conjunction symbol: ∧ / 71 Section 3.2 Conjunction symbol: ∧ The symbol ∧ is used to express conjunction in our language, the notion we normally express in English using terms like and, moreover, and but. In first- order logic, this connective is always placed between two sentences, whereas in English we can also conjoin other parts of speech, such as nouns. For example, the English sentences John and Mary are home and John is home and Mary is home have the same first-order translation: Home(john) ∧ Home(mary) This sentence is read aloud as “Home John and home Mary.” It is true if and only if John is home and Mary is home. In English, we can also conjoin verb phrases, as in the sentence John slipped and fell. But in fol we must translate this the same way we would translate John slipped and John fell : Slipped(john) ∧ Fell(john) This sentence is true if and only if the atomic sentences Slipped(john) and Fell(john) are both true. A lot of times, a sentence of fol will contain ∧ when there is no visible sign of conjunction in the English sentence at all. How, for example, do you think we might express the English sentence d is a large cube in fol? If you guessed Large(d) ∧ Cube(d) you were right. This sentence is true if and only if d is large and d is a cube— that is, if d is a large cube. Some uses of the English and are not accurately mirrored by the fol conjunction symbol. For example, suppose we are talking about an evening when Max and Claire were together. If we were to say Max went home and Claire went to sleep, our assertion would carry with it a temporal implication, namely that Max went home before Claire went to sleep. Similarly, if we were to reverse the order and assert Claire went to sleep and Max went home it would suggest a very different sort of situation. By contrast, no such implication, implicit or explicit, is intended when we use the symbol ∧. The sentence WentHome(max) ∧ FellAsleep(claire) is true in exactly the same circumstances as FellAsleep(claire) ∧ WentHome(max) Section 3.2 72 / The Boolean Connectives Semantics and the game rule for ∧ Just as with negation, we can put complex sentences as well as simple ones together with ∧. A sentence P ∧ Q is true if and only if both P and Q are true. Thus P ∧ Q is false if either or both of P or Q is false. This can be summarized by the following truth table. P Q P ∧ Q true true true true false false false true false false false false truth table for ∧ The Tarski’s World game is more interesting for conjunctions than nega- tions. The way the game proceeds depends on whether you have committedgame rule for ∧ to true or to false. If you commit to the truth of P ∧ Q then you have implicitly committed yourself to the truth of each of P and Q. Thus, Tarski’s World gets to choose either one of these simpler sentences and hold you to the truth of it. (Which one will Tarski’s World choose? If one or both of them are false, it will choose a false one so that it can win the game. If both are true, it will choose at random, hoping that you will make a mistake later on.) If you commit to the falsity of P ∧ Q, then you are claiming that at least one of P or Q is false. In this case, Tarski’s World will ask you to choose one of the two and thereby explicitly commit to its being false. The one you choose had better be false, or you will eventually lose the game. You try it. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I 1. Open Claire’s World. Start a new sentence file and enter the sentence ¬Cube(a) ∧ ¬Cube(b) ∧ ¬Cube(c) I 2. Notice that this sentence is false in this world, since c is a cube. Play the game committed (mistakenly) to the truth of the sentence. You will see that Tarski’s World immediately zeros in on the false conjunct. Your commitment to the truth of the sentence guarantees that you will lose the game, but along the way, the reason the sentence is false becomes apparent. I 3. Now begin playing the game committed to the falsity of the sentence. When Tarski’s World asks you to choose a conjunct you think is false, pick the first sentence. This is not the false conjunct, but select it anyway and see what happens after you choose OK. Chapter 3 Disjunction symbol: ∨ / 75 If we wanted to express the exclusive sense of or in the above example, we could do it as follows: [Home(john) ∨ Home(mary)] ∧ ¬[Home(john) ∧ Home(mary)] As you can see, this sentence says that John or Mary is home, but it is not the case that they are both home. Many students are tempted to say that the English expression either . . . or expresses exclusive disjunction. While this is sometimes the case (and indeed the simple or is often used exclusively), it isn’t always. For example, suppose Pris and Scruffy are in the next room and the sound of a cat fight suddenly breaks out. If we say Either Pris bit Scruffy or Scruffy bit Pris, we would not be wrong if each had bit the other. So this would be translated as Bit(pris, scruffy) ∨ Bit(scruffy, pris) We will see later that the expression either sometimes plays a different logical function. Another important English expression that we can capture without intro- ducing additional symbols is neither. . . nor. Thus Neither John nor Mary is at home would be expressed as: ¬(Home(john) ∨ Home(mary)) This says that it’s not the case that at least one of them is at home, i.e., that neither of them is home. Semantics and the game rule for ∨ Given any two sentences P and Q of fol, atomic or not, we can combine them using ∨ to form a new sentence P ∨ Q. The sentence P ∨ Q is true if at least one of P or Q is true. Otherwise it is false. Here is the truth table. P Q P ∨ Q true true true true false true false true true false false false truth table for ∨ The game rules for ∨ are the “duals” of those for ∧. If you commit yourself game rule for ∨ to the truth of P ∨ Q, then Tarski’s World will make you live up to this by committing yourself to the truth of one or the other. If you commit yourself to the falsity of P ∨ Q, then you are implicitly committing yourself to the falsity Section 3.3 76 / The Boolean Connectives of each, so Tarski’s World will choose one and hold you to the commitment that it is false. (Tarski’s World will, of course, try to win by picking a true one, if it can.) You try it. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I 1. Open the file Ackermann’s World. Start a new sentence file and enter the sentence Cube(c) ∨ ¬(Cube(a) ∨ Cube(b)) Make sure you get the parentheses right! I 2. Play the game committed (mistakenly) to this sentence being true. Since the sentence is a disjunction, and you are committed to true, you will be asked to pick a disjunct that you think is true. Since the first one is obviously false, pick the second. I 3. You now find yourself committed to the falsity of a (true) disjunction. Hence you are committed to the falsity of each disjunct. Tarski’s World will then point out that you are committed to the falsity of Cube(b). But this is clearly wrong, since b is a cube. Continue until Tarski’s World says you have lost. I 4. Play the game again, this time committed to the falsity of the sentence. You should be able to win the game this time. If you don’t, back up and try again. I 5. Save your sentence file as Sentences Game 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations Remember 1. If P and Q are sentences of fol, then so is P ∨ Q. 2. The sentence P ∨ Q is true if and only if P is true or Q is true (or both are true). Exercises 3.8 ➶ If you skipped the You try it section, go back and do it now. You’ll be glad you did. Well, maybe. Submit the file Sentences Game 2. Chapter 3 Remarks about the game / 77 3.9 ➶ Open Wittgenstein’s World and the sentence file Sentences 3.6 that you created for Exercise 3.6. Edit the sentences by replacing ∧ by ∨ throughout, saving the edited list as Sentences 3.9. Once you have changed these sentences, decide which you think are true. Again, record your evaluations to help you remember them. Then go through and use Tarski’s World to evaluate your assessment. Whenever you are wrong, play the game to see where you went wrong. If you are never wrong, then play the game anyway a couple times, knowing that you should win. As in Exercise 3.6, find the maximum number of sentences you can make true by changing the size or shape (or both) of block f . Submit both your sentences and world. 3.10 ➶ Open Ramsey’s World and start a new sentence file. Type the following four sentences into the file: 1. Between(a, b, c) ∨ Between(b, a, c) 2. FrontOf(a,b) ∨ FrontOf(c, b) 3. ¬SameRow(b, c) ∨ LeftOf(b, a) 4. RightOf(b, a) ∨ Tet(a) Assess each of these sentences in Ramsey’s World and check your assessment. Then make a single change to the world that makes all four of the sentences come out false. Save the modified world as World 3.10. Submit both files. Section 3.4 Remarks about the game We summarize the game rules for the three connectives, ¬, ∧, and ∨, in Table 3.1. The first column indicates the form of the sentence in question, and the second indicates your current commitment, true or false. Which player moves depends on this commitment, as shown in the third column. The goal of that player’s move is indicated in the final column. Notice that commitment and rules although the player to move depends on the commitment, the goal of that move does not depend on the commitment. You can see why this is so by thinking about the first row of the table, the one for P ∨ Q. When you are committed to true, it is clear that your goal should be to choose a true disjunct. But when you are committed to false, Tarski’s World is committed to true, and so also has the same goal of choosing a true disjunct. There is one somewhat subtle point that should be made about our way of describing the game. We have said, for example, that when you are committed to the truth of the disjunction P ∨ Q, you are committed to the truth of one of the disjuncts. This of course is true, but does not mean you necessarily know which of P or Q is true. For example, if you have a sentence of the form Section 3.4 80 / The Boolean Connectives Parentheses are also used to indicate the “scope” of a negation symbolscope of negation when it appears in a complex sentence. So, for example, the two sentences ¬Home(claire) ∧ Home(max) ¬(Home(claire) ∧ Home(max)) mean quite different things. The first is a conjunction of literals, the first of which says Claire is not home, the second of which says that Max is home. By contrast, the second sentence is a negation of a sentence which itself is a con- junction: it says that they are not both home. You have already encountered this use of parentheses in earlier exercises. Many logic books require that you always put parentheses around any pair of sentences joined by a binary connective (such as ∧ or ∨). These books do not allow sentences of the form: P ∧ Q ∧ R but instead require one of the following: ((P ∧ Q) ∧ R) (P ∧ (Q ∧ R)) The version of fol that we use in this book is not so fussy, in a couple of ways. First of all, it allows you to conjoin any number of sentences without usingleaving out parentheses parentheses, since the result is not ambiguous, and similarly for disjunctions. Second, it allows you to leave off the outermost parentheses, since they serve no useful purpose. You can also add extra parentheses (or brackets or braces) if you want to for the sake of readability. For the most part, all we will require is that your expression be unambiguous. Remember Parentheses must be used whenever ambiguity would result from their omission. In practice, this means that conjunctions and disjunctions must be “wrapped” in parentheses whenever combined by means of some other connective. You try it. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I 1. Let’s try our hand at evaluating some sentences built up from atomic sentences using all three connectives ∧, ∨, ¬. Open Boole’s Sentences and Wittgenstein’s World. If you changed the size or shape of f while doing Exercises 3.6 and 3.9, make sure that you change it back to a large tetra- hedron. Chapter 3 Ambiguity and parentheses / 81 J2. Evaluate each sentence in the file and check your assessment. If your as- sessment is wrong, play the game to see why. Don’t go from one sentence to the next until you understand why it has the truth value it does. J3. Do you see the importance of parentheses? After you understand all the sentences, go back and see which of the false sentences you can make true just by adding, deleting, or moving parentheses, but without making any other changes. Save your file as Sentences Ambiguity 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations Exercises To really master a new language, you have to use it, not just read about it. The exercises and problems that follow are intended to let you do just that. 3.12 ➶ If you skipped the You try it section, go back and do it now. Submit the file Sentences Ambiguity 1. 3.13 ➶ (Building a world) Open Schröder’s Sentences. Build a single world where all the sentences in this file are true. As you work through the sentences, you will find yourself successively modifying the world. Whenever you make a change in the world, be careful that you don’t make one of your earlier sentences false. When you are finished, verify that all the sentences are really true. Submit your world as World 3.13. 3.14 ➶ (Parentheses) Show that the sentence ¬(Small(a) ∨ Small(b)) is not a consequence of the sentence ¬Small(a) ∨ Small(b) You will do this by submitting a coun- terexample world in which the second sentence is true but the first sentence is false. 3.15 ➶ (More parentheses) Show that Cube(a) ∧ (Cube(b) ∨ Cube(c)) is not a consequence of the sentence (Cube(a) ∧ Cube(b)) ∨ Cube(c) You will do this by submitting a coun- terexample world in which the second sentence is true but the first sentence is false. 3.16 ➶ (DeMorgan Equivalences) Open the file DeMorgan’s Sentences. Construct a world where all the odd numbered sentences are true. Notice that no matter how you do this, the even numbered sentences also come out true. Submit this as World 3.16.1. Next build a world where all the odd numbered sentences are false. Notice that no matter how you do it, the even numbered sentences also come out false. Submit this as World 3.16.2. Section 3.5 82 / The Boolean Connectives 3.17 ✎ In Exercise 3.16, you noticed an important fact about the relation between the even and odd numbered sentences in DeMorgan’s Sentences. Try to explain why each even numbered sentence always has the same truth value as the odd numbered sentence that precedes it. Section 3.6 Equivalent ways of saying things Every language has many ways of saying the same thing. This is particularly true of English, which has absorbed a remarkable number of words from other languages in the course of its history. But in any language, speakers always have a choice of many synonymous ways of getting across their point. The world would be a boring place if there were just one way to make a given claim. Fol is no exception, even though it is far less rich in its expressive capaci- ties than English. In the blocks language, for example, none of our predicates is synonymous with another predicate, though it is obvious that we could do without many of them without cutting down on the claims expressible in the language. For instance, we could get by without the predicate RightOf by expressing everything we need to say in terms of the predicate LeftOf, sys- tematically reversing the order of the names to get equivalent claims. This is not to say that RightOf means the same thing as LeftOf—it obviously does not—but just that the blocks language offers us a simple way to construct equivalent claims using these predicates. In the exercises at the end of this section, we explore a number of equivalences made possible by the predicates of the blocks language. Some versions of fol are more parsimonious with their basic predicates than the blocks language, and so may not provide equivalent ways of express- ing atomic claims. But even these languages cannot avoid multiple ways of expressing more complex claims. For example, P ∧ Q and Q ∧ P express the same claim in any first-order language. More interesting, because of the su- perficial differences in form, are the equivalences illustrated in Exercise 3.16, known as DeMorgan’s laws. The first of DeMorgan’s laws tells us that theDeMorgan’s laws negation of a conjunction, ¬(P ∧ Q), is logically equivalent to the disjunction of the negations of the original conjuncts: ¬P ∨ ¬Q. The other tells us that the negation of a disjunction, ¬(P ∨ Q), is equivalent to the conjunction of the negations of the original disjuncts: ¬P ∧ ¬Q. These laws are simple con- sequences of the meanings of the Boolean connectives. Writing S1 ⇔ S2 to indicate that S1 and S2 are logically equivalent, we can express DeMorgan’s Chapter 3 Translation / 85 In general, this is all we require of translations into and out of fol. Thus, given an English sentence S and a good fol translation of it, say S, any other sentence S′ that is equivalent to S will also count as an acceptable translation of it, since S and S′ have the same truth conditions. But there is a matter of style. Some good translations are better than others. You want sentences that are easy to understand. But you also want to keep the fol connectives close to the English, if possible. For example, a good translation of It is not true that Claire and Max are both at home would be given by ¬(Home(claire) ∧ Home(max)) This is equivalent to the following sentence (by the first DeMorgan law), so we count it too as an acceptable translation: ¬Home(claire) ∨ ¬Home(max) But there is a clear stylistic sense in which the first is a better translation, since it conforms more closely to the form of the original. There are no hard and fast rules for determining which among several logically equivalent sentences is the best translation of a given sentence. Many stylistic features of English have nothing to do with the truth con- ditions of a sentence, and simply can’t be captured in an fol translation. For example, consider the English sentence Pris is hungry but Carl is not. This sentence tells us two things, that Pris is hungry and that Carl is not hungry. So it would be translated into fol as Hungry(pris) ∧ ¬Hungry(carl) When it comes to truth conditions, but expresses the same truth function as and. Yet it is clear that but carries an additional suggestion that and does but, however, yet, nonethelessnot, namely, that the listener may find the sentence following the but a bit sur- prising, given the expectations raised by the sentence preceding it. The words but, however, yet, nonetheless, and so forth, all express ordinary conjunction, and so are translated into fol using ∧. The fact that they also communicate a sense of unexpectedness is just lost in the translation. Fol, as much as we love it, sometimes sacrifices style for clarity. In Exercise 21, sentences 1, 8, and 10, you will discover an important function that the English phrases either. . . or and both. . . and sometimes play. either. . . or, both. . . and Either helps disambiguate the following or by indicating how far to the left its scope extends; similarly both indicates how far to the left the following and extends. For example, Either Max is home and Claire is home or Carl Section 3.7 86 / The Boolean Connectives is happy is unambiguous, whereas it would be ambiguous without the either. What it means is that [Home(max) ∧ Home(claire)] ∨ Happy(carl) In other words, either and both can sometimes act as left parentheses act in fol. The same list of sentences demonstrates many other uses of either and both. Remember 1. The English expression and sometimes suggests a temporal ordering; the fol expression ∧ never does. 2. The English expressions but, however, yet, nonetheless, and moreover are all stylistic variants of and. 3. The English expressions either and both are often used like parentheses to clarify an otherwise ambiguous sentence. Exercises 3.20 ➶ (Describing a simple world) Open Boole’s World. Start a new sentence file, named Sen- tences 3.20, where you will describe some features of this world. Check each of your sentences to see that it is indeed a sentence and that it is true in this world. 1. Notice that f (the large dodecahedron in the back) is not in front of a. Use your first sentence to say this. 2. Notice that f is to the right of a and to the left of b. Use your second sentence to say this. 3. Use your third sentence to say that f is either in back of or smaller than a. 4. Express the fact that both e and d are between c and a. 5. Note that neither e nor d is larger than c. Use your fifth sentence to say this. 6. Notice that e is neither larger than nor smaller than d. Use your sixth sentence to say this. 7. Notice that c is smaller than a but larger than e. State this fact. 8. Note that c is in front of f ; moreover, it is smaller than f . Use your eighth sentence to state these things. Chapter 3 Translation / 87 9. Notice that b is in the same row as a but is not in the same column as f . Use your ninth sentence to express this fact. 10. Notice that e is not in the same column as either c or d. Use your tenth sentence to state this. Now let’s change the world so that none of the above mentioned facts hold. We can do this as follows. First move f to the front right corner of the grid. (Be careful not to drop it off the edge. You might find it easier to make the move from the 2-D view. If you accidentally drop it, just open Boole’s World again.) Then move e to the back left corner of the grid and make it large. Now none of the facts hold; if your answers to 1–10 are correct, all of the sentences should now be false. Verify that they are. If any are still true, can you figure out where you went wrong? Submit your sentences when you think they are correct. There is no need to submit the modified world file. 3.21 ➶ (Some translations) Tarski’s World provides you with a very useful way to check whether your translation of a given English sentence is correct. If it is correct, then it will always have the same truth value as the English sentence, no matter what world the two are evaluated in. So when you are in doubt about one of your translations, simply build some worlds where the English sentence is true, others where it is false, and check to see that your translation has the right truth values in these worlds. You should use this technique frequently in all of the translation exercises. Start a new sentence file, and use it to enter translations of the following English sentences into first-order logic. You will only need to use the connectives ∧, ∨, and ¬. 1. Either a is small or both c and d are large. 2. d and e are both in back of b. 3. d and e are both in back of b and larger than it. 4. Both d and c are cubes, however neither of them is small. 5. Neither e nor a is to the right of c and to the left of b. 6. Either e is not large or it is in back of a. 7. c is neither between a and b, nor in front of either of them. 8. Either both a and e are tetrahedra or both a and f are. 9. Neither d nor c is in front of either c or b. 10. c is either between d and f or smaller than both of them. 11. It is not the case that b is in the same row as c. 12. b is in the same column as e, which is in the same row as d, which in turn is in the same column as a. Before you submit your sentence file, do the next exercise. Section 3.7