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.
(exists x)(p(x) q(x)) ((exists x) p(x) (exists x) q(x))

Passo 1

O enunciado pede para verificar se a fórmula
(exists x)(p(x) q(x)) ;; ((exists x)p(x) (exists x)q(x))
é válida em toda interpretação (isto é, uma tautologia de predicados) ou, caso não seja, encontrar uma interpretação que a torne falsa. Para ver se a fórmula é válida, lembramos que provar validade equivale a mostrar que em toda interpretação ela vale “verdadeiro”. Se conseguirmos achar uma interpretação em que o valor da parte antecedente seja verdadeiro e o da parte consequente seja falso, teremos um contraexemplo e a fórmula não será válida.

Passo 2

Reescrevemos p(x) q(x) como neg p(x) lor q(x). Então a fórmula fica
(exists x)(neg p(x) lor q(x)) ;; ((exists x)p(x) (exists x)q(x))
Para que uma implicação A B seja falsa basta ter A verdadeiro e B falso.

Passo 3

Escolhemos uma interpretação com domínio D = a,b e definimos as avaliações de p e q assim:
p(a) = V, p(b) = F
q(a) = F, q(b) = F.

Passo 4

Verificamos a verdade de cada parte:
  1. (exists x)(neg p(x) lor q(x)) é verdadeiro porque em x = b temos neg p(b) lor q(b) = neg F lor F = V. Logo existe um elemento que satisfaz neg p(x) lor q(x).
  2. (exists x)p(x) é verdadeiro pois em x = a temos p(a) = V.
  3. (exists x)q(x) é falso porque para ambos x=a e x=b, q(x)=F.

Passo 5

Como (exists x)p(x) é verdadeiro e (exists x)q(x) é falso, a implicação (exists x)p(x) (exists x)q(x)) é falsa. Assim, o antecedente da fórmula geral vale V e o consequente vale F, tornando toda a fórmula falsa nessa interpretação.

Resposta

A fórmula não é válida. Contraexemplo: domine D=a,b, com p(a)=V,p(b)=F e q(a)=F,q(b)=F, faz a fórmula valer falsa.

Exercícios relacionados