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

O enunciado pede para verificar se a fórmula de primeira ordem abaixo é válida (verdadeira em toda interpretação) ou então fornecer uma interpretação que a torne falsa:
(forall x)l(p(x,a) to (forall x),q(x,b)r) rightarrow l((exists x),p(x,b) to (forall x),q(x,a)r)
Estamos trabalhando com equivalências lógicas envolvendo quantificadores e queremos testar sua validade.

Passo 2

Repare que
forall xl(p(x,a) to Cr)
é equivalente à
(exists x),p(x,a) to C,
pois se existe algum x que satisfaça p(x,a), então de fato a condicional exige C; caso contrário, a implicação é trivialmente verdadeira em cada x.
No nosso caso, tomamos
Cequiv forall x,q(x,b),
e obtemos:
forall xl(p(x,a) to (forall x),q(x,b)r) equiv (exists x),p(x,a) to (forall x),q(x,b)

Passo 3

De forma análoga, o outro lado da equivalência se reescreve como
(exists x),p(x,b) to (forall x),q(x,a)
Portanto a fórmula original equivale a
(exists x),p(x,a) to (forall x),q(x,b) rightarrow (exists x),p(x,b) to (forall x),q(x,a)
Não há simetria obrigatória entre esses dois condicionalões, logo não devemos esperar validade geral.

Passo 4

Para construir um contra‐exemplo, basta tomar um domínio unitário e atribuir valores de forma a falsificar a equivalência. Seja a interpretação I definida por:
• Domínio D = d.
• Constrantes de nome a, b interpretam-se como d.
• Predicados avaliados em d:
p(d,a) verdadeiro,
p(d,b) falso,
q(d,a) verdadeiro,
q(d,b) falso.

Passo 5

Avaliação na interpretação I:
(exists x),p(x,a) é verdadeiro (pois p(d,a) é verdadeiro).
(forall x),q(x,b) é falso (pois q(d,b) é falso).
Logo o condicional
(exists x),p(x,a) to (forall x),q(x,b)
é VtoF = F
• Por outro lado, (exists x),p(x,b) é falso e (forall x),q(x,a) é verdadeiro, então
(exists x),p(x,b) to (forall x),q(x,a)
é (F\toV = V.]
Logo a equivalência avaliada fica F rightarrow V = F, contradizendo validade.

Passo 6

Portanto a fórmula não é válida em primeira ordem e a interpretação I acima a torna falsa.

Resposta

Não é válida. Por exemplo, na interpretação com domínio d em que p(d,a)=V, p(d,b)=F, q(d,a)=V, q(d,b)=F, a equivalência vale FrightarrowV=F

Exercícios relacionados