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 y 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 }$Los nodos - y - 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 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 se evalúa como 1, si y sólo si la función booleana de todos sus hijos se evalúa como 1. De manera similar, un nodo representa la función booleana que se evalúa como 1, si y sólo si 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, la que se evalúa como 1, si y sólo si la función booleana de su hijo se evalúa como 0. ${\displaystyle \top }$ ${\displaystyle \bot }$ ${\displaystyle x}$ ${\displaystyle x=1}$ ${\displaystyle x=1}$ ${\displaystyle \bigtriangleup }$ ${\displaystyle \bigtriangledown }$ ${\displaystyle \Diamond }$

PDAG, BDD y NNF

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 : ${\displaystyle f(x1,x2,x3)=-x1*-x2*-x3+x1*x2+x2*x3}$

Ver también

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

Referencias

• M. Wachter & R. Haenni, "DAG proposicionales: un nuevo lenguaje basado en gráficos para representar funciones booleanas", KR'06, Décima Conferencia Internacional sobre Principios de Razonamiento y Representación del Conocimiento, Lake District, Reino Unido, 2006.
• M. Wachter & R. Haenni, "Probabilistic Equivalence Checking with Propositional DAGs", 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 & J. Jonczy, "Fiabilidad y diagnóstico de sistemas modulares: un nuevo enfoque probabilístico", DX'06, XVIII Taller Internacional sobre Principios de Diagnóstico, Peñaranda de Duero, Burgos, España, 2006.