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

Passo 1

O enunciado pede para encontrar modelos (interpretações) e atribuições de variáveis livres que façam a fórmula
(∀x)(∀x) p(x,y) → (∃y) q(z) ser verdadeira e outros que a façam falsa. O conteúdo aqui é a semântica de Lógica de Predicados de 1ª ordem, usando as regras de interpretação de quantificadores e de implicação.

Passo 2

Primeiro, vamos simplificar o entendimento da fórmula. Note que repetir ∀x duas vezes é redundante, pois
(∀x)(∀x) p(x,y)
é equivalente a
(∀x) p(x,y).
Além disso, no consequente temos (∃y) q(z): o quantificador ∃y não aparece em q(z), logo esse trecho é equivalente a q(z).
Portanto a fórmula fica logicamente equivalente a
(∀x) p(x,y) → q(z).
Pela semântica de →, ela é verdadeira exatamente quando ou o antecedente é falso ou o consequente é verdadeiro.

Passo 3

Para construir um modelo que torne a fórmula verdadeira, basta fazer com que (∀x) p(x,y) seja falso, pois então a implicação será verdadeira independentemente de q(z). Por exemplo, consideremos a interpretação M₁ definida por:
– Domínio D = {a}
– p^M₁ = ∅ (ou seja, p(x,y) é sempre falso)
– q^M₁ = ∅ (q(x) também sempre falso)
E a atribuição de variáveis livres s₁ tal que s₁(y)=a e s₁(z)=a.
Avaliando:
(∀x) p(x,y) sob s₁ é falso (não há nenhum par em p^M₁),
então toda a implicação vale verdadeiro.

Passo 4

Para construir um modelo que torne a fórmula falsa, precisamos que o antecedente seja verdadeiro e o consequente seja falso. Então escolhemos um modelo M₂ onde p é sempre verdadeiro e q é sempre falso. Por exemplo:
– Domínio D = {a}
– p^M₂ = D×D = {(a,a)} (p(x,y) sempre verdadeiro)
– q^M₂ = ∅ (q(x) sempre falso)
E atribuição s₂ com s₂(y)=a e s₂(z)=a.
Então:
(∀x) p(x,y) sob s₂ é verdadeiro (p(a,a) está em p^M₂),
mas q(z) = q(a) é falso,
logo a implicação verdadeira → falso resulta em falso.

Passo 5

Essas duas interpretações mostram como a mesma fórmula pode ser satisfeita (modelo M₁) ou não (modelo M₂), dependendo da extensão de p e q e da atribuição de y e z.

Resposta

Interpretação que faz a fórmula verdadeira:
D={a}, p^M=∅, q^M=∅, com y↦a, z↦a.
Interpretação que faz a fórmula falsa:
D={a}, p^M=D×D, q^M=∅, com y↦a, z↦a.

Exercícios relacionados