Editing Skolem normal form (section)

== Examples ==

The simplest form of Skolemization is for existentially quantified variables that are not inside the [[scope (logic)|scope]] of a universal quantifier. These may be replaced simply by creating new constants. For example, <math>\exists x P(x)</math> may be changed to <math>P(c)</math>, where <math>c</math> is a new constant (does not occur anywhere else in the formula).

More generally, Skolemization is performed by replacing every existentially quantified variable <math>y</math> with a term <math>f(x_1,\ldots,x_n)</math> whose function symbol <math>f</math> is new. The variables of this term are as follows. If the formula is in [[prenex normal form]], then <math>x_1,\ldots,x_n</math> are the variables that are universally quantified and whose quantifiers precede that of <math>y</math>. In general, they are the variables that are quantified universally (we assume we get rid of existential quantifiers in order, so all existential quantifiers before <math>\exists y</math> have been removed) and such that <math>\exists y</math> occurs in the scope of their quantifiers. The function <math>f</math> 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'''.
 
As an example, the formula <math>\forall x \exists y \forall z P(x,y,z)</math> is not in Skolem normal form because it contains the existential quantifier <math>\exists y</math>. Skolemization replaces <math>y</math> with <math>f(x)</math>, where <math>f</math> is a new function symbol, and removes the quantification over {{nowrap|<math>y</math>.}} The resulting formula is <math>\forall x \forall z P(x,f(x),z)</math>. The Skolem term <math>f(x)</math> contains <math>x</math>, but not <math>z</math>, because the quantifier to be removed <math>\exists y</math> is in the scope of <math>\forall x</math>, but not in that of <math>\forall z</math>; since this formula is in prenex normal form, this is equivalent to saying that, in the list of quantifiers, <math>x</math> precedes <math>y</math> while <math>z</math> does not. The formula obtained by this transformation is satisfiable if and only if the original formula is.