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
é equivalente a
, temos:
Passo 3
Agora usamos a equivalência de distribuição do quantificador existencial sobre disjunção. Em geral
.
Aplicando aqui:
Aplicando aqui:
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).
\lnot(\forall x)p(x) \lor (\exists x)r(x)
\equiv
(\exists x)\lnot 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.
o bicondicional entre eles é sempre verdadeiro. Portanto a fórmula é válida em toda interpretação.
Resposta
A fórmula é válida (é uma tautologia).