how to convert a propositional logical tree into conjunction normal form (CNF) tree

Question

I have a string like string

     s="(=> P (OR (AND A (NOT B)) (AND B (NOT A))))";

and convert it output the CNF of this string,like

( OR ( NOT P ) ( OR A B ) ) ( OR ( NOT P ) ( OR ( NOT B ) ( NOT A ) ) )

do I need to make a struct TreeNode to keep the value?

     struct TreeNode {
            string val;         // The data in this node.
            TreeNode *left;   // Pointer to the left subtree.
            TreeNode *right;  // Pointer to the right subtree.
            //TreeNode *farther;//should I use farther or not in convert to CNF?
      };

how to make it to CNF, which is conjunctive normal form? please give some algorithm detail. from my point of view, maybe use recursive function is better for solving this problem, but I still can not think out how to use recursion. Or you have other suggestion for solving this problem?

Answer 1

Let's say you name your function CNF, taking a tree and returning the tree in CNF.

1. First, replace equivalency p<=>q with AND(p=>q,q=>p) then replace implications p=>q with OR(q,NOT(p)).

2. Convert to negation normal form: move all NOT operations down the tree, so that the NOT operations bind only to atoms (A, B).

3. Then, the result of CNF(AND(x,y)) is simple: AND(CNF(x),CNF(y)), as it is CNF-like to have ANDs high in the tree.

4. The result of CNF(OR(AND(x,y),z)) is a little bit more complicated. Here we will use the rule of distribution of disjunction over conjunction, which is OR(AND(x,y),z) is equivalent to AND(OR(x,z),OR(y,z)). In effect, CNF(OR(AND(x,y),z)) will be AND(OR(CNF(x),CNF(z)),OR(CNF(y),CNF(z)).

And you're done.

Answer 2

Simple recursive descent parser solution:

TreeNode* ParseExpression(const char*& p): If the string pointed to by p does not start with '(' then return ParseAtom(p), else move p past the '(', call ParseOperation(p), then move p past the ')' and return the value returned by ParseOperation.

TreeNode* ParseAtom(const char*& p): skip p past the atom (contiguous series of non-spaces). Return a TreeNode with the atom as value and NULL left and right.

TreeNode* ParseOperation(const char*& p): The string pointed to by p should start with an operator. Move p past the operator, then determine how many operands the operator takes. If one, Call ParseExpression(p) once; if two, call ParseExpression(p) twice. Then return a TreeNode with the operator as value and the results of the one or two ParseExpression calls as left and right (right should be NULL for an operator with only one operand).

Set a pointer pointing to the original string; call ParseExpression on that pointer; the return value is your tree and the pointer will point past the first expression in your string.

This addresses one of your questions: how to turn a string into a tree. Adrian Panasiuk addressed the other question, how to convert a tree to normal form. Since you're going to be doing additional tree transformations, "value" in your nodes should be called "op" or something like that to stand for "operator" (which is a reserved word in C++), and it should be an enum, not a string.