Grafo acíclico dirigido proposicional

Un grafo acíclico dirigido proposicional (PDAG) es una estructura de datos que se utiliza para representar una función booleana . Una función booleana puede representarse como un grafo acíclico dirigido con raíz de la siguiente forma:

• Las hojas están etiquetadas con${\displaystyle \top }$(verdadero),${\displaystyle \bot }$(falso), o una variable booleana.
• Las plantas que no son hojas son${\displaystyle \bigtriangleup }$(y lógico),${\displaystyle \bigtriangledown }$(o lógico) y${\displaystyle \Diamond }$(negación lógica).
• ${\displaystyle \bigtriangleup }$- y${\displaystyle \bigtriangledown }$-los nodos tienen al menos un hijo.
• ${\displaystyle \Diamond }$-Los nodos tienen exactamente un hijo.

Hojas etiquetadas con${\displaystyle \top }$(${\displaystyle \bot }$) representan la función booleana constante que siempre se evalúa a 1 (0). Una hoja etiquetada con una variable booleana${\displaystyle x}$se interpreta como la asignación${\displaystyle x=1}$, es decir, representa la función booleana que se evalúa a 1 si y solo si${\displaystyle x=1}$. La función booleana representada por un${\displaystyle \bigtriangleup }$-nodo es aquel que se evalúa a 1, si y solo si la función booleana de todos sus hijos se evalúa a 1. De manera similar, un${\displaystyle \bigtriangledown }$-node representa la función booleana que se evalúa a 1, si y solo si la función booleana de al menos un hijo se evalúa a 1. Finalmente, un${\displaystyle \Diamond }$-node representa la función booleana complementaria de su hijo, es decir, la 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 binaria (BDD) y cada forma normal de negación (NNF) son también un PDAG con algunas propiedades particulares. Las siguientes imágenes representan la función booleana f(x1, x2, x3) = -x1 * -x2 * -x3 + x1 * x2 + x2 * x3:

• 
  BDD para la función f
• 
  PDAG para la función f obtenida del BDD
• 
  PDAG para la función f

• Estructura de datos
• Problema de satisfacibilidad booleana
• Proposición
• Circuito booleano

• M. Wachter y R. Haenni, "DAG proposicionales: un nuevo lenguaje basado en grafos para representar funciones booleanas", KR'06, 10.ª Conferencia Internacional sobre Principios de Representación del Conocimiento y Razonamiento, Lake District, Reino Unido, 2006.
• M. Wachter y R. Haenni, "Comprobación de equivalencia probabilística con DAG proposicionales", Informe técnico iam-2006-001, Instituto de Ciencias de la Computación y Matemáticas Aplicadas, Universidad de Berna, Suiza, 2006.
• M. Wachter, R. Haenni y J. Jonczy, "Fiabilidad y diagnóstico de sistemas modulares: un nuevo enfoque probabilístico", DX'06, 18º Taller Internacional sobre Principios de Diagnóstico, Peñaranda de Duero, Burgos, España, 2006.