Diagrama de decisión binario

Para esta tarea se nos pidió lo siguiente

• Inventar una expresión Booleana (utilizando por mínimo 3 variables y 4 conectivos básicos).
• Construir y dibujar su BDD.
• Reducir el BDD resultante a un ROBDD.
• Dibujar el ROBDD resultante.

La expresión que invente es la siguiente:

(p ^ q) v (q -> r) ^ (p v ¬r)

Tabla de verdad:

Árbol binario de decisión:

Reducir a ROBDD

Para reducir un árbol binario de decisión a un Diagrama Binario de Decisión se tienen que considerar dos reglas:

1. Unir los isomorfismos (de igual forma) de subgrafos
2. Eliminar los nodos que sus dos hijos sean isomorfos.

Un DDB se encuentra reducido a DDBR (Diagrama de decisión binario reducido ordenado) si tiene las siguientes características:

• Unicidad: No existan dos nodos con el mismo símbolo proposicional ni con los mismos hijos izquierdo y derecho (nodos duplicados)
• No redundancia: No existan nodos variables idénticos.

Con esto se redujo el primer árbol que observamos en la imagen. :)