Propositional directed acyclic graph


Propositional directed acyclic graph

A propositional directed acyclic graph (PDAG) is a data structure that is used to represent a Boolean function. A Boolean function can be represented as a rooted, directed acyclic graph of the following form:
* Leaves are labeled with op (true), ot (false), or a Boolean variable.
* Non-leaves are mathcal{4} (logical and), mathcal{5} (logical or) and Diamond (logical not).
* mathcal{4}- and mathcal{5}-nodes have at least one child.
* Diamond-nodes have exactly one child.

Leaves labeled with op (ot) represent the constant Boolean function which always evaluates to 1 (0). A leaf labeled with a Boolean variable 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 mathcal{4}-node is the one that evaluates to 1, if and only if the Boolean function of all its children evaluate to 1. Similarly, a mathcal{5}-node represents the Boolean function that evaluates to 1, if and only if the Boolean function of at least one child evaluates to 1. Finally, a Diamond-node represents the complemenatary Boolean function its child, i.e. the one that evaluates to 1, if and only if the Boolean function of its child evaluates to 0.

PDAG, BDD, and NNF

Every binary decision diagram (BDD) and every negation normal form (NNF) is also a PDAG with some particular properties. The following pictures represent the Boolean function f(x1, x2, x3) = -x1 * -x2 * -x3 + x1 * x2 + x2 * x3:

See also

* Data structure
* Boolean satisfiability problem
* Proposition

References

* 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.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Binary decision diagram — In the field of computer science, a binary decision diagram (BDD) or branching program, like a negation normal form (NNF) or a propositional directed acyclic graph (PDAG), is a data structure that is used to represent a Boolean function. On a… …   Wikipedia

  • PDAG — can refer to: Propositional directed acyclic graph, a data structure in computer science Partially directed acyclic graph, also called mixed graph This disambiguation page lists articles associated with the same title. If an internal link le …   Wikipedia

  • Boolean function — In mathematics, a (finitary) Boolean function is a function of the form f : B k rarr; B, where B = {0, 1} is a Boolean domain and k is a nonnegative integer called the arity of the function. In the case where k = 0, the function is essentially a… …   Wikipedia

  • 2-satisfiability — In computer science, 2 satisfiability (abbreviated as 2 SAT or just 2SAT) is the problem of determining whether a collection of two valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all… …   Wikipedia

  • Resolution (logic) — In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation theorem proving technique for sentences in propositional logic and first order logic. In other words, iteratively applying the… …   Wikipedia

  • Quantitative comparative linguistics — is a branch of comparative linguistics that applies mathematical models to the problem of classifying language relatedness. This includes the use of computational phylogenetics and cladistics to define an optimal tree (or network) to represent a… …   Wikipedia

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia


We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.