CODEWITHSUNDEEP
algorithmrecursionbinary-treeautomataconjunctive-normal-form
Adi GuN
Adi GuN

Reputation: 1294

Can a conjunctive/disjunctive normal form be represented in a binary tree?

I could find this relative question Distributing AND over OR in a binary tree (Conjunctive Normal Form)

I'm not quite sure what would be the out come of the CNF binary tree representation for the this expression. A & B & C

AND
|- A
|- AND
   |-B
   |-C

Is this right? My basic question is does the CNF binary representation can have multiple AND nodes in the tree rather than just one AND node as root. My understanding is we could have non-root AND nodes as long as its parent is an AND node.

Related question is? Is this representation optimal? or representing them in a n-nary tree with just one root AND node is beneficial? The optimality I'm looking here is wrt building and traversal of the tree.

// Edit based on the comment. For the sake of simplicity, assume that the not (~) operator is part of leaf nodes A, B or C. That means you need to worry about ~ operator being part of the non-leaf nodes which might change the tree structure when expanded as per Demorgan's law.

Upvotes: 1

Views: 1148

Answers (1)

Axel Kemper
Axel Kemper

Reputation: 11332

A minimum BDD for your conjunction:

enter image description here

The BDD was created using this online tool.

For a simple AND with three inputs, there is nothing to optimize. The BDD nodes build a chain.

Upvotes: 0

Related Questions