Propozycyjny skierowany graf acykliczny

Graf acykliczny skierowany propozycyjnie (PDAG) to struktura danych używana do reprezentowania funkcji logicznej . Funkcję logiczną można przedstawić jako pierwiastkowy, skierowany graf acykliczny w następującej postaci:

Liście są oznaczone ${\ displaystyle \ top}$ (prawda), ${\ displaystyle \ bot}$ (fałsz) lub zmienną logiczną.
Liście inne niż $liście$ (logiczne i), (logiczne lub) i $logiczne$ nie $.$
$-węzły$ i $.$ co najmniej jedno dziecko
$mają$ dokładnie jedno dziecko.

$\bot$ Liście oznaczone $) reprezentują$ stałą funkcję boolowską, która zawsze daje 1 ( $x$ is interpreted as the assignment $x=1$ , i.e. it represents the Boolean function which evaluates to 1 if and only if $x=1$ . The Boolean function represented by a $\bigtriangleup$ -node to ten, który ma wartość 1 wtedy i tylko wtedy, gdy funkcja boolowska wszystkich jej dzieci ma wartość 1. Podobnie $reprezentuje$ funkcję boolowską, która ma wartość 1 wtedy i tylko wtedy, gdy funkcja boolowska co najmniej jednego dziecka ma wartość 1. Wreszcie $dziecka$ reprezentuje uzupełniającą funkcję boolowską jej dziecko, tj. tę, która ma wartość 1, wtedy i tylko wtedy, gdy funkcja boolowska jego ocenia na 0.

PDAG, BDD i NNF

Każdy binarny diagram decyzyjny (BDD) i każda postać normalna negacji (NNF) są również PDAG z pewnymi szczególnymi właściwościami. Poniższe rysunki przedstawiają funkcję logiczną ${\ Displaystyle f (x1, x2, x3) = -x1 * -x2 * -x3 + x1 * x2 + x2 * x3}$ :

BDD dla funkcji f

PDAG dla funkcji f uzyskany z BDD

PDAG dla funkcji f

Zobacz też

M. Wachter i R. Haenni, „Propositional DAGs: a New Graph-Based Language for Representing Boolean Functions”, KR'06, 10. Międzynarodowa Konferencja na temat zasad reprezentacji wiedzy i rozumowania, Lake District, Wielka Brytania, 2006.
M. Wachter i R. Haenni, „Probabilistic Equivalence Checking with Propositional DAGs”, Raport techniczny iam-2006-001, Instytut Informatyki i Matematyki Stosowanej, Uniwersytet w Bernie, Szwajcaria, 2006.
M. Wachter, R. Haenni i 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, Hiszpania, 2006.