domingo, 2 de septiembre de 2012

Tarea 4:


 1-. Inventen una expresión Booleana.                   
           Usando por mínimo 3 variables y 4 conectivos básicos.
2-. Construyan y dibujen su BDD.
3-. Reduzcan el BDD resultante a un ROBDD.

4-. Dibujen el ROBDD resultante.


1-. Inventen una expresión Booleana.  

(((p^r)^(p|q))|^((¬r)|(p^q)))^¬q


Como vemos nuestra expresión Booleana tiene tres variables y cuenta con los 4 conectivos que son:
¬ : Negación
| = conjunción
^ = disyunción
 = Implicación


Después realizamos la tabla de verdad de la expresión:




Después realice el árbol binario de desición:

En el arbol la linea gris es 1 y la linea gris punteada es 0.




2-. Construyan y dibujen su BDD(Binary Decisión Diagram).

Para poder construir un Diagrama Binario de Desición se toma en cuenta:

1. Quitar los nodos terminales repetidos: Dejamos un solo nodo 0 y 1
2. Quitar los nodos no terminales repetidos (coinciden la variable y los hijos)
3. Quitar tests redundantes (coinciden los dos hijos)












3 y 4 -. Reduzcan el BDD resultante a un ROBDD y dibujarlo:

Cambie la posición de las variables como se muestra a r,q,p.

Como vemos se redujo a 4 nodos de los 5 que teniamos.

Referencias: DBB


1 comentario: