Исказни усмерени ациклични граф

Исказни усмерени ациклични граф je структура података која се користи да представи Булову функцију. Булова функција може бити представљена као коренски, усмерени ациклични граф у следећој форми:

• Листови су означени са $\top$ (тачно), $\bot$ (нетачно), или Буловом променљивом.
• Чворови који нису листови могу бити $\bigtriangleup$ (логичко И), $\bigtriangledown$ (логичко ИЛИ) и $\Diamond$ (логичко НЕ).
• $\bigtriangleup$- и $\bigtriangledown$-чворови имају барем једно дете.
• $\Diamond$-чворови имају тачно једно дете.

Листови означени са $\top$ ($\bot$) представљају константу Булове функције која је увек једнака 1 (0). Лист означен Буловом променљивом $x$ се тумачи као задавање $x=1$, то јест, представља Булову функцију која је једнака 1 ако и само ако је $x=1$. Булова функција представљена са $\bigtriangleup$-чвором је она која је једнака 1, ако и само ако је Булова функција све његове деце једнака 1. Слично, $\bigtriangledown$-чвор представља Булову функцију која је једнака 1, ако и само ако је Булова функција бар једног детета једнака 1. Коначно, $\Diamond$-чвор представља комплементарну Булову функцију свог детета, то јест једнака је 1, ако и само ако је Булова функција његовог детета једнака 0.

PDAG, BDD, и NNF

Сваки бинарни дијаграм одлуке (BDD) и свака негацијска нормална форма (NNF) су такође исказни усмерени ациклични граф са одређеним својствима. Следеће слике представљају Булову финкцију $f(x1,x2,x3)=-x1*-x2*-x3+x1*x2+x2*x3$:

BDD за функцију f

PDAG за функцију f добијену из BDD

PDAG за функцију f

Види још

• Структуре података

Референце

• M. Wachter & R. Haenni, "Propositional DAGs: a New Graph-Based Language for Representing Boolean Functions", KR'06, 10th International Conference on Principles of Knowledge Representation and Reasoning, Lake District, UK, 2006.
• M. Wachter & R. Haenni, "Probabilistic Equivalence Checking with Propositional DAGs", Technical Report iam-2006-001, Institute of Computer Science and Applied Mathematics, University of Bern, Switzerland, 2006.
• M. Wachter, R. Haenni & J. Jonczy, "Reliability and Diagnostics of Modular Systems: a New Probabilistic Approach", DX'06, 18th International Workshop on Principles of Diagnosis, Peñaranda de Duero, Burgos, Spain, 2006.