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

Passo 1

O enunciado pede para mostrar que as fórmulas H = (∀x)(∀y) p(x,y,z) e G = (∀y)(∀x) p(x,y,z) são equivalentes, ou seja, têm exatamente o mesmo conjunto de modelos. O conteúdo é a troca de quantificadores universais e vamos usar a propriedade de comutatividade de ∀.

Passo 2

Sabendo que quando temos dois quantificadores universais aninhados podemos reagrupar ou trocar a ordem sem alterar o significado, podemos escrever H de forma condensada:
H equiv (forall x,y),p(x,y,z)
Aplicando a mesma condensação a G, obtemos:
G equiv (forall y,x),p(x,y,z)

Passo 3

Agora usamos a regra de troca (comutatividade) dos quantificadores universais: para qualquer fórmula A,
(forall x,y),A(x,y) ;equiv; (forall y,x),A(x,y)

Passo 4

Aplicando essa regra a H, vemos que
(forall x,y),p(x,y,z) ;equiv; (forall y,x),p(x,y,z),
o que mostra que H é logicamente equivalente a G. Portanto, H e G têm o mesmo sentido.

Passo 5

Como consequência direta da comutatividade de ∀, H implica G e G implica H em qualquer interpretação, concluindo a equivalência lógica.

Resposta

As fórmulas H e G são logicamente equivalentes porque a ordem de quantificadores universais pode ser trocada sem alterar o significado: (∀x)(∀y)p(x,y,z) ≡ (∀y)(∀x)p(x,y,z).

Exercícios relacionados