martes, 4 de septiembre de 2012

Diagramas binarios de decisión



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:



Ahora se reduce el BDD resultante a un ROBDD:

 
Bibliografía:


1 comentario:

Elisa dijo...

Tu nodo C de extremo derecho falta un ramo. 9 pts.

Publicar un comentario