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 (true), (false), or a Boolean variable.
- Non-leaves are (logical and), (logical or) and (logical not).
- - and -nodes have at least one child.
- -nodes have exactly one child.
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 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.
Read more about Propositional Directed Acyclic Graph: PDAG, BDD, and NNF, See Also
Famous quotes containing the words directed and/or graph:
“Anger is always concerned with individuals, ... whereas hatred is directed also against classes: we all hate any thief and any informer. Moreover, anger can be cured by time; but hatred cannot. The one aims at giving pain to its object, the other at doing him harm; the angry man wants his victim to feel; the hater does not mind whether they feel or not.”
—Aristotle (384–322 B.C.)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)