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 

Tarea 5: Lógica Predictiva 

En la tarea 5 seleccionamos un ejercicio del libro  Lean Symbolic Logic de Lewis Carroll, en este caso me toco el ejercicio numero 38:

No emperors are dentists 

All dentists are dreaded by children 

No emperors are dreaded by children. 

Traducción español:

No hay emperadores que sean dentistas

Todos los dentistas son temidos por los niños

No hay emperadores que sean temidos por los niños

No hay=Ningunos

E(x): emperors(emperadores)
D(x): dentists(dentistas)
N(x): dreaded by children(temidos por los niños)

Simbolos fundamentales que usaremos:

$\forall$: cuantificador universal (todos)
$\exists$ : cuantificador existencial (existe)

Sustituimos las palabras por símbolos:

• No emperors are dentists : $\mathbf{\rightharpoondown\exists (x) E(x)\to D(x)}$

• All dentists are dreaded by children: $\forall (x)D(x)\to N\left ( x \right ) $

• No emperors are dreaded by children: $\mathbf{\rightharpoondown\exists (x) E(x)\to N(x)}$

Conclusión:

Some people, dreaded by children, are not emperors

Someone dreaded by children, are not emperors: $\mathbf{\exists (x) N(x)\to \rightharpoondown E(x)}$




Referencias:

Link1
Link2
Link3
Link4

Tarea 4:


 1-. Inventen una expresión Booleana.                   
           Usando por mínimo 3 variables y 4 conectivos básicos.
2-. Construyan y dibujen su BDD.
3-. Reduzcan el BDD resultante a un ROBDD.

4-. Dibujen el ROBDD resultante.

1-. Inventen una expresión Booleana.  

(((p^r)^(p|q))|^((¬r)|(p^q)))^¬q

Como vemos nuestra expresión Booleana tiene tres variables y cuenta con los 4 conectivos que son:
¬ : Negación
| = conjunción
^ = disyunción
→ = Implicación


Después realizamos la tabla de verdad de la expresión:

Después realice el árbol binario de desición:

En el arbol la linea gris es 1 y la linea gris punteada es 0.

2-. Construyan y dibujen su BDD(Binary Decisión Diagram).

Para poder construir un Diagrama Binario de Desición se toma en cuenta:

1. Quitar los nodos terminales repetidos: Dejamos un solo nodo 0 y 1
2. Quitar los nodos no terminales repetidos (coinciden la variable y los hijos)

3. Quitar tests redundantes (coinciden los dos hijos)

3 y 4 -. Reduzcan el BDD resultante a un ROBDD y dibujarlo:

Cambie la posición de las variables como se muestra a r,q,p.

Como vemos se redujo a 4 nodos de los 5 que teniamos.

Referencias: DBB