Formal Logic

Mark Jago

Description

This book introduces the techniques of formal logic in a way suitable for all students of philosophy.

Sujets

• Literary Criticism
• European

Informations

• Publié par: Humanities eBooks
• Date de parution: 11 janvier 2021
• Nombre de lectures: 0
• EAN13: 9781847600417
• Langue: English

Extrait

The World is all that is the case Philosophy Insights General Editor: Mark Addis

Running Head 1

Formal Logic

Mark Jago

‘What makes an argument valid?’

http//www.humanities-ebooks.co.uk For advice on use of this ebook please scroll to page 2

Publication Data

© Mark Jago, 2007

he Autor as asserted is rigt to be identified as te autor of tis Work in accord- ance wit te Copyrigt, Designs and Patents Act 1988. Publised byHumanitiesEbooks, LLP,Tirril Hall, Tirril, Penrit CA10 2

Reading Options

*To use te navigation tools, te searc facility, and oter features of te toolbar, tis Ebook sould be read in default view. *To navigate troug te contents use te yperlinked ‘Bookmarks’ at te left of te screen. *To searc, expand te searc column at te rigt of te screen or click on te bin- ocular symbol in te toolbar. *For ease of reading, use <CTRL+L> to enlarge te page to full screen *Use <Esc> to return to te full menu. *Hyperlinks appear in Blue Underlined Text. To return from an internal yperlink use te ‘previous view’ button and repeat if necessary. *For a computer generated reading use <View>Read out Loud>

Licence and permissions

Purcasing tis book licenses you to read tis work on-screen and to print one copy for your own use. Copy and paste functions are disabled. No part of tis publication may be oterwise reproduced or transmitted or distributed witout te prior written permission of bot te copyrigt owner and te publiser. Making or distributing copies of tis book constitutes copyrigt infringement and would be liable to prosecution. hank you for respecting te rigts of te autor.

ISBN 978-1-84760-041-7

F

o

r

m

a

l

Mark Jago

L

o

Bibliographical Entry:

g

i

c

Jago, Mark.Formal Logic. Philosophy Insights. Tirril: Humanities-Ebooks, 2007

A Note on the Author

Mark Jago is a lecturer in the Department of Philosophy at the University of Notting ham, UK and a Junior Research Associate in the Research Group on the Philosophy of Information at the University of Oxford. He wrote theWittgensteinguide in the Philosophy Insights series and has published articles on truth, belief, logic, fiction and information.

Personal website: http://www.nottingham.ac.uk/philosophy/staff/markjago.htm.

Contents

Introduction

1

2

3

4

Philosophy Insights:Formal Logic

Logical Reasoning 1.1 Preliminaries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Valid Arguments. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Valid Forms of Inference. . . . . . . . . . . . . . . . . . . . . . . . Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Propositional Logic 2.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Logical Connectives. . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 The Logical Language. . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Construction Trees. . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Truth Tables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Valuations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Entailment and Equivalence 3.1 Logical Entailment. . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Equivalence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Equivalence Schemes. . . . . . . . . . . . . . . . . . . . . . . . . . Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Proof Trees 4.1 Proofs in Logic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The Proof Tree Method. . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Examples of Proof Trees. . . . . . . . . . . . . . . . . . . . . . . . 4.4 Decidability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Valuations From Open Finished Trees. . . . . . . . . . . . . . . . . 4.6 Soundness and Completeness. . . . . . . . . . . . . . . . . . . . . . Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

7

9 9 10 12 15

16 16 17 20 23 24 27 30

32 32 34 36 39

41 41 41 44 45 46 48 49

5

6

7

Philosophy Insights:Formal Logic

First Order Logic 5.1 More Valid Arguments. . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Constants, Predicates and Relations. . . . . . . . . . . . . . . . . . 5.3 Existence and Generality. . . . . . . . . . . . . . . . . . . . . . . . 5.4 Formation Rules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Binary Relations. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Semantics for FirstOrder Logic. . . . . . . . . . . . . . . . . . . . 5.7 Satisfaction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Identity 6.1 The Puzzle of Identity. . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Identity in FirstOrder Logic. . . . . . . . . . . . . . . . . . . . . . 6.3 ExpressingAt Least,At MostandExactly. . . . . . . . . . . . . . . 6.4 Definite Descriptions. . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Leibniz’s Law and Second Order Logic. . . . . . . . . . . . . . . . Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Proof Trees for First Order Logic 7.1 Rules for Quantifiers. . . . . . . . . . . 7.2 Rules for Identity. . . . . . . . . . . . . 7.3 Undecidability. . . . . . . . . . . . . . . 7.4 Constructing Models from Open Branches 7.5 Soundness and Completeness. . . . . . . Exercises. . . . . . . . . . . . . . . . . . . .

Appendix A. Basic Set Theory

Appendix B. Infinity

References and Further Reading

Answers to Exercises

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

51 51 52 54 57 58 62 65 68

70 70 70 71 74 75 76

78 78 83 84 85 88 89

91

92

94

95

Introduction

