First-Order Logic

ISBN-13: 9783642867200 / Angielski / Miękka / 2012 / 160 str.

Raymond R. Smullyan

Opis

Except for this preface, this study is completely self-contained. It is intended to serve both as an introduction to Quantification Theory and as an exposition of new results and techniques in "analytic" or "cut-free" methods. We use the term "analytic" to apply to any proof procedure which obeys the subformula principle (we think of such a procedure as "analysing" the formula into its successive components). Gentzen cut-free systems are perhaps the best known example of ana lytic proof procedures. Natural deduction systems, though not usually analytic, can be made so (as we demonstrated in 3]). In this study, we emphasize the tableau point of view, since we are struck by its simplicity and mathematical elegance. Chapter I is completely introductory. We begin with preliminary material on trees (necessary for the tableau method), and then treat the basic syntactic and semantic fundamentals of propositional logic. We use the term "Boolean valuation" to mean any assignment of truth values to all formulas which satisfies the usual truth-table conditions for the logical connectives. Given an assignment of truth-values to all propositional variables, the truth-values of all other formulas under this assignment is usually defined by an inductive procedure. We indicate in Chapter I how this inductive definition can be made explicit-to this end we find useful the notion of a formation tree (which we discuss earlier)."

Spis treści

I. Propositional Logic from the Viewpoint of Analytic Tableaux.- I. Preliminaries.- §0. Foreword on Trees.- §1. Formulas of Propositional Logic.- §2. Boolean Valuations and Truth Sets.- II. Analytic Tableaux.- §1. The Method of Tableaux.- §2. Consistency and Completeness of the System.- III. Compactness.- §1. Analytic Proofs of the Compactness Theorem.- §2. Maximal Consistency: Lindenbaum’s Construction.- §3. An Analytic Modification of Lindenbaum’s Proof.- §4. The Compactness Theorem for Deducibility.- II. First-Order Logic.- IV. First-Order Logic. Preliminaries.- §1. Formulas of Quantification Theory.- §2. First-Order Valuations and Models.- §3. Boolean Valuations vs. First-Order Valuations.- V. First-Order Analytic Tableaux.- §1. Extension of Our Unified Notation.- §2. Analytic Tableaux for Quantification Theory.- §3. The Completeness Theorem.- §4. The Skolem-Löwenheim and Compactness Theorems for First-Order Logic.- VI. A Unifying Principle.- §1. Analytic Consistency.- §2. Further Discussion of Analytic Consistency.- §3. Analytic Consistency Properties for Finite Sets.- VII. The Fundamental Theorem of Quantification Theory.- §1. Regular Sets.- §2. The Fundamental Theorem.- §3. Analytic Tableaux and Regular Sets.- §4. The Liberalized Rule D.- VIII. Axiom Systems for Quantification Theory.- §0. Foreward on Axiom Systems.- §1. The System Q1.- §2. The Systems Q2, Q*2.- IX. Magic Sets.- §1. Magic Sets.- §2. Applications of Magic Sets.- X. Analytic versus Synthetic Consistency Properties.- §1. Synthetic Consistency Properties.- §2. A More Direct Construction.- III. Further Topics in First-Order Logic.- XI. Gentzen Systems.- §1. Gentzen Systems for Propositional Logic.- §2. Block Tableaux and Gentzen Systems for First-Order Logic.- XII. Elimination Theorems.- §1. Gentzen’s Hauptsatz.- §2. An Abstract Form of the Hauptsatz Ill.- §3. Some Applications of the Hauptsatz.- XIII. Prenex Tableaux.- §1. Prenex Formulas.- §2. Prenex Tableaux.- XIV. More on Gentzen Systems.- §1. Gentzen’s Extended Hauptsatz.- §2. A New Form of the Extended Hauptsatz.- §3. Symmetric Gentzen Systems.- XV. Craig’s Interpolation Lemma and Beth’s Definability Theorem.- §1. Craig’s Interpolation Lemma.- §2. Beth’s Definability Theorem.- XVI. Symmetric Completeness Theorems.- §1. Clashing Tableaux.- §2. Clashing Prenex Tableaux.- §3. A Symmetric Form of the Fundamental Theorem.- XVII. Systems of Linear Reasoning.- §1. Configurations.- §2. Linear Reasoning.- §3. Linear Reasoning for Prenex Formulas.- §4. A System Based on the Strong Symmetrie Form of the Fundamental Theorem.- References.