Demonstre que as fórmulas H e G a seguir são equivalentes:
H=(forall x)(forall x) p(x), G=(forall x) p(x)

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 (forall x)(forall x)p(x) com a mesma variável. Pela α-conversão podemos renomear o quantificador interno para y, obtendo:
(forall x)(forall y)p(y)

Passo 3

Na expressão (forall x)(forall y)p(y) o quantificador externo forall x é redundante porque p(y) não depende de x. Então podemos eliminá-lo (idempotência do forall), ficando com:
(forall y)p(y)

Passo 4

Basta renomear y para x para chegar em G:
(forall x)p(x)

Passo 5

Para mostrar a implicação inversa, partimos de (forall x)p(x). Por eliminação de forall obtemos um termo arbitrário t com p(t). Em seguida, aplicamos introdução de forall duas vezes (primeiro em t como y, depois em t como x) e reconstruímos (forall x)(forall x)p(x), que é H.

Resposta

As fórmulas (forall x)(forall x)p(x) e (forall x)p(x) são logicamente equivalentes.

Exercícios relacionados