Logic with Trees

An Introduction to Symbolic Logic

Colin Howson

• Publisher: Routledge
• Year: 2005
• ISBN:
  9781134785506
• Edition: 1
• Topic: Philosophy
• Subtopic: Philosophy History & Theory

Logic With Trees is a new and original introduction to modern formal logic. Unlike most texts, it also contains discussions on more philosophical issues such as truth, conditionals and modal logic. It presents the formal material with clarity, preferring informal explanations and arguments to intimidatingly rigorous development. Worked examples and excercises enable the readers to check their progress. Logic With Trees equips students with * a complete and clear account of the truth-tree system for first order logic * the importance of logic and its relevance to many different disciplines * the skills to grasp sophisticated formal reasoning techniques necessary to explore complex metalogic * the ability to contest claims that `ordinary' reasoning is well represented by formal first order logic The issues covered include a thorough discussion of truth-functional and full first order logic, using the truth-tree or semantic tableau approach. Completeness and Soundness proofs are given for both truth-functional and first order trees. Much use is made of induction, which is presented in a clear and consistent manner. There is also discussion of alternative deductive systems, an introduction to transfinite numbers and categoricity, the Lowenhein-Skolem theories and the celebrated findings of Godel and Church. The book concludes with an account of Kripke's attempted solution of the liar paradox and a discussion of the weakness of truth-functional account of conditionals. Particularly useful to those who favour critical accounts of formal reasoning, it will be of interest to students of philosophy at first level and beyond and also students of mathematics and computer science.

Part I

Truth-Functional Logic

Chapter 1

The Basics

1 Deductively Valid Inference

There is much more to logic than the question of what makes inferences deductively valid or invalid, but to most people that is what logic is all about, so that is where we shall begin. One of the most basic features of these inferences is that they seem to be composed of declarative sentences, that is to say sentences which make assertions capable of being true or false. ‘Boris Yeltsin became President of Russia in 1993’, ‘All hydrogen atoms have one proton in their nucleus’ and ‘Michelangelo painted the ceiling of the Sistine Chapel’ are declarative sentences, and (we believe) true ones at that. ‘Shut that door!’ and ‘Is Hanoi in Scotland?’ are not. Neither is Chomsky’s funny example ‘Colourless green ideas sleep furiously’, which has the grammatical form, but only the form, of a fact-stating sentence.

So far, so good. The sentences composing an inference are its premises and conclusion, the latter usually signalled by the prefix ‘therefore’ (for which, for brevity, we shall often use the symbol ∴). If the inference is deductively valid the conclusion is called a deductive or logical consequence, or simply consequence, of the premises. What else do we know? Well, one of the most familiar facts about deductively valid inferences, and the one which probably goes farthest towards explaining the importance they have always been accorded, is that it is impossible for their conclusions to be false if their premises are true: if anything is basic to the notion of deduction, that surely is. Consider this example, known as a disjunctive syllogism:

It’s raining or it’s snowing.

It’s not raining.

∴ It’s snowing.

Clearly, you don’t have to know whether it’s actually raining or not, or snowing or not, to know that if the premises are true, so too is the conclusion. Not only is the conclusion true if the premises are. The conclusion must be true if the premises are true; there is no possibility of its being false.

Not only is this the most important property of deductively valid inferences; it is difficult to think of any other that has that same generality. This being so, we might as well take it as the defining property, and accordingly frame the following

Provisional definition: a valid deductive inference is one whose premises cannot all be true and conclusion false.

The definition is provisional because the word ‘cannot’ itself rather obviously needs a definition, and providing an adequate one is not trivial: most of this book will be occupied in the task. But one thing we do know is that ‘cannot’ here has nothing at all to do with empirical fact, as it does in the statement that water cannot unaided run uphill. ‘Cannot’ in this context refers to a logical impossibility. It is a logical, not merely a physical, impossibility that ‘It’s snowing’ is false if both ‘It’s either raining or it’s snowing’ and ‘It’s not raining’ are true (assuming sameness of spatio-temporal reference in premises and conclusion). Here are two more examples to consider.

If Lev is in Moscow then Irina is in Kiev.

Lev is in Moscow.

∴ Irina is in Kiev.

Cain was hairy and Abel was his victim.

∴ Cain was hairy.

It is intuitively clear that these remain deductively valid, in the sense of the definition above, whatever sentences are substituted for ‘Cain was hairy’, ‘Abel was his victim’, ‘Lev is in Moscow’, ‘Irina is in Kiev’ and, in the disjunctive syllogism, ‘It’s raining’ and ‘it’s snowing’. Another way of putting it is to say that if we replace these sentences by the letters A, B, C, D, E and F, the respective formal representations (or formalisations) of these inferences

E or F

not E

∴ F

If A then B

A

∴ B

C and D

∴ C

will always generate deductively valid inferences when the letters A, B, C, D, E and F are replaced by any sentences.

An explanation of why this is so will plausibly rest on an analysis of the logical role played by the particles ‘and’, ‘or’, ‘not’, and ‘if… then—’. Now, a common method of analysing some phenomenon is to construct a model of it and see whether the model behaves in a way sufficiently resembling what it is supposed to model. This will be our procedure. The model, which will be presented in a systematic form in Chapter 3, is called a propositional language. ‘And’, ‘or’, ‘not’, etc. are basic syntactical items of these languages, and in the following sections we shall describe the way they are used to form compound truth-functional sentences, and the rules which determine how truth and falsity should be ascribed to these. (The syntax of a language is the set of rules which determine its formal structure, that is to say the way its basic vocabulary is organised into well-formed expressions, among which are the sentences of the language; the rules by which the sentences are equipped with truthconditions constitute the language’s semantics.)

2 Syntax: Connectives and the Principle of Composition

‘And’, ‘or’, ‘if…then—’ are structural items, called connectives by logicians, which articulate sentences into further sentences. ‘Cain was hairy’ and ‘Abel was his victim’ are said to be conjoined by ‘and’ to yield the conjunction ‘Cain was hairy and Abel was his victim’; the two sentences forming the conjunction are its conjuncts. ‘Not’ operates on the sentence ‘It’s raining’ to generate its negation ‘It’s not raining.’ ‘It’s raining’ and ‘it’s snowing’ are disjoined by ‘or’ to form the disjunction ‘It’s raining or it’s snowing’ of those two sentences, which are called the disjuncts. The sentences ‘Lev is in Moscow’ and ‘Irina is in Kiev’ are combined into the conditional sentence ‘If Lev is in Moscow then Irina is in Kiev’; ‘Lev is in Moscow’ is the antecedent, and ‘Irina is in Kiev’ is the consequent.

These connectives play such a fundamental role that they have been given special symbols by logicians. The following are now standard:

Connective	Symbol
not	¬
and	∧
or	∨
if…then	→

Because they operate on pairs of sentences to generate other sentences, ∧, ∨ and → are binary connectives; ¬ is unary, because it operates on single sentences. In what follows we shall refer, as just now, to ∧, ∨, and → directly as connectives rather than as connective symbols.

In our model the basic items out of which its sentences are built are these connectives and a stock of capital letters A, B, C, D, etc., called sentence letters, from the beginning of the Roman alphabet. These are intended to represent some given set of English sentences with whose internal structure we are not concerned. The sentence letters are often called the atomic sentences of the model, because all its other sentences are compounded from them, using the connectives. The first level of composition consists of the negations, disjunctions, conjunctions of sentence letters, and conditionals formed from them. Each of these compounds ...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright
• Dedication
• Contents
• Acknowledgments
• Introduction
• Part I: Truth-functional logic
• Part II: First-order logic
• List of notation
• Answers to selected exercises
• References
• Name index
• Subject index