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

Neste exercício, temos a fórmula (forall x)(p(x) q(x)) rightarrow ((exists x)p(x) (forall x)q(x)). O conteúdo é lógica de predicados de primeira ordem, e vamos precisar dos conceitos de validade, modelos e interpretação de fórmulas.

Passo 2

Para mostrar que a fórmula não é válida, basta encontrar um modelo M onde ela seja falsa. Lembrando que uma fórmula é válida se for verdadeira em todo modelo.

Passo 3

Definimos um modelo M com domínio D=1,2 e extensões de predicados
p^M = 1,
q^M = 1
Agora vamos verificar o valor de verdade de cada lado da equivalência.

Passo 4

No modelo M, calculamos:
Para a subfórmula forall x(p(x) q(x)):
  • Para x=1, p(1) q(1) é T T, que vale V.
  • Para x=2, p(2) q(2) é F F, que vale V.
    Logo forall x(p(x) q(x)) é V.
    Para (exists x)p(x) (forall x)q(x):
  • exists x,p(x) é V (pois p(1) é V).
  • forall x,q(x) é F (pois q(2) é F).
    Então a implicação é V F, que vale F.
    Assim, os lados da equivalência valem V e F, respectivamente, tornando a equivalência F.

Passo 5

Portanto, encontramos um contraexemplo em que a fórmula é falsa, mostrando que ela não é válida.

Resposta

A fórmula não é válida. Por exemplo, no modelo com domínio 1,2, p^M=1 e q^M=1, a equivalência assume valor falso.

Exercícios relacionados