Se possível, determine interpretações que interpretem as fórmulas a seguir como verdadeiras e como falsas. Justifique suas respostas.
(forall x)(exists y) p(x, y, z) (exists y)(forall z) p(x, y, z)

Passo 1

O enunciado pede para encontrar duas interpretações (domínio e interpretação de p) de modo que a fórmula aberta
(forall x)(exists y),p(x,y,z) ;; (exists y)(forall z),p(x,y,z)
seja verdadeira em uma delas e falsa em outra. O conteúdo envolve Lógica de Primeira Ordem e o conceito de verdade em uma interpretação.

Passo 2

Lembrando que, como há variáveis livres (x em p(x,y,z) do segundo membro e z no primeiro), uma interpretação I torna a fórmula verdadeira se, sob toda atribuição de valores às variáveis livres, a implicação for satisfeita. Para fazê-la falsa, basta encontrar uma atribuição que torne o antecedente verdadeiro e o consequente falso.

Passo 3

Interpretação I1 que faz a fórmula verdadeira. Seja o domínio
D = a
e defina
p^I = emptyset
isto é, p(x,y,z) é sempre falsa. Então:
  • Antecedente: (forall x)(exists y)p(x,y,z) é falso (não existe y que satisfaça p(a,y,z)).
  • Como o antecedente é falso, toda implicação falso→(qualquer) é verdadeira. Logo a fórmula vale em toda atribuição.

Passo 4

Interpretação I2 que faz a fórmula falsa. Tome domínio com pelo menos dois elementos:
D = 0,1
E defina
$$
p^I = {(x,y,z)\in D^3 \mid y = z}\n$$
Então:
- Antecedente p^I = (x,y,z)in D^3 mid y = zn: para qualquer (forall x)(exists y)p(x,y,z) basta escolher xin D (valor livre de y = z) para ter z verdadeira; assim o antecedente é verdadeiro em toda atribuição.
- Consequente p(x,y,z): exige um (exists y)(forall z)p(x,y,z) que funcione para todo y, ou seja, um z igual a todos os y simultaneamente — impossível em domínios com mais de um elemento. Logo o consequente é falso em toda atribuição.
- Assim, sob qualquer atribuição, a implicação é z, ou seja, falsa.

Passo 5

Portanto, em I1 a fórmula é verdadeira e em I2 é falsa.

Resposta

Uma escolha que funciona é:
I1:
D = {a},
p^I = ∅.
→ O antecedente é falso, logo a implicação é verdadeira.
I2:
D = {0,1},
p^I = { (x,y,z) ∈ D^3 | y = z }.
→ O antecedente é verdadeiro (basta y = z) e o consequente é falso (não há y igual a todo z), logo a implicação é falsa.

Exercícios relacionados