•Procedimento para Obtenção da Forma Normal Prenex
–1.
Eliminar os conectivos lógicos ®
e « usando as seguintes leis:
•F « G = (F ®
G) ^ (G ® F)
•(F ® G) = Ø
F v G
–2.
Repetir o uso das seguintes leis:
•Ø Ø F
= F
•Ø (F v G) = Ø
F ^ Ø G
•Ø (F ^ G) = Ø
F v Ø G
•Ø ("xF(x)) = $
x(Ø F(x))
•Ø ($ x F(x)) = "x(Ø F(x)
•Estas leis são utilizadas para trazer
os sinais de negação para
antes dos átomos.
–3.
Padronizar as variáveis, se necessário, de modo que cada quantificador possua
sua própria variável.
–4. Usar
as leis abaixo de forma a mover os quantificadores para a esquerda da fórmula para obter a Forma Normal
PRENEX.
•Qx F(x) v G = Qx (F(x) v G)
•Qx F(x) ^ G = Qx (F(x) ^ G)
•"x F(x) ^ "x G(x) = "x (F(x) ^ G(x))
•$ x F(x) v $
x G(x) = $ x (F(x) v G(x))
•Q1x F(x) v Q2x
G(x) = Q1x Q2z(F(x) v G(z))
•Q3x F(x) ^ Q4x
G(x) = Q3x Q4z(F(x) ^ G(z))
–EXEMPLO
1
•"x P(x) ® $
x Q(x)
•"x P(x) ® $
x Q(x) = Ø "x P(x) v $
x Q(x)
•$ x (Ø P(x)) v $
x Q(x)
•$ x (Ø P(x) v Q(x))
–