AI-Portal Artificial Intelligence for Enthusiasts

Prenex Normal Form

In First Order Predicate Logic ( FOPL ), one can represent an expression using the operators

For any X, Expression

Exists X such that Expression.

Where Expression is a logic expression , either a predicate or a combination of logic operators and other expressions.

In order to represent an Expression in Prenex Normal Form, one must do some transformation. For an expression to be in Prenex Normal Form, all the "Any" and "Exists" Logical operators must precede a whole stand-alone expression. For example, expression

(Any X in P(X) ) Or ( Exists Y in Q(Y)) it''s not in Prenex Normal Form.


(Any X in ( P(X) and Q (Y) ) ) is in Prenex Normal Form .

Prenex Normal Form is useful in Knowledge representation for obvious reasons: memorizing in computer memory, specific attributes: We evaluate first the "Any"/"Exists" operators and the following expression can be substituted to simple expression.

To convert a normal expression to Prenex Normal Form, we consider the following transformation rules:

( Any X in Expr) or (Another_Expr) changes to (Any X in ( Expr or Another_Expr )) with mentioning the fact that X has no free appearances in Another_Expr ( if free they are renamed to another free variable )

( Any X in Expr) and (Another_Expr) changes to (Any X in (Expr and Another_Expr )) with same mentioning.

The same rules apply to Exists operator.