CODEWITHSUNDEEP
algorithmdata-structuresimplementationboolean-logicbinary-decision-diagram
Palash Ahuja
Palash Ahuja

Reputation: 522

Converting binary decision diagram to truth table

Given a binary decision diagram, how do I convert it into a truth table? What is the exact algorithm for it ? I have been trying this for a long time. Here is an example which one can follow:

enter image description here

Source: Wikipedia.

(The dotted edges represent 0; solid edges, 1.)

Upvotes: 2

Views: 1245

Answers (1)

kjhughes
kjhughes

Reputation: 111551

Beginning at the root node, traverse tree in depth-first manner.

For each leaf node reached, record an entry in truth table as follows:

  • x1 is 0 if you descended the dashed edge from node x1; 1 otherwise.
  • x2 is 0 if you descended the dashed edge from node x2; 1 otherwise.
  • x3 is 0 if you descended the dashed edge from node x3; 1 otherwise.
  • f is value of the leaf node.

Upvotes: 3

Related Questions