Three Views of Logic: Mathematics, Philosophy, and Computer Science - Softcover

Loveland, Donald W.; Hodel, Richard; Sterrett, S. G.

Softcover

ISBN 10: 0691160449 ISBN 13: 9780691160443

Verlag: Princeton University Press, 2014

Inhaltsangabe

Demonstrating the different roles that logic plays in the disciplines of computer science, mathematics, and philosophy, this concise undergraduate textbook covers select topics from three different areas of logic: proof theory, computability theory, and nonclassical logic. The book balances accessibility, breadth, and rigor, and is designed so that its materials will fit into a single semester. Its distinctive presentation of traditional logic material will enhance readers' capabilities and mathematical maturity. The proof theory portion presents classical propositional logic and first-order logic using a computer-oriented (resolution) formal system. Linear resolution and its connection to the programming language Prolog are also treated. The computability component offers a machine model and mathematical model for computation, proves the equivalence of the two approaches, and includes famous decision problems unsolvable by an algorithm. The section on nonclassical logic discusses the shortcomings of classical logic in its treatment of implication and an alternate approach that improves upon it: Anderson and Belnap's relevance logic. Applications are included in each section. The material on a four-valued semantics for relevance logic is presented in textbook form for the first time. Aimed at upper-level undergraduates of moderate analytical background, Three Views of Logic will be useful in a variety of classroom settings. * Gives an exceptionally broad view of logic * Treats traditional logic in a modern format * Presents relevance logic with applications * Provides an ideal text for a variety of one-semester upper-level undergraduate courses

Über diesen Titel

Über die Autorin bzw. den Autor

Donald W. Loveland is professor emeritus of computer science at Duke University and the author of Automated Theorem Proving: A Logical Basis. Richard E. Hodel is associate professor emeritus of mathematics at Duke University and the author of An Introduction to Mathematical Logic. S. G. Sterrett is the Curtis D. Gridley Distinguished Professor of History and Philosophy of Science at Wichita State University and the author of Wittgenstein Flies a Kite: A Story of Models of Wings and Models of the World.

Von der hinteren Coverseite

"Formal logic should no longer be taught as a course within a single subject area, but should be taught from an interdisciplinary perspective. Three Views of Logic has many fine features and combines materials not found together elsewhere. We have needed an accessible textbook like this one for quite some time."--Hans Halvorson, Princeton University

"This concise, precise, and clear textbook is unique in the range of material covered and the level at which it is written, which is intended for undergraduates. The exercises are a considerable help to the student and the examples are useful and interesting."--David Plaisted, University of North Carolina, Chapel Hill

"Loveland, Hodel, and Sterrett are all internationally recognized and leading researchers in their field. Their new textbook gives an excellent introduction to the resolution of propositional and first-order predicate logic, and an outstanding overview of computability theory. The examples and exercises are well chosen, and the material is accessible to students without a logic background."--Frank Wolter, University of Liverpool

Aus dem Klappentext

"Formal logic should no longer be taught as a course within a single subject area, but should be taught from an interdisciplinary perspective. Three Views of Logic has many fine features and combines materials not found together elsewhere. We have needed an accessible textbook like this one for quite some time."--Hans Halvorson, Princeton University

"This concise, precise, and clear textbook is unique in the range of material covered and the level at which it is written, which is intended for undergraduates. The exercises are a considerable help to the student and the examples are useful and interesting."--David Plaisted, University of North Carolina, Chapel Hill

"Loveland, Hodel, and Sterrett are all internationally recognized and leading researchers in their field. Their new textbook gives an excellent introduction to the resolution of propositional and first-order predicate logic, and an outstanding overview of computability theory. The examples and exercises are well chosen, and the material is accessible to students without a logic background."--Frank Wolter, University of Liverpool

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

THREE VIEWS OF LOGIC

Mathematics, Philosophy, and Computer Science

By DONALD W. LOVELAND, RICHARD E. HODEL, S. G. STERRETT

PRINCETON UNIVERSITY PRESS

Copyright © 2014 Princeton University Press
All rights reserved.

ISBN: 978-0-691-16044-3

Contents

