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

Passo 1

O enunciado pede para checar se a fórmula H = (forall x),p(x) to (exists x),p(x) é tautologia ou não. O conteúdo envolve lógica de predicados de primeira ordem e precisamos usar a semântica de domínios e interpretações para testar validade.
Em lógica de predicados, dizemos que uma fórmula é tautologia (ou válida) se ela é verdadeira em toda interpretação possível, isto é, para qualquer domínio não vazio e qualquer atribuição de predicados e funções. Note que na semântica padrão de primeira ordem o domínio deve ser não vazio.

Passo 2

Vamos analisar H. Há dois casos: o antecedente (forall x)p(x) pode ser verdadeiro ou falso.

Passo 3

Se (forall x)p(x) for falso, então a implicação forall x p(x) to exists x p(x) é verdadeira independentemente do consequente, pois Fto Q é sempre V.
Se (forall x)p(x) for verdadeiro, então por definição temos que para todo elemento a do domínio p(a) é verdadeiro. Como o domínio não é vazio, existe pelo menos um elemento a tal que p(a) é verdadeiro, o que garante que (exists x)p(x) seja verdadeiro. Assim o consequente é V e, portanto, a implicação é V.

Passo 4

Como em ambos os casos a fórmula H avalia-se como verdadeira em qualquer interpretação com domínio não vazio, concluímos que H é uma fórmula válida (tautologia).

Resposta

A fórmula (forall x)p(x) to (exists x)p(x) é tautologia (válida) na semântica padrão de primeira ordem com domínio não vazio.

Exercícios relacionados