Algumas das fórmulas a seguir são válidas (tautologias), outras não. Para cada fórmula, demonstre se ela é válida ou defina uma interpretação que a interprete como sendo falsa.

Passo 1

Nesse exercício, a gente precisa verificar se a fórmula de LPO é uma tautologia (válida em toda interpretação) ou não. O conteúdo aqui é lógica de primeira ordem, mais especificamente avaliação de fórmulas em modelos: entender quantificadores, implicação e como construir um contra‐exemplo (interpretação) quando a fórmula não for válida.
Vamos reescrever a fórmula de forma mais clara, assumindo a precedência usual de quantificadores (eles só valem até o parêntese mais próximo) e da seta “→”:
(exists x)(forall y)l((q(x,y) wed>= q(y,x)) to (q(x,x) rightarrow q(y,y))r)
Assim temos uma sentença fechada (sem variáveis livres). A gente avalia se em todo modelo essa sentença é verdadeira (válida) ou encontra um modelo em que seja falsa.

Passo 2

Uma fórmula fechada da forma (exists x)phi(x) é falsa num modelo se, para todo elemento do domínio, a subfórmula phi(x) é falsa. E (forall y)psi(y) é falsa se existe algum y que torna psi(y) falsa. Além disso, Pto Q é falsa exatamente quando P é verdadeira e Q é falsa.

Passo 3

Para mostrar que a sentença não é válida, construímos um modelo A tal que ela dê falsa. Seja o domínio
D = a,b,
e definimos a interpretação de q como
q^A = (a,a),(a,b),(b,a)
Ou seja, q(x,y) é verdadeira sempre que (x,y) está nessa lista.

Passo 4

Agora avaliamos
(exists x)(forall y)((q(x,y)wed>= q(y,x))to(q(x,x)rightarrow q(y,y)))
Para cada candidato xin D:
- Se x=a, escolhemos y=b. Então q(a,b) e q(b,a) são verdadeiras, logo o antecedente q(a,b)wed>= q(b,a) é verdadeiro. Mas q(a,a) é verdadeiro e q(b,b) é falso, então q(a,a)rightarrow q(b,b) é falso. A implicação fica Vto F, que é falsa. Logo, (forall y)dots falha para x=a.
- Se x=b, fazemos o mesmo com y=a: o antecedente dá verdadeiro e o consequente dá falso, então a implicação é falsa. Logo (forall y)dots falha para x=b.
Em ambas as tentativas, não existe x que faça (forall y)dots verdadeira, então (exists x)(forall y)dots é falso no modelo A.

Passo 5

Concluímos que há pelo menos um modelo que torna a sentença falsa, portanto ela não é válida.

Resposta

A fórmula não é válida. Um contra‐exemplo é o modelo com domínio a,b e q^A=(a,a),(a,b),(b,a), em que a sentença avalia como falsa.

Exercícios relacionados