Propositionsriktad acyklisk graf

En propositionsriktad acyklisk graf (PDAG) är en datastruktur som används för att representera en boolesk funktion . En boolesk funktion kan representeras som en rotad, riktad acyklisk graf av följande form:

Blad är märkta med $\top$ (true), $\bot$ (false) eller en boolesk variabel.
Icke-blad är $\bigtriangleup$ (logiskt och), $\bigtriangledown$ (logiskt eller) och $\Diamond$ (logiskt inte).
$\bigtriangleup$ - och $\bigtriangledown$ -noder har minst ett underordnat.
$\Diamond$ -noder har exakt ett barn.

Blad märkta med $\top$ ( $\bot$ ) representerar den konstanta booleska funktionen som alltid utvärderas till 1 (0). Ett blad märkt med en boolesk variabel $x$ tolkas som tilldelningen $x=1$ , dvs det representerar den booleska funktionen som utvärderas till 1 om och endast om $x =1$ . Den booleska funktionen som representeras av en $\bigtriangleup$ -nod är den som utvärderas till 1, om och bara om den booleska funktionen för alla dess underordnade värden evalueras till 1. På samma sätt, en $\bigtriangledown$ -nod representerar den booleska funktionen som utvärderas till 1, om och endast om den booleska funktionen för minst ett barn utvärderas till 1. Slutligen representerar en ◊ {\ $\Diamond }$ -nod den komplementära booleska funktionen dess underordnade, dvs. den som utvärderar till 1, om och endast om den booleska funktionen för dess underordnade värde utvärderas till 0.

PDAG, BDD och NNF

Varje binärt beslutsdiagram (BDD) och varje negationsnormalform (NNF) är också en PDAG med vissa speciella egenskaper. Följande bilder representerar den booleska funktionen $f(x1,x2 ,x3)=-x1*-x2*-x3+x1*x2+x2*x3$ :

BDD för funktionen f

PDAG för funktionen f erhållen från BDD

PDAG för funktionen f

Se även

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, Storbritannien, 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, Spanien, 2006.