Tarea 4 - Diagramas Binarios de Decisión (BDD)

Para esta entrada construiremos diagramas binarios de decisión a partir de una expresión de lógica proposicional (que nosotros mismos inventamos).
La expresión proposicional que inventé para el desarrollo de esta tarea y su correspondiente tabla de verdad es la siguiente:

 

El primer BDD construido a partir de la tabla de verdad obtenida se ve así:

A partir de este BDD inicial vemos que en todos los casos las salidas se repiten (parejas de 0's y de 1's) entonces primeramente convertiremos las parejas de salidas en una sola salida individual y enlazaremos las combinaciones de C a dicha salida individual, y quedaría de la siguiente manera:

Ahora, con el árbol anterior comenzaremos a reducirlo para así obtener nuestro ROBDD final.

Comenzaremos por organizar nuestras salidas para que sólo nos queden 0 y 1 y quedaría de la siguiente manera:

Y finalmente, podemos obsevar que en todas las combinaciones cuando a = 1 (línea continua) cualquier combinación de "b" y "c" nos da 1 siempre por lo que podemos minimizar el árbol enviando a = 1 hasta la salida 1. 

Ahora analizando cuando a = 0 (línea discontinua); para combinaciones de b = 0 (línea discontinua) cualquier combinación de "c" nos da 0, por lo que podemos minimizarlo enviando 

b = 0 directamente a la salida 0, mientras que cuando b = 1 (línea continua) cualquier combinación de "c" nos da 1 por lo que podemos minimizarlo enviando b = 1 directamente a la salida 1. Y así obtenemos el ROBDD final: