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

Resumo do enunciado: Temos a fórmula de lógica de predicados

e queremos mostrar que ela é uma tautologia (válida em toda interpretação). Vamos usar equivalências lógicas para provar isso.

Passo 2

Começamos simplificando o primeiro membro da bicondicional. Lembrando que A B é equivalente a lnot A lor B, temos:

Passo 3

Agora usamos a equivalência de distribuição do quantificador existencial sobre disjunção. Em geral
exists x (Q(x) lor R(x)) equiv (exists x)Q(x) lor (exists x)R(x).
Aplicando aqui:
(exists x)(lnot p(x) lor r(x)) equiv (exists x)lnot p(x) lor (exists x)r(x)

Passo 4

Agora simplificamos o segundo membro. Primeiro, escrevemos
$$(\forall x)p(x) \rightarrow (\exists x)r(x) \equiv \lnot(\forall x)p(x) \lor (\exists x)r(x).
(forall x)p(x) (exists x)r(x) equiv lnot(forall x)p(x) lor (exists x)r(x)
\lnot(\forall x)p(x) \lor (\exists x)r(x)
\equiv
(\exists x)\lnot p(x) \lor (\exists x)r(x).
$$

Passo 5

Como ambos os lados foram reduzidos à mesma forma
$$(\exists x)\lnot p(x) \lor (\exists x)r(x),
$$
o bicondicional entre eles é sempre verdadeiro. Portanto a fórmula é válida em toda interpretação.

Resposta

A fórmula é válida (é uma tautologia).

Exercícios relacionados