Preface, ix, 
Acknowledgments, xiii, 
PART 1. Proof Theory DONALD W. LOVELAND, 1, 
1 Propositional Logic, 3, 
2 Predicate Logic, 31, 
3 An Application: Linear Resolution and Prolog, 61, 
PART 2. Computability Theory RICHARD E. HODEL, 93, 
4 Overview of Computability, 95, 
5 A Machine Model of Computability, 123, 
6 A Mathematical Model of Computability, 165, 
PART 3. Philosophical Logic S. G. STERRETT, 221, 
7 Non-Classical Logics, 223, 
8 Natural Deduction: Classical and Non-Classical, 243, 
9 Semantics for Relevance Logic: A Useful Four-Valued Logic, 288, 
10 Some Concluding Remarks on the Logic of Entailment, 315, 
References, 316, 
Index, 319, 

CHAPTER 1

Propositional Logic

There are several reasons that one studies computer-oriented deductivelogics. Such logics have played an important role in natural languageunderstanding systems, in intelligent database theory, in expert systems,and in automated reasoning systems, for example. Deductivelogics have even been used as the basis of programming languages, atopic we consider in this book. Of course, deductive logics have beenimportant long before the invention of computers, being key to thefoundations of mathematics as well as a guide in the general realm ofrational discourse.

What is a deductive logic? It has two major components, a formallanguage and a notion of deduction. A formal language has a syntaxand semantics, just like a natural language. The first formal language wepresent is the propositional logic.

We first give the syntax of the propositional logic.

• Alphabet

1. Statement Letters: P, Q, R, P1, Q1, R1, ....

2. Logical Connectives: [conjunction], [disjunction], [logical not], [right arrow], [left and right arrow].

3. Punctuation: (,).

• Well-formed formulas (wffs), or statements

1. Statement letters are wffs (atomic wffs or atoms).

2. If A and B are wffs, then so are

([logical not]A), (A [disjunction] B), (A [conjunction] B), (A [right arrow] B), and (A [left and right arrow] B).

Convention. For any inductively defined class of entities we will assumea closure clause, meaning that only those items created by (often repeateduse of) the defining rules are included in the defined class.

We will denote statement letters with the letters P, Q, R, possiblywith subscripts, and wffs by letters from the first part of the alphabetunless explicitly noted otherwise. Statement letters are considered to benon-logical symbols.

