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

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

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

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

PDAG, BDD, и NNF

Сваки бинарни дијаграм одлуке (BDD) и свака негацијска нормална форма (NNF) су такође исказни усмерени ациклични граф са одређеним својствима. Следеће слике представљају Булову финкцију ${\displaystyle 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.