Gráfico acíclico dirigido proposicional
Un gráfico acíclico dirigido proposicional (PDAG) es una estructura de datos que se utiliza para representar una función booleana . Una función booleana se puede representar como un gráfico acíclico dirigido con raíz de la siguiente forma:
Las hojas etiquetadas con ( ) representan la función booleana constante que siempre se evalúa como 1 (0). Una hoja etiquetada con una variable booleana se interpreta como la asignación , es decir, representa la función booleana que se evalúa como 1 si y sólo si . La función booleana representada por un -nodo es la que da como resultado 1, si y solo si la función booleana de todos sus hijos da como resultado 1. De manera similar, un -nodo representa la función booleana que da como resultado 1, si y solo si la función booleana de todos sus hijos da como resultado 1. La función booleana de al menos un hijo se evalúa como 1. Finalmente, un nodo representa la función booleana complementaria de su hijo, es decir, el que se evalúa como 1, si y solo si la función booleana de su hijo se evalúa como 0.
Cada diagrama de decisión binario (BDD) y cada forma normal de negación (NNF) también son un PDAG con algunas propiedades particulares. Las siguientes imágenes representan la función booleana :
