Diagrama de decisión binario

Para ésta entrada, se nos encargo realizar una actividad, que nos pedían realizar una expresión lógica y de ahí sacaramos un árbol de decisión binario (BDD), ya una vez tenido éste, se buscaría reducirse (RBB).

Introducción:

Definiendo un poquito ésto, encontramos que el Diagrama de decisión binario, nos sirve para representar una expresión lógica y ésta la vemos representada en un árbol binario.

Expresión booleana:

-((a^-b)V(c^a)) ^ -(-b^c)

Tabla de Verdad:

Árbol binario de decisión:

En mi caso, mi árbol de decisioón binario quedo de la siguiente manera:

Las flechas punteadas son falso y las normales verdadero.

Tips:

Podemos notar, que al momento de realizar ésto, los valores resultantes de la tabla, son los mismos de los nodos terminales (0 y 1).


Una vez teniendo el árbol, podemos proseguir a reducirlo, donde buscamos aplicar las siguientes reglas: quitar los últimos nodos que se repitan, dejando un solo nodo en 0 y 1, quitar los nodos repetidos y quitar auellos nodos que coincidan sus hijos.

Con ésto mi árbol se puede reducir de la siguiente forma:

En la cuál quite varios nodos terminales que apuntaban a uno mismo (en éste caso cero), así que los uní a uno solo, pero podemos ver que nuestro árbol aún puede ser más reducido, ya que unos nodos apuntan al mismo.

Referencia:

http://es.wikipedia.org/wiki/Diagrama_de_decisi%C3%B3n_binario 
http://ia2.freeiz.com/tema10.html