Propositional directed acyclic graph

A propositional directed acyclic graph (PDAG) is a data structure that is used to represent a Boolean function.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 \top (true), \bot (false), or a Boolean variable. * Non-leaves are \bigtriangleup (logical and), \bigtriangledown (logical or) and \Diamond (logical not). * \bigtriangleup - and \bigtriangledown -nodes have at least one child. * \Diamond -nodes have exactly one child.

Leaves labeled with \top ( \bot ) 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 \bigtriangleup -node is the one that evaluates to 1, if and only if the Boolean function of all its children evaluate to 1. Similarly, a \bigtriangledown -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 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.

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 \top (true), \bot (false), or a Boolean variable.

Non-leaves are \bigtriangleup (logical and), \bigtriangledown (logical or) and \Diamond (logical not). \bigtriangleup - and \bigtriangledown -nodes have at least one child. \Diamond -nodes have exactly one child. Leaves labeled with \top ( \bot ) 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 \bigtriangleup -node is the one that evaluates to 1, if and only if the Boolean function of all its children evaluate to 1.

Similarly, a \bigtriangledown -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 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.

File:BDD simple.svg|BDD for the function f File:BDD2pdag.png|PDAG for the function f obtained from the BDD File:BDD2pdag simple.svg|PDAG for the function f

Text derived from https://en.wikipedia.org/w/index.php?oldid=1282081590 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001282081590 · captured 1742791063.0 · version history

Cite this page as: encyclopegia.org, “Propositional directed acyclic graph”, snapshot enwiki-001282081590. https://encyclopegia.org/a/propositional-directed-acyclic-graph

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.