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 (tačno), (netačno), ili Bulovom promenljivom.
- Čvorovi koji nisu listovi mogu biti (logičko I), (logičko ILI) i (logičko NE).
- - i -čvorovi imaju barem jedno dete.
- -čvorovi imaju tačno jedno dete.
Listovi označeni sa () predstavljaju konstantu Bulove funkcije koja je uvek jednaka 1 (0). List označen Bulovom promenljivom se tumači kao zadavanje , to jest, predstavlja Bulovu funkciju koja je jednaka 1 ako i samo ako je . Bulova funkcija predstavljena sa -čvorom je ona koja je jednaka 1, ako i samo ako je Bulova funkcija sve njegove dece jednaka 1. Slično, -čvor predstavlja Bulovu funkciju koja je jednaka 1, ako i samo ako je Bulova funkcija bar jednog deteta jednaka 1. Konačno, -č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
[uredi | uredi izvor]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 :
Vidi još
[uredi | uredi izvor]
Reference
[uredi | uredi izvor]- 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.