Verificação de Modelos

Os Amigos de Gandalf

Como verificar se uma interpretação é modelo de uma fórmula com quantificadores universais?

Sejam

• Constantes: $\mathcal{C}=\left\{\text{Gandalf}\right\}$,
• Relações: $\mathcal{R}=\left\{{\text{Amigo}}_2\right\}$,

Dada a seguinte interpretação daqueles símbolos em $\mathcal{U}=\left\{\text{A},\text{B},\text{C}\right\}$: $$\begin{array}{rl}{\text{Gandalf}}^v& =\text{A},\\ {\text{Amigo}}^v& =\left\{\left(\text{A},\text{A}\right),\left(\text{B},\text{A}\right),\left(\text{C},\text{A}\right)\right\}.\end{array}$$

Será que $v$ satisfaz "Nenhum dos amigos dos amigos de Gandalf é amigo dele"?

$$p:\forall x\forall y\underset{q\left(x,y\right)}{\underbrace{\text{Amigo}\left(x,\text{Gandalf}\right)\wedge \text{Amigo}\left(y,x\right)\to \neg \text{Amigo}\left(y,\text{Gandalf}\right)}}$$

Para verificar se $v\models p$ listam-se os todos possíveis valores de $x,y$:

$$\begin{array}{cccccc}{x}^v& y^v& {\text{Am}\left(x,\text{Ga}\right)}^v& {\text{Am}\left(x,y\right)}^v& \neg {\text{A.}\left(y,\text{Ga}\right)}^v& q{\left(x,y\right)}^v\\ \boxed{\text{A}}& \boxed{\text{A}}& \mathtt{v}& \mathtt{v}& \mathtt{f}& \boxed{\mathtt{f}}\\ \text{A}& \text{B}& \mathtt{f}& \mathtt{f}& \mathtt{f}& \mathtt{v}\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮\end{array}$$

O que a primeira linha mostra é que, fazendo $x^v=A$ e $y^v=A$ então a fórmula $q{\left(x,y\right)}^v$ é falsa: $$v\left[x\mapsto \text{A}\right]\left[y\mapsto \text{A}\right]/\models \text{Amigo}\left(x,\text{Gandalf}\right)\wedge \text{Amigo}\left(y,x\right)\to \neg \text{Amigo}\left(y,\text{Gandalf}\right).$$

Como uma das explicitações de $x,y$ não é verdade em $v$ então $$v/\models \forall x\forall y\text{Amigo}\left(x,\text{Gandalf}\right)\wedge \text{Amigo}\left(y,x\right)\to \neg \text{Amigo}\left(y,\text{Gandalf}\right).$$