We list the logical connectives with their English labels. (The negationsymbol doesn't connect anything; it only has one argument. However,for convenience we ignore that detail and call all the listed logicalsymbols "connectives.")

[logical not] negation

[conjunction] and

[disjunction] or

[right arrow] implies

[left and right arrow] equivalence

Example. ((([logical not]P) [conjunction] Q) [right arrow] (P [right arrow] Q)).

A formal language, like a natural language, has an alphabet and anotion of grammar. Here the grammar is simple; the wffs (statements)are our sentences. As even our simple example shows, the parenthesesmake statements very messy. We usually simplify matters by forgoingtechnically correct statements in favor of sensible abbreviations. Wesuppress some parentheses by agreeing on a hierarchy of connectives.However, it is always correct to retain parentheses to aid quick readabilityeven if rules permit further elimination of parentheses. We also willuse brackets or braces on occasion to enhance readability. They are to beregarded as parentheses formally.

We give the hierarchy with the tightest binding connective on top.

[logical not]

[disjunction], [conjunction]

[right arrow], [left and right arrow]

We adopt association-to-the-right.

A [right arrow] B [right arrow] C is (A [right arrow] (B [right arrow] C)).

Place the parentheses as tightly as possible consistent with the existingbindings, beginning at the top of the hierarchy.

Example. The expression [logical not] P [conjunction] Q [right arrow] P [right arrow] Q represents the wff

((([logical not]P) [conjunction] Q) [right arrow] (P [right arrow] Q)).

A more readable expression, also called a wff for convenience, is

([logical not]P [conjunction] Q) [right arrow] (P [right arrow] Q).

1.1 Propositional Logic Semantics

We first consider the semantics of wffs by seeing their source as naturallanguage statements.

English to formal notation.

Example 1. An ongoing hurricane implies no class meeting, so if nohurricane is ongoing then there is a class meeting.

Use: H: there is an ongoing hurricane

C: there is a class meeting

Formal representation.

(1) A

(2) (H [right arrow] [logical not]C) [right arrow] ([logical not]H [right arrow] C)

(3) (H [right arrow] [logical not]C) [conjunction] [(H [right arrow] [logical not]C) [right arrow] ([logical not]H [right arrow] C)]

The first representation is technically correct (ignoring the "use" instruction),but useless. The idea is to formalize a sentence in as fine-grainedan encoding as is possible with the logic at hand. The secondand third representations do this.

Notice that there are three different English expressions encodedby the implies symbol. "If ... then" and "implies" directly translateto the formal implies connective. "So" is trickier. If "so" implies thetruth of the first clause, then wff (3) is preferred as the clause is assertedand connected by the logical "and" symbol to the implication.The second interpretation simply reflects that the antecedent of "so"(supposedly) implies the consequent. This illustrates that formalizingnatural language statements is often an exercise in guessing the intentof the natural language statement. The task of formalizing informalstatements is often best approached by creating a candidate wff andthen directly replacing the statement letters by the assigned Englishmeanings and judging how successfully the wff captures the intent ofthe informal statement. One does this by asserting the truth of thewff and then considering the truth status of the component parts.For example, asserting the truth of wff (3) forces the truth of the twocomponents of the logical "and" by the meaning of logical "and." Weconsider the full "meaning" of implication shortly. One should tryalternate wffs if there is any question that the wff first tried is notclearly satisfactory. Doing this in this case yields representations (2) and(3). Which is better depends on one's view of the use of "so" in thissentence.

Aside: For those who suspect that this is not a logically true formula,you are correct. We deal with this aspect later.

Example 2. Either I study logic now or I go to the game. If I study logicnow I will pass the exam but if I go to the game I will fail the exam.Therefore, I will go to the game and drop the course.

Use: L: I study logic now

G: I go to the game

P: Ipass theexam

D: I drop the course

Formal representation.

(1) (L [disjunction] G) [conjunction] [((L [right arrow] P) [conjunction] (G [right arrow] [logical not]P)) [right arrow] G [conjunction] D]or

(2) ((L [disjunction] G) [conjunction] (L [right arrow] P) [conjunction] (G [right arrow] [logical not]P)) [conjunction] [((L [right arrow] P) ^ (G [right arrow] [logical not]P)) [right arrow] G [conjunction] D].

"Therefore" is another English trigger for the logical "implies" connectivein the wff that represents the English sentences. Again, it isa question of whether the sentences preceding the "therefore" areintended as facts or only as part of the conditional statement. Twopossibilities are given here. As before, the logical "and" forces theassertion of truth of its two components when the full statement isasserted to be true. Note that the association-to-the-right is used here toavoid one pair of added parentheses in representation (2). We do groupthe first three subformulas (conjuncts) together reflecting the Englishsense.

As illustrated above, logic studies the truth value of natural languagesentences and their associated wffs. The truth values are limited to true(T) and false (F) in classical logic. All interpreted wffs have truth values.To determine the truth values of interpreted wffs we need to definethe meaning of the logical connectives. This is done by a truth table,which defines the logical symbols as functions from truth values totruth values. (We often refer to these logical functions as the logicalconnectives of propositional logic.)

Definition. The following truth tables are called the defining truth tablesfor the given functions.

Although there appears to be only one "table" displayed here, it isbecause we have combined the defining truth table for each connectiveinto one compound truth table.

To illustrate the use of the truth tables, consider the "and" function.Suppose we have a wff (possibly a subformula) of form A [conjunction] B where weknow that A and B both have truth value F. The first two columns givethe arguments of the logical functions so we choose the fourth row.A [conjunction] B has value F inthat rowsowe knowthat A [conjunction] B has value F when eachof A and B has truth value F. All the logical functions except "implies"are as you have usually understood the meaning of those functions.Notice that the "or" function is the inclusive or. We discuss the function"implies" shortly, but a key concept is that this definition forces thefalsity of A [right arrow] B tomean both that A is true and B is false.

The idea of logic semantics is that the user specifies the truth valueof the statement letters, or atoms, and the logical structure of the wffas determined by the connectives supplies the truth value of the entirewff. We capture this "evaluation" of the wffs by defining a valuationfunction.

We will need a number of definitions that deal with propositionallogic semantics and we give them together for easier reference later,followed by an illustration of their use. Here and hereafter we use "iff"for "if and only if."

Definition. An interpretation associates a T or F with each statementletter.

Definition. A valuation function V is a mapping from wffs and interpretationsto T and F, determined by the defining truth tables of the logicalconnectives. We write VI [A] for the value of the valuation of wff Aunder interpretation I of A.

Definition. A wff A is a tautology (valid wff) iff VI [A] = T for allinterpretations I.

Example. The wff P [disjunction] [logical not] P is a tautology.

We now consider further the choice we made in the defining truthtable for implication. We have chosen a truth table for implication thatyields the powerful result that the theorems of the deductive logic westudy in this part of the book are precisely the valid wffs. That is, we areable to prove precisely the set of wffs that are true in all interpretations.The implication function chosen here is called material implication.Other meanings (i.e., semantics) for implication are considered in Part 3of this book.

Definition. A wff A is satisfiable iff there exists an interpretation I suchthat VI [A] = T.

We also say "I makes A true" and "I satisfies A."

Definition. A wff A is unsatisfiable iff the wff is not satisfiable; i.e., theredoes NOT exist an interpretation I such that VI [A] = T.

Definition. Interpretation I is a model of wff A iff VI]A] = T. I is a modelof a set S of wffs iff I is a model of each wff of S. If A is satisfiable, thenA has a model.

