Výrokově zaměřený acyklický graf - Propositional directed acyclic graph

A výrokově zaměřený acyklický graf (PDAG) je datová struktura který se používá k reprezentaci a Booleovská funkce. Booleovská funkce může být reprezentována jako rootovaná, směrovaný acyklický graf v následujícím tvaru:

Listy jsou označeny ${displaystyle op}$ (skutečný), ${displaystyle ot}$ (false) nebo logická proměnná.
Ne-listy jsou ${displaystyle igtriangleup}$ (logické a), ${displaystyle igtriangledown}$ (logické nebo) a ${displaystyle Diamond}$ (logicky ne).
${displaystyle igtriangleup}$ - a ${displaystyle igtriangledown}$ -uzly mají alespoň jedno dítě.
${displaystyle Diamond}$ -uzly mají přesně jedno dítě.

Listy označené ${displaystyle op}$ ( ${displaystyle ot}$ ) představují konstantní booleovskou funkci, která se vždy vyhodnotí na 1 (0). List označený logickou proměnnou ${displaystyle x}$ se interpretuje jako zadání ${displaystyle x = 1}$ , tj. představuje booleovskou funkci, která se vyhodnotí na 1 právě tehdy ${displaystyle x = 1}$ . Booleovská funkce představovaná a ${displaystyle igtriangleup}$ -node je ten, který se vyhodnotí na 1, právě když booleovská funkce všech jejích podřízených vyhodnotí na 1. Podobně ${displaystyle igtriangledown}$ -node představuje booleovskou funkci, která se vyhodnotí na 1, právě tehdy, když booleovská funkce alespoň jednoho dítěte bude vyhodnocena jako 1. Nakonec a ${displaystyle Diamond}$ -node představuje doplňkovou booleovskou funkci jejího podřízeného prvku, tj. tu, která se vyhodnotí na 1, právě tehdy, když booleovská funkce jejího podřízeného objektu vyhodnotí 0.

PDAG, BDD a NNF

Každý binární rozhodovací diagram (BDD) a každý normální forma negace (NNF) jsou také PDAG s některými zvláštními vlastnostmi. Následující obrázky představují booleovskou funkci ${displaystyle f (x1, x2, x3) = - x1 * -x2 * -x3 + x1 * x2 + x2 * x3}$ :

BDD pro funkci f

PDAG pro funkci f získanou z BDD

PDAG pro funkci f

Viz také

Reference

M. Wachter & R. Haenni, „Propositional DAGs: a New Graph-Based Language for Representing Boolean Functions“, KR'06, 10. mezinárodní konference o zásadách reprezentace a uvažování znalostí, Lake District, UK, 2006.
M. Wachter & R. Haenni, „Probabilistic Equivalence Checking with Propositional DAGs“, technická zpráva iam-2006-001, Ústav výpočetní techniky a aplikované matematiky, Univerzita v Bernu, Švýcarsko, 2006.
M. Wachter, R. Haenni a J. Jonczy, „Spolehlivost a diagnostika modulárních systémů: nový pravděpodobnostní přístup“, DX'06, 18. mezinárodní workshop o zásadách diagnostiky, Peñaranda de Duero, Burgos, Španělsko, 2006.