Es una estructura de datos utilizada para representar una función booleana. Estos pueden ser considerados como una representación comprimida de conjuntos o relaciones, donde las operaciones se realizan directamente en los diagramas, sin necesidad de descomprimirlos.
Mi Proposición
Para esta tarea nuestro trabajo fue construir una expresión booleana con al menos tres variables y cuatro conectivos lógicos, para hacer su diagrama de decisión binario y después minimizar el mismo. La expresión que escogí fue la siguiente:
(A→B)^(A+¬B+¬C)Para construir el BDD(Binary desition Diagram) me base en el PDF de la liga de referencias, donde se muestran el método en unos pasos simples de comprender.
Para realizar el dibujo utilice OpenOffice y el método fue el siguiente:
- (0) Primero construí una tabla de verdad con la expresión elegida que me sirvió como base para construir el BDD inicial.
- (1) Después se remueven terminales duplicadas.
- (2) Después se unen los nodos duplicados.
- (3) Se remueven los nodos redundantes.
^ = conjuncion + = disyuncion → = condicional ¬ = negacion (A→B)^(A+¬B+¬C) ABC F ----- 000 1 001 1 010 1 011 0 100 0 101 0 110 1 111 1
Mi BDD
Las lineas punteadas y grises representan caminos para los cuales el átomo es "Falso" y las lineas continuas y negras representan los caminos para los cuales el átomo es "Verdadero"
Una vez obtenido el diagrama reducido me fue fácil construir una expresión lógicamente equivalente a la primera de la forma DNF(disjunctive normal form) la cual es la siguiente:
AB+¬A¬B+¬AB¬CSu tabla de verdad:
ABC F ----- 000 1 001 1 010 1 011 0 100 0 101 0 110 1 111 1
Referencias:
Excelente. 10 pts.
ResponderBorrar