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 nos dá a fórmula de primeira ordem
\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 o modelo M'=(A',R') com
A'=\{a,b,c\}, \quad R'=\{(b,c),\,(a,b),\,(c,b)\}.
Precisamos verificar se M'\models\varphi, ou seja, se para todo par (x,y) no domínio existe um z que faz a implicação verdadeira.

Passo 2

Repare que numa implicação P\rightarrow Q ela é verdadeira sempre que P for falsa, e quando P for verdadeira precisamos que Q seja verdadeira. Logo, para satisfazer
\forall x\,\forall y\,\exists z\bigl(R(x,y)\rightarrow R(y,z)\bigr)
basta mostrar que sempre que (x,y)\in R' existe algum z com (y,z)\in R'. Se (x,y)\notin R', qualquer z serve porque a implicação será verdadeira automaticamente.

Passo 3

Os pares de R' são exatamente
(b,c),\quad (a,b),\quad (c,b).

Passo 4

Analisamos cada caso:
– Para (x,y)=(b,c), temos R'(b,c). Precisamos de z com (c,z)\in R'. Olhando R', (c,b)\in R', então basta escolher z=b.
– Para (x,y)=(a,b), temos R'(a,b). Precisamos de z com (b,z)\in R'. Como (b,c)\in R', z=c funciona.
– Para (x,y)=(c,b), temos R'(c,b). De novo, para y=b basta z=c, pois (b,c)\in R'.
Em todos os casos em que R'(x,y) é verdadeiro, encontramos z tal que R'(y,z) é verdadeiro.

Passo 5

Como nos demais pares (x,y)\notin R' a implicação é verdadeira sem restrição em z, concluímos que para todo x,y existe um z satisfazendo a implicação.

Resposta

Sim, M'\vDash \varphi.

Exercícios relacionados