Fueron
introducidos en los años 70 por Bryant para representar funciones booleanas de
forma compacta.
Sirven
para representar simbólicamente los estados del sistema.
Los
Diagramas de Decisión Binarios Ordenados (OBDDs) son representaciones canónicas
de las funciones.
Son
equivalentes a los autómatas de cadenas con alfabeto.
Un diagrama de decisión binario (DDB), tal como una forma normal de
negación (FNN) o un grafo
acíclico dirigido proposicional (GADP), es
una estructura de
datos utilizada para representar una función booleana. A un nivel más abstracto, los DDBs pueden ser
considerados como una representación comprimida de conjuntos o relaciones. A diferencia de otras representaciones comprimidas, las
operaciones se realizan directamente en los DDB, sin necesidad de
descomprimirlos.
Una función booleana puede
representarse como un grafo acíclico dirigido con raíz, el cual posee nodos
de decisión y dos nodos terminales llamados terminal-0 y terminal-1. Cada nodo
de decisión está etiquetado por una variable booleana (0 o 1) y tiene dos nodos hijos, llamados hijo
menor e hijo mayor. La arista que une un nodo con un hijo menor (mayor)
representa una asignación de la variable con el valor 0 (1).
Un DDB está ordenado si las distintas
variables aparecen en el mismo orden para todos los caminos desde la raíz.
Un
DDB es reducido si se
han aplicado las siguientes dos reglas a su grafo:
- Unir los isomorfismos de subgrafos.
- Eliminar los nodos cuyos dos hijos sean isomorfos.
Expresión Booleana
[(¬A → B) ˄ C] ↔ (A ˅ ¬B)
A partir de la tabla de verdad realice el árbol binario:
A partir de la tabla de verdad realice el árbol binario:
Ahora se reduce el BDD resultante a un ROBDD:
Bibliografía:
1 comentario:
Tu nodo C de extremo derecho falta un ramo. 9 pts.
Publicar un comentario