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.
(forall x)(exists y) p(x, y) (exists y) p(y, y)

Passo 1

O enunciado pede para verificar se a fórmula
(forall x)(exists y),p(x,y) ;; (exists y),p(y,y)
é válida (verdadeira em toda interpretação) ou encontrar uma interpretação que a torne falsa. O conteúdo é lógica de predicados de primeira ordem e vamos precisar do conceito de interpretação e de contra-exemplo para validade.

Passo 2

Uma fórmula é válida se for verdadeira em toda interpretação (todo domínio e toda atribuição de verdade ao predicado). Para mostrar que não é válida, basta achar uma interpretação onde o antecedente seja verdadeiro e o consequente seja falso.
Considere uma interpretação com domínio
D = a, b,
e definimos a relação p por
p(a,b)=V, p(b,a)=V, p(a,a)=F, p(b,b)=F

Passo 3

Agora verificamos cada parte da fórmula nessa interpretação:
  • Para cada xin D:
    • se x=a, existe y=b com p(a,b)=V;
    • se x=b, existe y=a com p(b,a)=V.
      Logo, o antecedente
    (forall x)(exists y),p(x,y)
    é verdadeiro.
  • Mas não existe y tal que p(y,y) seja verdadeiro, pois p(a,a) e p(b,b) são falsas. Assim, o consequente
    (exists y),p(y,y)
    é falso.

Passo 4

Como conseguimos uma interpretação em que o antecedente é verdadeiro e o consequente é falso, a implicação inteira também é falsa nessa interpretação. Portanto, a fórmula não é verdadeira em toda interpretação, ou seja, não é válida.

Resposta

A fórmula não é válida. Um contra-exemplo é a interpretação com domínio a,b e p(a,b)=p(b,a)=V, p(a,a)=p(b,b)=F, em que o antecedente é verdadeiro e o consequente é falso.

Exercícios relacionados