1

I need to compare a given logical expression with another in java, to identify if both are the same. For example, consider an expression as ((a&b)&(c|d)&(e&f)) and other as ((a&e)&(c|d)&(b&f)), they both are equivalent. Consider (a&(f&(b&e))&(c|d)): this is also equivalent. Furthermore, this expressions can be nested. I thought of converting this to prefix notations, but can't find a proper way through. Expressions is a recursive class object with expression-type as AND/OR and an array of it's child expressions ex. for above first expression:

{
    type: AND,
    expressions: [{
        type: AND,
        expressions: [{
            type: SIMPLE,
            expression: [a]       <-- this could also be nested if type would have been logical
        }, {
            type: SIMPLE,
            expression: [b]
        }]
    }, {
        type: OR,
        expressions: [{
            type: SIMPLE,
            expression: [c]
        }, {
            type: SIMPLE,
            expression: [d]
        }]
    }, {
        type: AND,
        expressions: [{
            type: SIMPLE,
            expression: [e]
        }, {
            type: SIMPLE,
            expression: [f]
        }]
    }]
}

Is there any way to simplify expressions and compare them?

user7630232
  • 135
  • 1
  • 3
  • 16
  • You probably want to convert the expression to either CNF or DNF, then sort the clauses and then compare. You might also want to minimize the expressions using one of the many minification algorithms like the marking algorithm before comparing. If during algorithm execution, you find a counter-example, terminate. This problem has been studied extensively in theoretical computer science and papers are readily available. Any beginner course on logic should cover this. look at constraint solving. – Polygnome Oct 17 '20 at 21:32
  • @Polygnome If I do perform cnf, then how to sort the clauses (any criteria for this?). I am not getting the sense properly, can you point out one or two paper/course for this? – user7630232 Oct 19 '20 at 04:12

1 Answers1

1

You can use the "boolean.py" module to do this. If you want to try it, there's a bit of a trick. You need to install via "pip install boolean.py" vs "pip install boolean". They're two different packages, and you want the '.py' version.

Here's looking at your examples, and a failure case that I added as well:

import boolean
algebra = boolean.BooleanAlgebra()
expr1 = algebra.parse("((a&b)&(c|d)&(e&f))").simplify()
expr2 = algebra.parse("((a&e)&(c|d)&(b&f))").simplify()
expr3 = algebra.parse("(a&(f&(b&e))&(c|d))").simplify()
print(expr1 == expr2)
print(expr1 == expr3)

expr4 = algebra.parse("(a&(f&(b&e))&(c|d)&(x|y))").simplify()
expr5 = algebra.parse("(a&(f&(b&e))&(c|y)&(x|d))").simplify()

print(expr4 == expr5)

Result:

True
True
False
CryptoFool
  • 21,719
  • 5
  • 26
  • 44
  • I need to apply this in java though. Any alternatives for that? – user7630232 Oct 19 '20 at 03:54
  • Ha! Oops. Sorry. I didn't notice that, obviously. Sorry about that. I'll take a look... – CryptoFool Oct 19 '20 at 04:00
  • This library MIGHT do the same thing. It also has a `simplify()` method: https://github.com/bpodgursky/jbool_expressions – CryptoFool Oct 19 '20 at 04:09
  • yes @Steve thanks, I did played with this library, and it suits my use-cases. The only challenge I see is to convert my java objects to suitable Expressions/Tree used by this library, as it accepts only Expression. How can I convert my java class object to this. – user7630232 Oct 27 '20 at 17:34