Book contents
- Frontmatter
- Contents
- Preface to the Fifth Edition
- COMPUTABILITY THEORY
- BASIC METALOGIC
- FURTHER TOPICS
- 19 Normal Forms
- 20 The Craig Interpolation Theorem
- 21 Monadic and Dyadic Logic
- 22 Second-Order Logic
- 23 Arithmetical Definability
- 24 Decidability of Arithmetic without Multiplication
- 25 Nonstandard Models
- 26 Ramsey's Theorem
- 27 Modal Logic and Provability
- Annotated Bibliography
- Index
19 - Normal Forms
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface to the Fifth Edition
- COMPUTABILITY THEORY
- BASIC METALOGIC
- FURTHER TOPICS
- 19 Normal Forms
- 20 The Craig Interpolation Theorem
- 21 Monadic and Dyadic Logic
- 22 Second-Order Logic
- 23 Arithmetical Definability
- 24 Decidability of Arithmetic without Multiplication
- 25 Nonstandard Models
- 26 Ramsey's Theorem
- 27 Modal Logic and Provability
- Annotated Bibliography
- Index
Summary
A normal form theorem of the most basic type tells us that for every formula A there is a formula A* of some special syntactic form such that A and A* are logically equivalent. A normal form theorem for satisfiability tells us that for every set г of sentences there is a set г* of sentences of some special syntactic form such that г and г* are equivalent for satisfiability, meaning that one will be satisfiable if and only if the other is. In section 19.1 we establish the prenex normal form theorem, according to which every formula is logically equivalent to one with all quantifiers at the beginning, along with some related results. In section 19.2 we establish the Skolem normal form theorem, according to which every set of sentences is equivalent for satisfiability to a set of sentences with all quantifiers at the beginning and all quantifiers universal. We then use this result to give an alternative proof of the Löwenheim–Skolem theorem, which we follow with some remarks on implications of the theorem that have sometimes been thought ‘paradoxical’. In the optional section 19.3 we go on to sketch alternative proofs of the compactness and Gödel completeness theorems, using the Skolem normal form theorem and an auxiliary result known as Herbrand's theorem. In section 19.4 we establish that every set of sentences is equivalent for satisfiability to a set of sentences not containing identity, constants, or function symbols. […]
- Type
- Chapter
- Information
- Computability and Logic , pp. 243 - 259Publisher: Cambridge University PressPrint publication year: 2007