Normal Forms
George Boolos, John P. Burgess, Richard C. Jeffrey · Cambridge University Press eBooks · 2007
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. […]