Demonstre que as fórmulas
e
a seguir são equivalentes:
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 é
e G é
. 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
.
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 =
, vemos que podemos renomear a variável ligada
para
, pois
não ocorre livre em
. Assim obtemos
, que é exatamente G.
Passo 4
Para verificar semanticamente, considere qualquer estrutura
e atribuição
. Temos:
Substituindo a variável ligada por
Passo 5
Como a renomeação de variável ligada não altera o significado de uma fórmula e a semântica de
leva exatamente aos mesmos valores de verdade, concluímos que H e G são logicamente equivalentes.
Resposta
As fórmulas
e
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.