Grafo 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 están etiquetadas con (verdadero), (falso) o una variable booleana. ${\displaystyle \top }$ ${\displaystyle \bot }$
• Las no hojas son (lógico y), (lógico o) y (lógico no). ${\displaystyle \bigtriangleup }$ ${\displaystyle \bigtriangledown }$ ${\displaystyle \Diamond }$
• ${\displaystyle \bigtriangleup }$- y -los nodos tienen al menos un hijo. ${\displaystyle \bigtriangledown }$
• ${\displaystyle \Diamond }$-Los nodos tienen exactamente un hijo.

Las hojas etiquetadas con ( ) representan la función booleana constante que siempre evalúa a 1 (0). Una hoja etiquetada con una variable booleana se interpreta como la asignación , es decir, representa la función booleana que evalúa a 1 si y solo si . La función booleana representada por un -nodo es la que evalúa a 1, si y solo si la función booleana de todos sus hijos evalúa a 1. De manera similar, un -nodo representa la función booleana que evalúa a 1, si y solo si la función booleana de al menos un hijo evalúa a 1. Finalmente, un -nodo representa la función booleana complementaria de su hijo, es decir, la que evalúa a 1, si y solo si la función booleana de su hijo evalúa a 0. ${\displaystyle \top }$ ${\displaystyle \bot }$ ${\displaystyle x}$ ${\displaystyle x=1}$ ${\displaystyle x=1}$ ${\displaystyle \bigtriangleup }$ ${\displaystyle \bigtriangledown }$ ${\displaystyle \Diamond }$

PDAG, BDD y NNF

Todo diagrama de decisión binario (BDD) y toda forma normal de negación (NNF) también son PDAG con algunas propiedades particulares. Las siguientes imágenes representan la función booleana : ${\displaystyle f(x1,x2,x3)=-x1*-x2*-x3+x1*x2+x2*x3}$

Véase también

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

Referencias

• M. Wachter y R. Haenni, "DAG proposicionales: un nuevo lenguaje basado en gráficos para representar funciones booleanas", KR'06, 10ª Conferencia internacional sobre principios de representación y razonamiento del conocimiento, Distrito de los Lagos, 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.