Skolem normal form

Skolem is a term of predicate logic and refers to a predicate logic formula that is in a normal form after Thoralf Skolem Albert. Algorithms for testing the satisfiability often use the Skolem. This is useful, since each set of formulas X is satisfiable if their Skolem is satisfiable. Furthermore, the Skolem is a useful intermediate step if you want to transform a formula in clause normal form. It is also required as an intermediate result, if you want to create a Herbrand universe.

In the Skolem no existential () are included more. Variables that were bound to existential quantifiers are replaced by new function symbols. The arguments of the new function symbols get the variables of the universal quantifiers (), which stood in front of the remote existential.

Algorithm for generating the Skolem

This gives a formula according to Skolem, if one applies the following transformations on an adjusted, prenex formula F:

As long as F contains an existential quantifier:

Note: stands for the formula G, was in the x replaced by w. Skolem function f is called, in the case Skolemkonstante.

As a result, we obtain the formula F in Skolem. Other designations are Skolemization of F or Skolem'sche normal form. Note that in the above- forming does not necessarily maintain the logical equivalent. Although you will obtain the satisfiability of the formula and is thus erfüllbarkeitsäquivalent, but is not model- sustaining. This means that an interpretation which satisfies the original formula, not necessarily also satisfies the skolemisierte formula (see also logic ), which is not surprising due to the re -interpret the function symbol.

Example

Is adjusted in prenex form (BPF ).

By applying the algorithm above we obtain:

  • The first step is replaced by the zero- ary function newly introduced:
  • Is then introduced as a replacement for:
  • Then is replaced. For the 1- digit function is introduced. It receives as an argument the bound by universal quantifier variable, because the universal quantifier precedes the existential quantifier.

Now the formula is in the Skolem constants, and a 1- ary function symbol in front.

  • Logic
Term algebra
733461
de