Verifique se as fórmulas a seguir são tautologias ou não:
H=(forall x)(exists y) p(x, y) (exists y) p(y, y)

Passo 1

O enunciado apresenta a fórmula de lógica de predicados H = (forall x)(exists y),p(x,y) (exists y),p(y,y) e pede para verificar se ela é uma tautologia (válida em toda interpretação).

Passo 2

Em lógica de predicados, chamar uma fórmula de tautologia (ou válida) significa que ela vale em todo domínio e para toda interpretação de p. Para mostrar que H não é válida, basta encontrar um modelo (contraexemplo) em que o antecedente seja verdadeiro e o consequente seja falso.

Passo 3

Considere o domínio D = a,b e a interpretação de p dada por
p = (a,b),,(b,a)
Nesse modelo, para cada xin D existe um yin D tal que p(x,y): se x=a escolhemos y=b, e se x=b escolhemos y=a. Portanto o antecedente (forall x)(exists y),p(x,y) é verdadeiro.

Passo 4

Agora, não existe yin D tal que p(y,y), pois nem p(a,a) nem p(b,b) pertencem à interpretação de p. Logo o consequente (exists y),p(y,y) é falso.

Passo 5

Como encontramos um modelo onde o antecedente é verdadeiro e o consequente é falso, a implicação H falha nessa interpretação. Logo, H não é uma tautologia.

Resposta

H não é uma tautologia.

Exercícios relacionados