Considere a sentença \varphi=\forall \mathbf{x} \forall \mathbf{y} \exists \mathbf{z}(\mathbf{R}(\mathbf{x}, \mathbf{y}) \rightarrow \mathbf{R}(\mathbf{y}, \mathbf{z})), onde \mathbf{R} é um símbolo de predicado com dois argumentos.
Seja A^{\prime}=\{a, b, c\} e R^{\prime}=\{(b, c),(a, b),(c, b)\}. Temos M^{\prime} \vDash \varphi ? Justifique sua resposta, qualquer que seja ela

Passo 1

O enunciado dá a sentença
\varphi = \forall \mathbf{x}\,\forall \mathbf{y}\,\exists \mathbf{z}\,\bigl(\mathbf{R}(\mathbf{x},\mathbf{y}) \rightarrow \mathbf{R}(\mathbf{y},\mathbf{z})\bigr)
e a estrutura M'=(A',R') com
A'=\{a,b,c\}, \quad R'=\{(b,c),\,(a,b),\,(c,b)\}.
Precisamos verificar se M'\models\varphi, isto é, se para todo x,y\in A' existe z\in A' que torna verdadeira a fórmula interna.

Passo 2

Repare que uma implicação p\rightarrow q é verdadeira sempre que p for falsa. Logo, se \mathbf{R}(x,y) for falsa, qualquer escolha de z satisfaz
\mathbf{R}(x,y)\;\rightarrow\;\mathbf{R}(y,z).
Portanto só precisamos checar os pares (x,y) para os quais \mathbf{R}(x,y) é verdadeira em R'.

Passo 3

Os únicos pares (x,y)\in A'\times A' com \mathbf{R}(x,y) verdadeira são
(a,b),\quad (b,c),\quad (c,b).

Passo 4

Para cada um desses pares encontramos um z tal que \mathbf{R}(y,z) seja verdadeira:
  • Em (a,b), temos y=b e (b,c)\in R', então escolhemos z=c.
  • Em (b,c), temos y=c e (c,b)\in R', então escolhemos z=b.
  • Em (c,b), temos y=b e (b,c)\in R', então escolhemos z=c.
Em todos esses casos existe z\in A' com \mathbf{R}(y,z) verdadeira.

Passo 5

Nos demais pares de (x,y), como \mathbf{R}(x,y) é falsa, a implicação \mathbf{R}(x,y)\rightarrow\mathbf{R}(y,z) é satisfeita para qualquer z. Assim, para todo x,y existe um z que faz verdadeira a subfórmula, e portanto
M'\models \varphi.

Resposta

Sim, M'\vDash \varphi.

Exercícios relacionados