Adjusted normal form

In predicate logic , a formula is called adjusted if

1. no variable in the formula once as free occurs and as a bound variable,
2. there is another variable behind each quantifier .

Each formula has an equivalent adjusted formula. Each formula can be converted into a corrected form by appropriate, bound renaming. ${\displaystyle F}$

example

${\displaystyle F:=\forall x\exists y\left(P\left(x,y\right)\wedge Q\left(x,z\right)\right)}$

${\displaystyle G:=\exists u\left(\forall vP\left(u,v\right)\vee Q\left(v,v\right)\right)}$

In the formula the variables and are bound and is free. is thus adjusted. In the formula , all occurrences of the variable are bound, but both bound and free occur. is therefore not in an adjusted form. A transfer for is the following renaming (when renaming, the bound variables must be renamed): ${\displaystyle F}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle G}$

${\displaystyle G':=\exists u\left(\forall wP\left(u,w\right)\vee Q\left(v,v\right)\right)}$

See also

• Normal form