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

Passo 1

Este exercício pede para mostrar que as fórmulas
H=(\forall x) p(x) e G=(\forall y) p(y) são equivalentes. O conteúdo aqui é lógica de predicados de primeiro ordem e, em particular, a renomeação de variáveis ligadas (ou α-conversão). Vamos usar o fato de que renomear uma variável ligada não altera o significado da fórmula.

Passo 2

Em lógica de predicados, duas fórmulas são logicamente equivalentes se, para toda interpretação e avaliação de variáveis, elas têm o mesmo valor de verdade. Além disso, existe uma regra chamada α-conversão que diz que podemos renomear uma variável ligada sem mudar o valor de verdade da fórmula, contanto que o novo nome não apareça em outra parte que entre em conflito.

Passo 3

Para mostrar H⇒G, suponha que H seja verdadeira. Isso significa que para todo x vale p(x). Queremos ver que G é verdadeira, ou seja, para todo y vale p(y). Mas isso é imediato: se para todo x vale p(x), então podemos escolher y no lugar de x e concluir p(y). Logo, G segue de H.

Passo 4

De modo análogo, para mostrar G⇒H, suponha que G seja verdadeira. Então para todo y vale p(y). Como o nome da variável ligada não importa, podemos pensar em y como um x; portanto, concluímos que para todo x vale p(x), ou seja, H. Assim, H e G têm exatamente o mesmo conteúdo semântico.

Passo 5

Portanto, pelas demonstrações H⇒G e G⇒H (ou simplesmente pela α-conversão de variáveis ligadas), concluímos que as fórmulas H e G são equivalentes.

Resposta

As fórmulas são equivalentes por renomeação de variável ligada (α-conversão): H⇒G e G⇒H.

Exercícios relacionados