domingo, 2 de septiembre de 2012

[VVS] 4. Diagramas binarios de decisión

"Este tipo de diagramas sirven para representar simbólicamente los estados del sistema y las funciones booleanas de forma compacta"

Instrucciones

La tarea 4 consiste en realizar lo siguiente:
  • Inventar una funció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.

Expresion

[ ( A ∧ B ) ∧ ¬C ] ∨ ¬B

Tabla de Verdad


ABC(A ∧ B)¬C((A ∧ B) ∧ ¬C)¬B(((A ∧ B) ∧ ¬C ) ∨ ¬B
00001011
00100011
01001000
01100000
10001011
10100011
11011101
11110000

Árbol de Decisión

Con la expresión anterior formamos el siguiente diagrama:



Después procedemos con la reducción, eligiendo aquellas hojas que terminan en el mismo valor y fusionandolas en una sola, y tomando también aquellas ramas con la misma estructura y fusionandolas en una sola:

[1]

 [2]

Y ésta es la máxima reducción que logramos con el orden actual de las variables.
[3]

Referencias:

1 comentario: