Identifique, raciocinando por absurdo, se as seguintes fórmulas são válidas ou inválidas:
PS.: as fórmulas inválidas devem ser associadas a uma estrutura que as falsifique.
\forall x \neg R x a \vee R b a

Passo 1

O enunciado pede para verificar se
\forall x\,\neg R(x,a)\;\vee\;R(b,a)
é válida, isto é, se vale em toda interpretação de primeiro-ordem. Para mostrar que ela é inválida, vamos raciocinar por absurdo: assumimos que ela valeria sempre e, em seguida, exibimos uma estrutura onde ela falha.

Passo 2

Observe que a fórmula é uma disjunção de dois componentes:
  1. \forall x\,\neg R(x,a)
  2. R(b,a)
    Para que a disjunção seja falsa em alguma estrutura, ambos os componentes devem ser falsos nessa estrutura.

Passo 3

Escrevendo as condições de falsidade:
  • \forall x\,\neg R(x,a) é falsa se, e somente se, existe algum c tal que R(c,a) seja verdadeiro.
  • R(b,a) é falsa se, na interpretação, o par (b,a) não pertence a R.

Passo 4

Definimos a seguinte estrutura \mathcal{M}=(D,\dots):
D = \{d_0,d_1\},\quad a^{\mathcal{M}} = d_1,\quad b^{\mathcal{M}} = d_0,
R^{\mathcal{M}} = \{(d_1,d_1)\}.
Nesta estrutura:
  • Existe c=d_1 tal que R(d_1,a^{\mathcal{M}})=R(d_1,d_1) é verdadeiro, logo \forall x\,\neg R(x,a) é falso.
  • Porém R(b^{\mathcal{M}},a^{\mathcal{M}})=R(d_0,d_1) é falso, pois (d_0,d_1)\notin R^{\mathcal{M}}.
    Consequentemente a disjunção
\forall x\,\neg R(x,a)\;\vee\;R(b,a)
é falsa em \mathcal{M}.

Resposta

A fórmula é inválida. Um contra-modelo é
D=\{d_{0},d_{1}\},\;a^{\mathcal{M}}=d_{1},\;b^{\mathcal{M}}=d_{0},\;R^{\mathcal{M}}=\{(d_{1},d_{1})\}.

Exercícios relacionados