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

PropertyValue
dbpedia-owl:thumbnail
dbpprop:abstract
  • 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 <math>\top</math> (true), <math>\bot</math> (false), or a Boolean variable. Non-leaves are <math>\mathcal{4}</math> (logical and), <math>\mathcal{5}</math> (logical or) and <math>\Diamond</math> (logical not). <math>\mathcal{4}</math>- and <math>\mathcal{5}</math>-nodes have at least one child. <math>\Diamond</math>-nodes have exactly one child. Leaves labeled with <math>\top</math> (<math>\bot</math>) represent the constant Boolean function which always evaluates to 1 (0). A leaf labeled with a Boolean variable <math>x</math> is interpreted as the assignment <math>x=1</math>, i.e. it represents the Boolean function which evaluates to 1 if and only if <math>x=1</math>. The Boolean function represented by a <math>\mathcal{4}</math>-node is the one that evaluates to 1, if and only if the Boolean function of all its children evaluate to 1. Similarly, a <math>\mathcal{5}</math>-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 <math>\Diamond</math>-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.
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • 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 <math>\top</math> (true), <math>\bot</math> (false), or a Boolean variable.
rdfs:label
  • Propositional directed acyclic graph
owl:sameAs
skos:subject
foaf:depiction
foaf:page
is owl:sameAs of