How to convert a propositional logical tree into a united normal form (CNF) tree

Question

I have a string as a string

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

and convert its CNF output to this string, for example

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

Do I need to do a struct TreeNode to save 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 do this for CNF, which is a conjunctive normal form? give some details of the algorithm. from my point of view, it might be better to use a recursive function to solve this problem, but I still can’t figure out how to use recursion. Or do you have another suggestion to solve this problem?

Answer 1

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

• First, replace the equivalence p<=>q with AND(p=>q,q=>p) , then replace the values p=>q with OR(q,NOT(p)) .

• Convert to the normal form of negation: move all NOT operations down the tree so that NOT operations are only attached to atoms ( A , B ).

• Then the result of CNF(AND(x,y)) is simple: AND(CNF(x),CNF(y)) , since CNF likes to have AND high in the tree.

• The result of CNF(OR(AND(x,y),z)) bit more complicated. Here we will use the conjunction disjunction distribution rule, which OR(AND(x,y),z) equivalent to AND(OR(x,z),OR(y,z)) . Essentially, 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

A simple recursive analysis of the descent parser:

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

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

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

Set a pointer to the source line; call ParseExpression on this pointer; the return value is your tree, and the pointer will point to the first expression in your string.

This relates to one of your questions: how to turn a string into a tree. Adrian Panasyuk turned to another question, how to transform a tree into a normal form. Since you are going to perform additional tree transformations, the “value” in your nodes must be called “op” or something like that to stand behind the “operator” (this is a reserved word in C ++), and this should be an enumeration, and not a string.