Distributing AND over OR in a binary tree (Conjunctive Normal Form)

Question

I am trying to convert a binary tree, for example.

OR (Implementation of Operator - a specialisation of TreeNode... see below) |-A (Implementation of TreeNode... see below) |-OR |-B |-AND (Implementation of Operator - a specialisation of TreeNode... see below) |-C |-OR |-D |-E 

into this equivalent representation of the Conjunctive Normal Form (CND). I believe that since I use only the logical operators OR + AND, the only step I have to follow is to distribute AND over OR. This would create the following tree (still binary for my purposes) in CNF:

 AND |-OR | |-A | |-OR | |-B | |-OR | |-E | |-D |-OR |-A |-OR |-B |-OR |-E |-C 

I am having trouble creating an algorithm for this ... so far I have the following skeleton that will overwrite the bottom from bottom to top (note the recursive call to restore):

 public TreeNode reconstruct(TreeNode treeNode) { if(treeNode instanceof Operator) { TreeNode left = reconstruct(((Operator)treeNode).getLeft()); TreeNode right = reconstruct(((Operator)treeNode).getRight()); return distribute(treeNode, left, right); } else return node; } 

Using classes:

  ----------- | TreeNode | // Interface ----------- ^ | ----------- | Operator | // Interface ----------- | getLeft() | | getRight()| | setLeft() | | setRight()| ----------- 

Can anyone suggest a distribution implementation that will convert to CNF?

// EDIT 1 (after the response from nif)

 private Node distribute(TreeNode node, TreeNode left, TreeNode right) { if (node instanceof Or) { if (left instanceof And) { // distribute right over left AND return new And( new Or(((Operator)left).getLeft(), right), new Or(((Operator)left).getRight(), right) ); } else if (right instanceof And) { // distribute left over right AND return new And( new Or(((Operator)right).getLeft(), left), new Or(((Operator)right).getRight(), left) ); } } if(node instanceof Operator) { ((Operator)node).setLeft(left); ((Operator)node).setRight(right); } // default return node; } 

Answer 1

If AND and OR are the only statements you use, it should not be difficult to convert your tree to CNF. All you have to do is find structures in the form of OR(AND(X,Y), Z) or OR(Z, AND(X,Y)) and use the distribution law.

 private static TreeNode distribute(TreeNode n, TreeNode left, TreeNode right) { if (n instanceof Or) { if (left instanceof And) { // distribute right over left AND return new And(new Or(left.getLeft(), right), new Or(left.getRight(), right)); } else if (right instanceof And) { // distribute left over right AND return new And(new Or(right.getLeft(), left), new Or(right.getRight(), left)); } } // no change return treeNode; } 

This algorithm should be applied to all nodes of your tree until the tree is no longer modified. The order in which you apply the algorithm to the nodes does not matter. An intuitively repeated application of the algorithm will stretch all AND nodes over the OR nodes until the tree is in CNF.

 TreeNode root = ....; while (true) { TreeNode transformedRoot = reconstruct(root); if (root.equals(transformedRoot)) { break; } root = transformedRoot; } // root is now in CNF 

Note: Keep in mind that the CNF transform can blow your tree exponentially in size. The implementation shown is rather primitive and does not use any improvements to reduce computation time.

Answer 2

I recommend that you look at how the tree moves, your code looks like a depth search, so that you start with the deepest branch (the deepest operator), you need to develop your distribute method, waiting for this order and apply Distribution laws for child nodes in reverse direction.

A very general description of what the distribution method should do:

A stream of some distribution law is applied according to the type of parent operation and child nodes. Each child node can be an operator or a value, depending on this combination distributes the distribution according to the law.

The pseudo code of what I'm trying to tell you is:

 if parent node is OR type if child nodes are OPERATOR-VALUE combination if OPERATION is AND type apply correspondig distribution return the new parent else apply correspondig distribution return the new parent if child node are VALUE-VALUE combination return parent if parent node is AND type if child nodes are OPERATOR-VALUE combination if OPERATION is AND type apply correspondig distribution return the new parent else apply correspondig distribution return the new parent if child nodes are VALUE-VALUE combination return parent; 

Implementation Example:

 public TreeNode distribute(TreeNode parent,TreeNode leftChild, TreeNode rightChild) { if( !(leftChild instanceof Operator) && !(rightChild instanceof Operator) ){ /*There is nothing to do */ return parent; } if( parent.getType() == 'OR'){ /* Apply distributive laws and return the new branch for example: */ if ( (leftChild instanceof operator) && !(rightChild instanceof Operator) ){ TreeNode operatorLeftChild = leftChild.getLeftChild(); TreeNode operatorRightChild = leftChild.getRightChild(); if(leftChild.getType() == 'AND' ) { /* Applying distributive laws: rightChild OR (operatorLeftChild AND operatorRightChild) -> (rightChild OR operatorLeftChild) AND (rightChild OR operatorRightChild) */ TreeNode newBranch = new Operator("AND"); /*new Left child*/ TreeNode newLeftChild= new Operator("OR"); newLeftChild.setLeftChild(rightChild); newLeftChild.setRightChild(operatorLeftChild); /*new Richt Child */ TreeNode newRightChild= new Operator("OR"); newRightChild.setLeftChild(rightChild); newRightChild.setRightChild(operatorRightChild); /*Setting the new Branch*/ newBranch.setLeftChild(newLeftChild); newBranch.setRightChild(newRightChild); return newBranch; } } } if( parent.getType() == 'AND'){ /* Else-If and distributive laws stuff */ } /* You can also implement this part wihtout the else-if code by implementing a true table but is more abstract and less human redeable */ } 

Note The previous code has not been tested, and I accept a lot of things that I don’t know how your tree will be implemented, you will need to update the parent link in the child nodes.