↑ arvau

Wikipedia / Skolem normal form

In mathematical logic, a formula of first-order logic is in Skolem normal form if it is in prenex normal form with only universal first-order quantifiers.

Every first-order formula may be converted into Skolem normal form while not changing its satisfiability via a process called Skolemization (sometimes spelled Skolemnization). The resulting formula is not necessarily equivalent to the original one, but is equisatisfiable with it: it is satisfiable if and only if the original one is satisfiable.

Reduction to Skolem normal form is a method for removing existential quantifiers from formal logic statements, often performed as the first step in an automated theorem prover.

Examples

The simplest form of Skolemization is for existentially quantified variables that are not inside the scope is a new constant (does not occur anywhere else in the formula).

is new. The variables of this term are as follows. If the formula is in prenex normal form introduced in this process is called a Skolem function (or Skolem constant if it is of zero arity) and the term is called a Skolem term.

is a new function symbol, and removes the quantification over does not. The formula obtained by this transformation is satisfiable if and only if the original formula is.

How Skolemization works

Skolemization works by applying a second-order equivalence together with the definition of first-order satisfiability. The equivalence provides a way for "moving" an existential quantifier before a universal one.

where

  1. .

".

This equivalence is useful because the definition of first-order satisfiability implicitly existentially quantifies over functions interpreting the function symbols. In particular, a first-order formula of the free variables of the formula that evaluate the formula to true.

At the meta-level, first-order satisfiability in the definition of first-order satisfiability.

as follows. This formula is satisfied by a model true. By the axiom of choice.

Uses of Skolemization

One of the uses of Skolemization is within automated theorem proving. For example, in the method of analytic tableaux, to a model of the new formula.

This form of Skolemization is an improvement over "classical" Skolemization in that only variables that are free in the formula are placed in the Skolem term. This is an improvement because the semantics of tableaux may implicitly place the formula in the scope of some universally quantified variables that are not in the formula itself; these variables are not in the Skolem term, while they would be there according to the original definition of Skolemization. Another improvement that may be used is applying the same Skolem function symbol for formulae that are identical up to variable renaming.

Another use is in the resolution method for first-order logic, where formulas are represented as sets of clausess understood to be universally quantified. (For an example see drinker paradox.)

An important result in model theory is the Löwenheim–Skolem theorem, which can be proven via Skolemizing the theory and closing under the resulting Skolem functions.

Skolem theories

is a theory and for each formula with free variables there is an n is called a Skolem theory.

Every Skolem theory is model complete, i.e. every substructure of a model is an elementary substructure. Given a model M of a Skolem theory T, the smallest substructure of M containing a certain set A is called the Skolem hull of A. The Skolem hull of A is an atomic prime model over A.

History

Skolem normal form is named after the late Norwegian mathematician Thoralf Skolem.

See also

Notes

References