Demonstre que as fórmulas
e
a seguir são equivalentes:
Passo 1
Estamos mostrando que as fórmulas H e G são equivalentes em lógica de predicados, usando α-conversão e a idempotência do quantificador universal.
Passo 2
Na fórmula H temos dois quantificadores
com a mesma variável. Pela α-conversão podemos renomear o quantificador interno para y, obtendo:
Passo 3
Na expressão
o quantificador externo
é redundante porque p(y) não depende de x. Então podemos eliminá-lo (idempotência do
), ficando com:
Passo 4
Basta renomear y para x para chegar em G:
Passo 5
Para mostrar a implicação inversa, partimos de
. Por eliminação de
obtemos um termo arbitrário t com
. Em seguida, aplicamos introdução de
duas vezes (primeiro em t como y, depois em t como x) e reconstruímos
, que é H.
Resposta
As fórmulas
e
são logicamente equivalentes.