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)
-
-