Problema 4.24 Lógica de predicados se pueden utilizar para contar dos gráficas separadas: encontrar una fórmula que es cierto en el uno, pero no en la otra. Considere las siguientes dos imágenes:

Dar una fórmula, y R para la relación, cierto en el lado izquierdo y falso a la derecha

Como vemos la imagen anterior se compone de flechas dirigidas lo que lo hace un grafo dirigido, estas flechas dirigidas son llamadas bordes.

En el libro viene una explicación la cual es la siguiente:

Nos dice que la imagen es un grafo dirigido y que las siguientes formulas son correctas para que lo representemos:

$\mathbf{ \exists x\exists yRxy}$

$\mathbf{\exists xRxx}$

$\mathbf{\rightharpoondown \forall x\exists yRxy}$

Como en este caso que el primer grafo la relación es reflexiba y seria $\mathbf{xRy}$ por eso es verdadera si existe por lo menos una x y una y.

Propiedad Transitiva

La cual se representa de la siguiente manera:

$\mathbf{xRy \wedge  yRz\rightarrow xRz}$

Referencia

Figura 1

Nos piden la relacion y en este caso la relaciòn es transitiva, ya que siempre hay flechas de x a y y de y a z.

Figura 2

Como vemos aquí no hay ninguna relación transitiva, por lo cual vamos a formular la relación con la transitiva para que el grafo 1 sea verdadero y el 2 sea falso.

¿Por que no usamos la simétrica ni la reflexiva?, no la usamos ya que los dos grafos tienen relación simétrica y reflexiva y no podríamos tener una formula que sea falsa para la segunda.

Formula:

$\mathbf{\exists x\exists y\exists z\left ( Rxy \wedge  Ryz \right )}$

$\mathbf{\exists x\exists y\exists z\left ( Rxy \wedge  Ryz \right )}$ es verdadera si existe por lo menos una x,y y z que 

Entonces llegamos a la conclusión que es verdadera para la izquierda y falsa para la derecha ya que la derecha no tiene relación transitiva