Diagrama binario de decisión

La tarea correspondiente a esta semana es la siguiente:

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

La expresión booleana que yo inventé es:

ABCD + ¬A¬BCD + AB¬C¬D + AC¬B¬D

Como podemos apreciar cumple con los requisitos establecido, ya que tiene 4 variables y más de 6 conectivos básicos, en mi expresión "+" significa OR.

Primero cree una tabla de verdad:

Mi árbol binario queda de la siguiente manera, Líneas punteadas - - - quieren decir 0, y seguidas quieren decir 1:

El paso siguiente es hacer un BDD esto quiere decir Diagrama Binario de Decisión, en el que combinamos todos los subgrafos que sean iguales en uno solo y eliminar nodos cuyos hijos tengan la misma estructura, entonces queda de la siguiente manera, se reduce de 15 a 8 nodos:

Este fue el proceso que seguí, primero del nodo C derecho, abajo del B al lado derecho todos los números son ceros por eso se va esa C y redirecciono la línea de la B directo al 0, después el debajo de la B derecha, y C derecha tiene un nodo D izquierdo que también lo elimino ya que todo es 0 y se va a la cajita de 0. Lo mismo pasa con el nodo D que esta más a la izquierda todos sus números son 0 por eso lo elimino, enseguida se observa que debajo de las C que se encuentran debajo de la B izquierda hay dos D que tienen la misma combinación por lo que elimino una de las dos y redirecciono la línea al nodo correspondiente, después volvemos a tener dos nodos  con la misma combinación(0,1), entonces otra vez eliminamos uno de ellos y los juntamos en uno solo, para terminar solo dejamos una caja para 0 y otra para 1 y ahí juntamos todas las líneas. Esto se ve más claro en el gif siguiente:

Y ahora vemos el ROBDD(Reduce Ordered Binary Decision Diagram) para otros ordenes a ver que tanto se puede reducir, pero al parecer la forma más reducida de esta expresión fue la primera que obtuvimos ya que con varias combinaciones no logré bajarla de 8 nodos:

Orden C>D>A>B:

Orden C>D>B>A: 

Orden B>D>C>A:

Orden B>A>C>D:

Orden A>D>B>C:

Referencias:

Elisa Schaeffer
BDD