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

Из Википедије, слободне енциклопедије

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

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

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

PDAG, BDD, и NNF[уреди]

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