Propositional directed acyclic graph
From Wikipedia, the free encyclopedia
From Wikipedia, the free encyclopedia
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 labeled with () represent the constant Boolean function which always evaluates to 1 (0). A leaf labeled with a Boolean variable is interpreted as the assignment , i.e. it represents the Boolean function which evaluates to 1 if and only if . The Boolean function represented by a -node is the one that evaluates to 1, if and only if the Boolean function of all its children evaluate to 1. Similarly, a -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 -node represents the complementary 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.
Every binary decision diagram (BDD) and every negation normal form (NNF) are also a PDAG with some particular properties. The following pictures represent the Boolean function :
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.