Demonstre que as fórmulas
e
a seguir são equivalentes:
Passo 1
A questão pede para mostrar que as fórmulas H e G são equivalentes. Essas fórmulas envolvem quantificadores e negação, então vamos usar a lei de negação de quantificadores e também conversão α (renomeação de variáveis ligadas) para lidar com inconsistências de nome.
Passo 2
Escrevemos primeiro as fórmulas tal como estão:
Passo 3
Reparou que em G o quantificador está sobre y enquanto o predicado usa x, deixando x livre? Em lógica de predicados podemos renomear a variável ligada sem alterar o significado (conversão α). Então renomeamos y para x em G e ajustamos o predicado para p(x):
Passo 4
Agora provamos as duas implicações para garantir equivalência:
Para mostrar H G:
Assuma
Para mostrar H
Assuma
e tome um indivíduo arbitrário a. Suponha, por contradição, que p(a) seja verdadeiro. Então existiria x tal que p(x) (basta x=a), o que contradiz H. Logo devemos ter ¬p(a). Como a foi escolhido sem restrição, concluímos que
ou seja, G.
Passo 5
Para mostrar G
H:
Assuma
Assuma
e suponha, buscando contradição, que
Então existe um a com p(a). Mas G diz que para todo x temos ¬p(x), logo ¬p(a). Contradição. Portanto não pode existir x com p(x), isto é,
que é H.
Passo 6
Como mostramos H
G e G
H, concluímos que as duas fórmulas são logicamente equivalentes.