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

Passo 1

Enunciado e conteúdo: queremos mostrar que as fórmulas
H = (exists x)(exists y),p(x,y,z)
e
G = (exists y)(exists x),p(x,y,z)
são logicamente equivalentes. O assunto aqui é permutação de quantificadores existenciais e equivalência lógica, usando a noção de testemunha para exists.

Passo 2

Mostrando que Himplies G: suponha que H seja verdadeira num modelo. Então existe um elemento a tal que
(exists y),p(a,y,z)
Ou seja, existe um b com p(a,b,z). A partir de p(a,b,z) podemos aplicar a regra de introdução existencial em x para obter
(exists x),p(x,b,z)
Em seguida, aplicamos introdução existencial em y e concluímos
(exists y)(exists x),p(x,y,z),
que é exatamente G.

Passo 3

Mostrando que Gimplies H: de forma análoga, suponha que G seja verdadeira. Então existe um b tal que
(exists x),p(x,b,z)
Logo existe um a com p(a,b,z). Introduzindo existencialmente primeiro em y e depois em x chegamos a
(exists x)(exists y),p(x,y,z),
que é H.

Passo 4

Conclusão: como mostramos ambas as implicações Himplies G e Gimplies H, as fórmulas são logicamente equivalentes pela definição de equivalência (duas fórmulas se equivalem se cada uma implica a outra).

Resposta

As fórmulas são equivalentes: (exists x)(exists y)p(x,y,z) equiv (exists y)(exists x)p(x,y,z).

Exercícios relacionados