Forma normal prenex
Origem: Wikipédia, a enciclopédia livre.
Na lógica de predicados uma fórmula está na forma normal prenex se cada variável desta fórmula cai no escopo de algum quantificador e se todos os quantificadores estão juntos precedendo uma sentença livre de quantificadores. Uma fórmula na forma normal prenex apresenta portanto a seguinte forma:
onde é uma fórmula livre de quantificadores, chamada de matriz. A parte
é chamado de prefixo da fórmula, onde
são variáveis distintas e
ou
para cada
. No caso em que todos os
são quantificadores universais, a fórmula é dita universalmente fechada.
Todas as fórmulas de primeira ordem são logicamente equivalentes a alguma fórmula na forma normal prenex.
Índice |
[editar] Deslocando os quantificadores
Para pôr uma fórmula na forma normal prenex, movemos todos os quantificadores à esquerda dos conectivos lógicos . Se a fórmula contiver algum conectivo
, entao antes de proceder a este processo, devemos eliminar este conectivo da fórmula usando a redução:
Para mover cada quantificador à esquerda de cada tipo destes conectivos devemos usar uma das reduções a seguir.
Observe que a renomeação de todas as variáveis é para se garantir que todas as variáveis diferentes tenham distintos nomes. Se não tivermos este cuidado, pode acontecer que a fórmula resultante não seja equivalente à original. Por exemplo, no caso da fórmula , se aplicarmos a redução (3) obtemos a fórmula
. Mas, senão tivessemos realizado a renomeação de variáveis, teriamos obtido a fórmula
, onde a ocorrência de variável
em
, que antes era livre, passaria a ser ligada, alterando completamente o sentido da fórmula e portanto transformando a fórmula original numa fórmula não equivalente.
[editar] Exemplo
Seja a fórmula:
Uma seqüência de reduções para transformar a fórmula numa fórmula na forma normal prenex é a seguinte:
-
-
-
---------------------------redução (8)
------------------------redução (1)
------------------------redução (12)
--------------------redução (14)
----------------redução (13)
----------------redução (2)
----------------redução (1)
----------------redução (2)
-
-