Iskazni usmereni aciklični graf

Iskazni usmereni aciklični graf je struktura podataka koja se koristi da predstavi Bulovu funkciju. Bulova funkcija može biti predstavljena kao korenski, usmereni aciklični graf u sledećoj formi:

• Listovi su označeni sa $\top$ (tačno), $\bot$ (netačno), ili Bulovom promenljivom.
• Čvorovi koji nisu listovi mogu biti $\bigtriangleup$ (logičko I), $\bigtriangledown$ (logičko ILI) i $\Diamond$ (logičko NE).
• $\bigtriangleup$- i $\bigtriangledown$-čvorovi imaju barem jedno dete.
• $\Diamond$-čvorovi imaju tačno jedno dete.

Listovi označeni sa $\top$ ($\bot$) predstavljaju konstantu Bulove funkcije koja je uvek jednaka 1 (0). List označen Bulovom promenljivom $x$ se tumači kao zadavanje $x=1$, to jest, predstavlja Bulovu funkciju koja je jednaka 1 ako i samo ako je $x=1$. Bulova funkcija predstavljena sa $\bigtriangleup$-čvorom je ona koja je jednaka 1, ako i samo ako je Bulova funkcija sve njegove dece jednaka 1. Slično, $\bigtriangledown$-čvor predstavlja Bulovu funkciju koja je jednaka 1, ako i samo ako je Bulova funkcija bar jednog deteta jednaka 1. Konačno, $\Diamond$-čvor predstavlja komplementarnu Bulovu funkciju svog deteta, to jest jednaka je 1, ako i samo ako je Bulova funkcija njegovog deteta jednaka 0.

PDAG, BDD, i NNF

Svaki binarni dijagram odluke (BDD) i svaka negacijska normalna forma (NNF) su takođe iskazni usmereni aciklični graf sa određenim svojstvima. Sledeće slike predstavljaju Bulovu finkciju $f(x1,x2,x3)=-x1*-x2*-x3+x1*x2+x2*x3$:

BDD za funkciju f

PDAG za funkciju f dobijenu iz BDD

PDAG za funkciju f

Vidi još

• Strukture podataka

Reference

• 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.