- 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 usaré es una sencilla:
(X1 ^ ¬X2) v (X3 ^ ¬X1) ^ (X2 v X3)
Para crear el árbol binario de decisión, primeramente hice la tabla de verdad de dicha expresión, que es la siguiente:
A partir de la tabla de verdad, hice el árbol binario de la siguiente manera:
Éste es un árbol binario de decisión(Binary Decisión Tree) y para reducir éste a un diagrama binario de decisión(Binary Decisión Diagram, BDD), debemos seguir dos reglas:
- Combinar todos los subgrafos isomórficos(que tengan la misma estructura).
- Eliminar cualquier nodo cuyos hijos sean isomórficos.
Entonces tomando en cuenta estas reglas, reduje el árbol binario de decisión a un diagrama binario de decisión, que quedo así:
Observando a fondo, la única reducción visible es en el caso de que X1 y X2 sea igual a 1,para cualquier valor de X3 daría 0, por lo tanto se reduce. Lo demás no fue posible reducirlo.
ROBDD
Para reducir el BDD a un ROBDD(Reduce Ordered Binary Decision Diagram), el PDF: "An Introduction to
Binary Decision Diagrams" por Henrik Reif Andersen, menciona tres condiciones para el orden y reducción:
- Las variables deben estar ordenadas
- Los nodos deben ser únicos
- Solo tests no redundantes deben estar presentes
(1) (2) (3)
Además menciona que el orden de las variables escogidas en la construcción de un ROBDD tiene un gran impacto en el tamaño de el ROBDD, por lo tanto, probaré un orden diferente al del BDD para observar si se reduce el tamaño.
ROBDD para el Orden X1, X3, X2
Utilizando el orden X1<X3<X2, el tamaño del árbol fue reducido de 6 nodos a simplemente 4.
Referencias:
Bien, 10 pts.
ResponderEliminar