Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.2k questions

1.3k answers

1.7k comments

593 users

0 votes
Drawing ZDD : for the set representation {a,c,d}
Can we skip drawing dashed lines from each of these nodes to zero? Is it wrong if we skip it?
When is it appropriate to assign some node to zero?
in * TF "Emb. Sys. and Rob." by (370 points)

1 Answer

0 votes
In general, both outgoing edges of nodes in binary decision diagrams must be drawn, since it is not possible to know which node will be connected by the missing edge. However, there is one exception that is often used: The leaf node 'false' and all edges leading to it may be omitted. This is understood, and you can do it.

'When is it appropriate to assign a node to zero?' I think you are wondering when a node has an edge connected to the zero leaf node. Well, that depends on the Boolean function. For BDDs, any function equivalent to the formula x ∧ Phi, where x does not occur in Phi, will have nodes such that x's negative co-factor is zero, since x ∧ Phi is equivalent to (x ? Phi : false). Similarly, any function equivalent to the formula ¬x∧Phi is equivalent to (x?false:Phi), meaning the positive co-factors of the x nodes are zero.
by (172k points)

Related questions

Imprint | Privacy Policy
...