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

Every **binary decision diagram (BDD)** and every **negation normal form (NNF)** is also a PDAG with some particular properties. The following pictures represent the Boolean function** f(x1,x2,x3) = − x1 * − x2 * − x3 + x1 * x2 + x2 * x3. **See picture below for that.

### The Correspondence between PDAG and AHO (Atomistic Hybrid Object)

The semantics of PDAG resembles the one of AHO the symbolic element in the atomistic model. PDAG is an automaton of type three in the Chomsky hieararchy.

Grammar | Languages | Automaton | Production rules (constraints) |
---|---|---|---|

Type-0 | Recursively enumerable | Turing machine | (no restrictions) |

Type-1 | Context-sensitive | Linear-bounded non-deterministic Turing machine | |

Type-2 | Context-free | Non-deterministic pushdown automaton | |

Type-3 | Regular | Finite state automaton | and |

However, the **command **of AHO is more powerful, it can express any clause adapted from source code (*loopClause *is any loop, *pathClause *is any branch, *setClause *is any change of any variable etc) when splitted into sub-commands. There is one characteristic feature when describing mathematical calculations or non-trivial logical equations. Each AHO should be atomistic. The command of each AHO for calculations, logical operations and transformations is *opClause*. It refers to an operation.

The semantics of the * command *covers all levels of the Chomsky hieararchy. However, simulating levels 0 and 1 needs some arrangements. See more about the limitations from the book.

Some links:

- PDAG at Wiki: http://en.wikipedia.org/wiki/Propositional_directed_acyclic_graph
- Semantic Definition for the Atom: https://symbolicanalysis.wordpress.com/2009/09/08/semantic-definition-for-the-atom/
- Chomsky hieararchy: http://en.wikipedia.org/wiki/Chomsky_hierarchy

## Leave a comment

Comments feed for this article