How to determine if two boolean expressions are the same

Answer 1

I'm not sure if I follow what you're asking... If these are expressions using booleans (that is, the a and b in your example are booleans) you could work out the truth table for them, and if every case matches then your expressions are equivalent.

There are other ways but that seems fairly straight forward to implement. Just plug in a=true, b=true; a=true, b=false; a=false b=true; a=false, b=false and see what you get.

Answer 2

Unless you're really, really smart, and your problem contains millions of parameters, I'd say use brute force.

What you're doing is called "Formal equivalence checking", and is frequently done with a reduced ordered binary decision diagram, and at this point I'd be writing wikipedia articles, but since someone's gone to the trouble of doing that already, here they are.

http://en.wikipedia.org/wiki/Formal_equivalence_checking

http://en.wikipedia.org/wiki/Binary_decision_diagram

... And I had no idea that the linq Expressions namespace existed. In which case, maybe I'd go with what Ivan said.

Answer 3

There is no out of the box way to do that. The closest you get is Expression.Reduce() method, which doesn't do the reduction you want.

You will need to write an expression parser that simplifies, say boolean expressions, and then some logic to verify that the simplified expressions are the same.

Example class (no verification, just the framework of getting the expressions in:

public class ExpressionTest {
    public bool AreExpressionsSame<T>(Expression<T>/*<Func<bool,bool,bool>>*/ expr1, Expression<T> expr2) {
        var expr1_reduced = expr1.Reduce();
        var expr2_reduced = expr2.Reduce();
        //at this point expr2_reduced is the same as it went it.
        return true;
    }


    public void AreExpressionSameShouldAcceptLambda() {
        ExpressionTest et = new ExpressionTest();

        et.AreExpressionsSame<Func<bool,bool,bool>>((a,b) => a || b, (a,b)=>a && b || b);
    }
}

Answer 4

Maybe I am missing the point here, but can't you just do this:

if (S1 == S2)
{
    // Expressions are the same
} else {
    // Expressions are not the same
}