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

O enunciado pede para verificar se a fórmula
(forall x)(p(x,a) (forall x)q(x,b)) rightarrow ((exists x)p(x,a) (forall x)q(x,b))
é uma tautologia em Lógica de Predicados, ou então exibir uma interpretação que a torne falsa. Vamos usar a equivalência conhecida entre quantificadores e conectivos para provar que ela vale em qualquer interpretação.

Passo 2

Primeiro, note que o (forall x)q(x,b) interno usa o mesmo símbolo de variável, mas podemos renomeá-lo para não confundir. Defina
B = (forall y)q(y,b)
então a fórmula fica
(forall x)(p(x,a) B) rightarrow ((exists x)p(x,a) B).

Passo 3

Agora usamos a equivalência proposicional e de quantificadores:
  1. p(x,a) B é equivalente a neg p(x,a) lor B.
  2. (forall x)(neg p(x,a) lor B) é equivalente a wed>=x(neg p(x,a) lor B).
  3. Isso equivale a negl(veex (p(x,a) land neg B)r), ou seja, neg (exists x)(p(x,a) land neg B).
  4. E neg (exists x)(p(x,a) land neg B) é exatamente neg(exists x)p(x,a) lor B, que por sua vez é a definição de (exists x)p(x,a) B.
    Portanto mostramos que
(forall x)(p(x,a) B) equiv ((exists x)p(x,a) B)
em qualquer interpretação.

Passo 4

Como escolhemos B = (forall y)q(y,b), acabamos de provar que ambos os lados da bicondicional são sempre equivalentes. Logo, a fórmula original é válida (uma tautologia) em Lógica de Predicados.

Resposta

A fórmula é válida em qualquer interpretação; trata-se de uma tautologia.

Exercícios relacionados