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

Passo 1

O exercício pede para mostrar que as fórmulas de lógica de predicados H e G são equivalentes, onde H é (exists x),p(x) e G é (exists y),p(y). O conteúdo da matéria é a equivalência de fórmulas por renomeação de variável ligada (alpha-conversão) e a semântica de exists.

Passo 2

Em lógica de primeira ordem, duas fórmulas são semanticamente equivalentes se têm o mesmo valor de verdade em toda interpretação e atribuição de variáveis. A renomeação de variável ligada (alpha-conversão) permite trocar o nome de variáveis quantificadas desde que a nova variável não apareça livre na fórmula original.

Passo 3

Aplicando alpha-conversão em H = (exists x),p(x), vemos que podemos renomear a variável ligada x para y, pois y não ocorre livre em p(x). Assim obtemos (exists y),p(y), que é exatamente G.

Passo 4

Para verificar semanticamente, considere qualquer estrutura M e atribuição s. Temos:
a se, e somente se, existe um elemento M no domínio de y tal que
(exists y),p(y)
Substituindo a variável ligada por , obtemos a condição idêntica para . Portanto, as duas fórmulas têm verdade condicional idêntica em toda interpretação.

Passo 5

Como a renomeação de variável ligada não altera o significado de uma fórmula e a semântica de exists leva exatamente aos mesmos valores de verdade, concluímos que H e G são logicamente equivalentes.

Resposta

As fórmulas (exists x),p(x) e (exists y),p(y) são equivalentes por alpha-conversão de variável ligada e porque ambas têm as mesmas condições de verdade em qualquer interpretação.

Exercícios relacionados