Solvable Cases of the Decision Problem
Published on 14. May 2014
123 pages
978-0-08-095735-7 (ISBN)
Description
Provability, Computability and Reflection
More details
Other editions
Additional editions
Lev D. Beklemishev
Provability, Computability and Reflection: Volume 15
Book
04/2000
Elsevier
€210.46
Article exhausted; check different version
Content
- Front Cover
- Solvable Cases of the Decision Problem
- Copyright Page
- CONTENTS
- CHAPTER I. VALIDITY AND SATISFIABILITY IN FINITE DOMAINS
- 1. Well-formed formulas
- 2. Valuation of well-formed formulas in a finite domain. Validity and satisfiability
- CHAPTER II. THE DECISION PROBLEM
- 1. Valuation in arbitrary domains. Universal validity
- 2. Equivalences
- 3. S-formulas. Elimination of the propositional variables
- 4. Normal forms
- 5. Three forms of the decision problem
- CHAPTER III. SOLUTION OF THE DECISION PROBLEM FOR EQUALITY FORMULAS
- 1. Solution of the form II of the decision problem
- 2. Another criterion for the universal validity of equality formulas
- CHAPTER IV. SOLUTION OF THE DECISION PROBLEX FOR WELL- FORMED FORMULAS CONTAINING ONLY MONADIC PREDICATE VARIABLES
- 1. Solution of the form II of the decision problem for wffs which do not contain bound predicate variables and the sign of equality
- 2. Elimination theorems
- 3. General solution of the decision problem for wffs with only monadic predicate variables
- CHAPTER V. SOME GENERAL THEOREMS ABOUT THE VALIDITY OF FORMULAS OF THE PREDICATE CALCULUS OF FIRST ORDER INCLUDING EQUALITY
- 1. Skolem's normal form
- 2. Theorems about the validity of wffs not containing the sign of equality
- 3. Theorems about the validity of wffs which may contain the sign of equality
- CHAPTER VI. SOLUTION OF THE DECISION PROBLEM FOR WFFS WITH SPECIAL PREFIXES
- 1. Remarks on the selection of special cases of the decision problem
- 2. Solution for wffs having prefixes consisting solely of universal quantifiers
- 3. Solution for wffs having prefixes consisting solely of existential quantifiers
- 4. Reduction of the decision problem for wffs with certain prefixes to that for wffs with simpler prefixes
- 5. Solution for wffs having prefixes such that all the universal quantifiers precede all the existential ones
- CHAPTER VII. FURTHER CLASSES OF PREFIXES FOR WHICH THE DECISION PROBLEM CAN BE SOLVED
- 1. Solution for wffs having prefixes containing only one existential quantifier
- 2. Solution for wffs having prefixes containing only two existential quantifiers which are not separated by universal quantifiers
- CHAPTER VIII. GENERAL REMARKS ABOUT FURTHER INVESTIGATIONS
- 1. Limitation of the range of the method hitherto used
- 2. Some other cases for which the decision problem has been solved
- 3. A general theorem about the validity of wffs
- CHAPTER IX. THE DECISION PROBLEM FOR WFFS WITH FUNCTIONAL VARIABLES
- 1. Introduction of wffs with functional variables
- 2. Special cases for which the decision problem is solved for wffs with functional variables
- BIBLIOGRAPHY
- INDEX