Definition. A is a logical consequence of a set S of wffs iff every model ofS is a model of A.

Notation. We will have occasion to explicitly represent finite sets. Oneway this is done is by listing themembers. Thus, if A1, A2, and A3 are the(distinct) members of a set then we can present the set as { A1, A2, A3}.{ Ai|1 ≤ i ≤ n} represents a set with n members A1, A2, ..., An. {A} representsa set with one member, A.

Notation. S [??] A denotes the relation that A is a logical consequence ofthe set S of wffs. We write [??] A iff A is a tautology. We write [??] A for thenegation of [??] A. We sometimes write P [??] Q for {P} [??] Q where P andQ are wffs.

Definition. A and B are logically equivalent wffs iff A and B have exactlythe samemodels.

We illustrate the valuation function.

Example. Determine the truth value of the following sentence underthe given interpretation.

An ongoing hurricane implies no class meeting, so if no hurricane isongoing then there is a class meeting.

Use: H: there is an ongoing hurricane

C: there is a class meeting

Interpretation I is as follows.

I(H) = T I(C) = T

Then

VI [(H [right arrow] [logical not]C) [right arrow] ([logical not]H [right arrow]C)] = ??

We determine VI. We omit the subscript on V when it is understood.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The above gives the truth value of the statement under the choseninterpretation. That is, the meaning and truth value of the statement isdetermined by the interpretation and the correct row in the truth tablethat corresponds to the intended interpretation. Thus,

VI [(H [right arrow] [logical not]C) [right arrow] ([logical not]H [right arrow] C)] = T.

Now let us check as to whether the statement is a tautology. Followingthe tradition of presentation of truth tables, we omit reference tothe interpretation and valuation function in the column headings,even though the entries T, F are determined by the interpretation andvaluation function in the rows as above. Of course, the interpretationchanges with each row.

We see that the statement A is not a tautology because VI[A] = Funder I(H) = F and I(C) = F.

(Continues...)

Excerpted from THREE VIEWS OF LOGIC by DONALD W. LOVELAND, RICHARD E. HODEL, S. G. STERRETT. Copyright © 2014 Princeton University Press. Excerpted by permission of PRINCETON UNIVERSITY PRESS.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Details zur Ausgabe

• Verlag: Princeton University Press
• Erscheinungsdatum: 2014
• Sprache: Englisch
• ISBN 10: 0691160449
• ISBN 13: 9780691160443
• Einband: Tapa blanda
• Anzahl der Seiten: 344
• Kontakt zum Hersteller: Nicht verfügbar
• Verantwortliche Person: Nicht verfügbar