Database Reference
In-Depth Information
∨
¬
Figure 5.1:
A d-DNNF for the propositional formula
XYU
XYZ(
U)
.
Figure 5.2:
An OBDD (which is also an FBDD) for the propositional formula
X
1
Y
1
∨
X
1
Y
2
∨
X
2
Y
3
∨
X
2
Y
4
.
5.2.1 D-DNNF
¬
A d-DNNF is a circuit restricted to
independent-AND
,to
disjoint-OR
, and to
NOT
gates. All
variables are on the leaf nodes. The independent-AND gates are called
decomposable
(D) and the
disjoint-OR gates are called
deterministic
(d). Furthermore, all the NOT gates are restricted to be
applied only to variables (which can be achieved by applying repeatedly de Morgan's laws), which is
also called a
Negation Normal Form
(NNF): this gives the name, d-DNNF [
Darwiche and Marquis
,
2002
].
Figure 5.1
illustrates a simple d-DNNF.
The restriction that the NOT gates be applied only to variables has an undesirable conse-
quence: it is not known whether one can represent the negation of a d-DNNF without increasing
the size by more than a polynomial amount. However, for our purpose, we do not need to restrict
the application of NOT gates, and we will allow them to occur anywhere in the circuit: we denote
d-DNNF
¬
such a circuit. Thus, a d-DNNF
¬
consists of independent-AND, of independent-OR,
