AI-Portal Artificial Intelligence for Enthusiasts
Prenex Normal Form
- Details
- Written by Administrator
- Category: Uncategorised
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.
Expression
(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.