normal form

normal form a formula equivalent to a given logical formula, but having special properties. The main varieties follow. Conjunctive normal form. If D1 . . . Dn are disjunctions of sentential variables or their negations, such as (p 7 -q 7 r), then a formula F is in conjunctive normal form provided F % D1 & D2 & . . & Dn. The following are in conjunctive normal form: (-p 7 q); (p 7 q 7 r) & (-p 7 -q 7 -r) & (-q 7 r). Every formula of sentential logic has an equivalent conjunctive normal form; this fact can be used to prove the completeness of sentential logic. Disjunctive normal form. If C1 . . . Cn are conjunctions of sentential variables or their negations, such as p & -q & -r, then a formula F is in disjunctive normal form provided F % C1 7 C27 . . Cn. The following are thus in disjunctive normal form: (p & -q) 7 (-p & q); (p & q & -r) 7 (-p & -q & -r). Every formula of sentential logic has an equivalent disjunctive normal form. Prenex normal form. A formula of predicate logic is in prenex normal form if (1) all quantifiers occur at the beginning of the formula, (2) the scope of the quantifiers extends to the end of the formula, and (3) what follows the quantifiers contains at least one occurrence of every variable that appears in the set of quantifiers. Thus, (Dx)(Dy)(Fx / Gy) and (x)(Dy)(z)((Fxy 7 Gyz) / Dxyz) are in prenex normal form. The formula may contain free variables; thus, (Dx)(y) (Fxyz / Gwyx) is also in prenex normal form. The following, however, are not in prenex normal form: (x)(Dy) (Fx / Gx); (x)(y) Fxy / Gxy. Every formula of predicate logic has an equivalent formula in prenex normal form. Skolem normal form. A formula F in predicate logic is in Skolem normal form provided (1) F is in prenex normal form, (2) every existential quantifier precedes any universal quantifier, (3) F contains at least one existential quantifier, and (4) F contains no free variables. Thus, (Dx)(Dy) (z)(Fxy / Gyz) and (Dx)(Dy)(Dz)(w)(Fxy 7 Fyz 7 Fzw) are in Skolem normal form; however, (Dx) (y) Fxyz and (x) (y) (Fxy 7 Gyx) are not. Any formula has an equivalent Skolem normal form; this has implications for the completeness of predicate logic. See also COMPLETENESS. V.K.

meaning of the word normal form root of the word normal form composition of the word normal form analysis of the word normal form find the word normal form definition of the word normal form what normal form means meaning of the word normal form emphasis in word normal form