Lesson plan

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

Back to article

Article summary

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.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.