Logical reasoning is vital to philosophy. Descartes for one recognized this in hisRules for the Direction of the Mind(1628), where he writes: R ULE is need of a method for investigating the truth about things.4: There R ULE we shall be observing this method exactly if we reduce complex5: . . . and obscure propositions step by step to simpler ones, and then, by retracing our steps, try to rise from intuition of all of the simplest ones to knowledge of all the rest. Descartes’ aim was first to find principles whose truth he could be certain of and then to deduce further truths from these. This raises the question, just what counts as rea soning correctly from one proposition to another? This is what we hope to understand through studying logic. There are different views as to what studying logic should achieve, including the following: We should aim to discoverlogical truths, i.e. sentences that could not possibly be  false and which we can discover to be truea priori. We should aim to discovervalid forms of reasoningto use in our arguments.  We should aim to discover the principles of logical entailment, so that we can  ascertain the facts that are entailed by what we know to be the case. Fortunately for us, these approaches to logic all turn out to be interchangeable, at least in the form of logic that we will study here, known asclassical logic. Strange as it sounds at first, there is not one body of doctrine or method that can be labelled ‘logic’. There are disagreements over what principles apply to the notion of logical entailment and over what counts as a valid argument. These disagreements constitute the philosophyoflogic, which I will not go into in this book. As a rule of thumb, whenever someone speaks oflogic, unqualified as this or that style of logic, they will meanclassical first order logic. This is certainly true in most philosophy classes (at least, those not dealing with technical subjects such as the philosophy of logic or mathematics). Classical logic is also adopted as the logic of choice in mathematics 1 and electronics, although not always in computer science.

1 Classical logic is focused ontruth, whereas computer scientists are often focused on the kinds of tasks that computers can do and in particular, what computers canprove. Focusing onproofrather thantruthis the province ofconstructive logics.

Philosophy Insights:Formal Logic

8

The following chapters outline the basic features of classical logic. We begin In chapter1with a brief informal outline of some of the features of logical reasoning. In chapters2through to4, we investigatepropositional logic, in which we uncover the logical relations that hold between propositions of certain kinds. Finally, first order logic, the big brother of propositional logic, is presented in chapters5to7. A very short introduction to set theory and the concept of infinity is provided as an appendix. If you have never come across the notion of a set before, or find symbols such as ‘∈’ or concepts such ascountablethat you are unfamiliar with in the book, you might want to begin by reading the appendix.

1. Logical Reasoning

1.1

Preliminaries

Ambiguity, Sentences and Propositions

In logic, we are concerned with precise forms of reasoning and so we have to be careful to avoid ambiguity. The English sentence, ‘visiting relatives can be boring’ is ambiguous, for it can mean either that it can be boring to visit relatives or that the relatives who are visiting can be boring. If we do not know what the sentence means, we cannot tell what inferences can correctly be drawn from it. In logic, therefore, we only deal with unambiguous sentences. We can think of the unambiguous sentences and propositions of logic as statements, that is, sentences that state something quite unambiguously. Grammatically, such sentences are in theindicativemood. We can always tell whether a sentence is indicative by asking, does it make sense to say that the sentence is true (or false)? Here are some examples.

Indicative Sentences ‘It’s raining somewhere in Scotland right now.’  ‘I know that I exist.’  ‘If you go outside, you should take an umbrella.’ 

NonIndicative Sentences ‘Is it raining?’  ‘Close the door!’  ‘I hereby name this ship . . . .’  ‘If you go outside, take an umbrella.’  Philosophers sometimes use the term ‘proposition’ to mean an unambiguous indica tive sentence, capable of being true or false, although ‘proposition’ has also been 1 given other, more technical meanings by philosophers. I will use the term ‘propo sition’ throughout the first half of the course (when we look atpropositional logic)

1 Bertrand Russell took propositions to be abstract entities containing the very things in the world that the corresponding sentence is about, for example. Other philosophers take propositions to be sets of possible worlds.

Philosophy Insights:Formal Logic

10

and I will always mean no more than an unambiguous indicative sentence (so propo sitions are simply one type of sentence). In the second half I will talk aboutsentences rather than propositions but still mean unambiguous indicative sentences. There is no real difference between sentences and propositions as I will use the terms; the only difference is how they are treated by the logic we are looking at.

1.2

Valid Arguments

A valid argument is one in which the conclusion could not possibly be false whilst all the premises are simultaneously true. Throughout this book, we will take ‘false’ to be synonymous with ‘not true’ and so an argument is valid just in casethe conclusion is true if all of the premises are simultaneously true. By way of example: Premise 1:If it’s raining, then I had better take an umbrella. Premise 2:It’s raining. Conclusion:Therefore, I had better take an umbrella. The conclusion follows logically from the premises and so the argument is valid. We can usepropositional logicto show why this is (we will do so in chapter2). An example of aninvalidargument is Premise 1:All men are mortal. Conclusion:Socrates is mortal. The argument is invalid, even though both its premise and its conclusion are true, because the truth of the premise does not guarantee the truth of the conclusion. The premise guarantees something about men; but ‘Socrates’ might be the name of my pet goldfish. To be sure, goldfish are mortal too but the premise does not guarantee that this is so. Someone might argue that the laws of physics guarantee that goldfish are mortal. In this case, the premise plus the laws of physics guarantee the conclusion but the argument, as stated above, does not say anything about these laws. Someone living on a different planet (or even in a parallel universe) in which goldfish scientists have discovered the elixir for immortality (but withheld it from humans) could truly assert the premise but not the conclusion. In a logically valid argument, on the other hand, this cannot be the case. The truth of the premises must guarantee the truth of the conclusion, even in circumstances wildly different from our own.