Conversion to CNF

Question

This is for an assignment. I have to convert the set of statements to CNF and implement them. I know that I need to convert the input in prefix notation it to infix first and then repeatedly apply De Morgans's Laws. However, I don't know how to proceed with the implementation after converting it to infix notation.

1. Do I have to convert it to infix or is there a better process to do this?
2. I have been reading up on BDDs from the implementation in Python here. I'm coding in Java and I'd like to do it by myself without using any external libraries. Any pointers on the implementation algorithm? Am I going in the right direction converting it to infix?

Thanks!

Answer 1

There is no need to convert this to infix - you want to get out of the domain of strings as quickly as possible, for example

public abstract class Expression
public abstract class BinaryExpression extends Expression {
    private Expression expr1;
    private Expression expr2;
    public Expression getExpr1() { return expr1; }
    public void setExpr1(Expression expr) { expr1 = expr; }
}
public abstract class UnaryExpression extends Expression
public class Or extends BinaryExpression
public class Not extends UnaryExpression

and so on. To parse the input into Expressions you may find it useful to use a Recursive Descent Parser, although this is certainly not the only way to parse your input. Once you have your input converted to a symbolic Expression format it should be much easier to apply the boolean laws to convert it to CNF.