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

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:
H = neg (exists x),p(x)
G = (forall y),neg p(x)

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):
G equiv (forall x),neg p(x)

Passo 4

Agora provamos as duas implicações para garantir equivalência:
Para mostrar H RightarrowG:
Assuma
H: neg (exists x),p(x)
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
(forall x),neg p(x)
ou seja, G.

Passo 5

Para mostrar G RightarrowH:
Assuma
G: (forall x),neg p(x)
e suponha, buscando contradição, que
(exists x),p(x)
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 é,
neg (exists x),p(x)
que é H.

Passo 6

Como mostramos H RightarrowG e G RightarrowH, concluímos que as duas fórmulas são logicamente equivalentes.

Resposta

neg (exists x),p(x)equiv (forall x),neg p(x)

Exercícios relacionados