Formal Logic : Its Scope and Limits

by Jeffrey, Richard; Burgess, John P.

• ISBN13: 9780872208131
• ISBN10: 0872208133
• Edition: 4th
• Format: Hardcover
• Copyright: 2006-03-30
• Publisher: Hackett Pub Co Inc

Summary

The first beginning logic text to employ the tree method -- a complete formal system of first-order logic that is remarkably easy to understand and use -- this text allows students to take control of the nuts and bolts of formal logic quickly, and to move on to more complex and abstract problems. The tree method is elaborated in manageable steps over five chapters, in each of which its adequacy is reviewed; soundness and completeness proofs are extended at each step, and the decidability proof is extended at the step from truth functions to the logic of non-overlapping quantifiers with a single variable, after which undecidability is demonstrated by example. The first three chapters are bilingual, with arguments presented twice, in logical notation and in English. The last three chapters consider the discoveries defining the scope and limits of formal methods that marked logic's coming of age in the 20th century: Godel's completeness and incompleteness theorems for first and second-order logic, and the Church-Turing theorem on the undecidability of first order logic. This new edition provides additional problems, solutions to selected problems, and two new Supplements: 'Truth-Functional Equivalence' reinstates material on that topic from the second edition that was omitted in the third, and 'Variant Methods', in which John Burgess provides a proof regarding the possibility of modifying the tree method so that it will always find a finite model when there is one, and another, which shows that a different modification -- once contemplated by Jeffrey -- can result in a dramatic speed-up of certain proofs.

Author Biography

Richard Jeffrey (1926-2002) was Professor of Philosophy, Princeton University.John P. Burgess is Professor of Philosophy, Princeton University.

Table of Contents

Preface to the Fourth Edition	xi
Truth-Functional Logic	1	(20)
``Not,'' ``And''	2	(1)
``Or''	3	(1)
Is This Argument Valid?	4	(1)
A Bad Argument	4	(1)
Soundness	5	(1)
``If''	6	(1)
Denial, Conjunction, Disjunction	6	(2)
Conditionals	8	(1)
Counterfactual Conditionals	9	(1)
Biconditionals and Logical Equivalence	10	(1)
Rules of Valuation	10	(1)
Oddities of ``If''	11	(2)
Rules of Formation	13	(1)
Consistency and the Science of Refutation	14	(1)
Tautologies	15	(1)
Context Dependency	15	(2)
Formal Validity	17	(1)
Problems	18	(3)
Truth Trees	21	(14)
A Closed Tree	22	(2)
An Open Finished Tree	24	(1)
Double Denial	24	(1)
Flowchart for ``--'' and ``→'' with Examples	25	(2)
Rules of Inference, with Flowchart	27	(2)
Problems	29	(2)
Adequacy of the Tree Test	31	(1)
Decidability	32	(1)
Soundness	33	(1)
Completeness	34	(1)
Generality	35	(24)
Universal Instantiation (``UI'')	37	(1)
Existential Instantiation (``El'')	38	(1)
UI Again---Closure	39	(1)
Examples	40	(1)
Rules of Formation	41	(3)
The Complete Method, with Flowchart	44	(2)
Logical Structure	46	(2)
Problems	48	(1)
Interpretations	49	(2)
Rules of Interpretation	51	(1)
Counterexamples	52	(2)
``Some S's Are P''	54	(1)
Decidability	55	(1)
Completeness	55	(1)
Soundness	56	(1)
``Some S's Are P'': Solution	57	(2)
Multiple Generality	59	(16)
Example	59	(1)
Example	60	(1)
Logic into English	61	(1)
Linkage	62	(1)
Rules of Formation	63	(1)
English into Logical Notation	64	(1)
Example: Alma's Narcissism Inflames the Baron	65	(1)
Example: Alma Inflamed by Her Own Narcissism	66	(1)
Amor Vincit Omnia	66	(1)
Problems	67	(1)
Infinite Counterexamples	68	(2)
More Problems	70	(1)
Undecidability	70	(1)
Soundness	70	(1)
Completeness	71	(1)
Translation Drill	72	(2)
Exercises	74	(1)
Identity	75	(10)
Rules of Inference for Identity	76	(2)
Saying of What Is Not That It Is Not	78	(1)
Definite Descriptions	79	(1)
Number	80	(1)
Problems	81	(1)
Rule of Interpretation for Identity	81	(1)
Soundness	81	(1)
Completeness	82	(1)
Examples of Modified Interpretations	83	(1)
Problems	84	(1)
Functions	85	(14)
Rule of Formation	86	(1)
Rule of Interpretation	87	(1)
El and UI Revised	88	(1)
Regulating UI, with Flowchart	89	(1)
Adequacy	90	(3)
Problems	93	(1)
Mathematical Reasoning and Groups	93	(2)
Problems	95	(1)
Robinson Arithmetic	96	(1)
Problems	97	(2)
Uncomputability	99	(14)
How to Program a Register Machine	100	(2)
Problems	102	(1)
Register Machine Tree Tests	102	(3)
The Church-Turing Thesis	105	(1)
Unsolvability of the Halting Problem	106	(3)
Problems	109	(1)
Programs in Logical Notation	110	(2)
Problems	112	(1)
Undecidability	113	(12)
The Decision Problem	114	(1)
A Routine Test for Halting	115	(1)
The Argument Is Valid iff the Program Halts	116	(3)
Focusing the Undecidability Result	119	(2)
A Solvable Case of the Decision Problem	121	(1)
Undecidability without Function Symbols	121	(1)
Undecidability of Two-Place Predicate Logic	122	(1)
Problems	123	(2)
Incompleteness	125	(16)
Second-Order Logic	125	(3)
Problems	128	(1)
Logical Types	128	(2)
Russell's Paradox	130	(1)
Second-Order Formation and Valuation Rules	131	(1)
Mathematical Induction	132	(2)
Isomorphism, Categoricity, Completeness	134	(1)
Incompleteness of Validity Tests for Second-Order Logic	135	(3)
Problems	138	(1)
Some History	139	(2)
Supplement A Truth-Functional Equivalence	141	(10)
Venn Diagrams	141	(2)
Laws of Equivalence	143	(1)
Normal Form	144	(3)
Expressive Completeness	147	(1)
Simplification	147	(1)
Logic Circuits	148	(2)
Problems	150	(1)
Supplement B Variant Methods	151	(10)
Looking for Finite Models	152	(1)
Finding Finite Models	153	(1)
Adequacy of the Method	154	(1)
The Cut Rule	155	(1)
Speedy Closure with Cut	156	(1)
Slow Closure without Cut	157	(1)
Problems	158	(3)
Solutions	161	(10)
Index	171