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

Passo 1

O exercício pede para verificar se a fórmula (forall x),p(x) (exists x),p(x) é válida (tautologia) em lógica de predicados de primeira ordem, isto é, se em toda interpretação seu valor de verdade é verdadeiro.

Passo 2

Em lógica de predicados assume-se que o domínio de discurso D é não vazio. A fórmula (forall x),p(x) é verdadeira em uma interpretação se, para cada a in D, temos p(a) verdadeiro. A fórmula (exists x),p(x) é verdadeira se existe pelo menos um b in D tal que p(b) seja verdadeiro. A implicação F G só é falsa quando F é verdadeira e G é falsa.

Passo 3

Escolhemos uma interpretação genérica I com domínio Dneqemptyset. Suponha que Imodels (forall x),p(x), ou seja, todo ain D satisfaz p(a). Como D não é vazio, existe algum bin D, e daí Imodels p(b). Logo Imodels (exists x),p(x). Dessa forma, sempre que a parte antecedente (forall x),p(x) for verdadeira, a parte consequente (exists x),p(x) também será.

Passo 4

Como nossa interpretação I foi completamente arbitrária, concluímos que em toda interpretação (com domínio não vazio) a implicação é verdadeira. Portanto a fórmula é válida em lógica de predicados de primeira ordem.

Resposta

A fórmula (forall x),p(x) (exists x),p(x) é válida (tautologia).

Exercícios relacionados