c# - 如何判断两个布尔表达式是否相同

Question

我需要确定两个不同的布尔表达式是否相同。例如：

S1 = a ∨ b
S2 = (a ∧ ¬b) ∨ b;

这两个其实是一样的。所以我需要检测它们是否相同。我正在使用 C#。

Answer 1

我不确定我是否遵循您的要求...如果这些是使用布尔值的表达式（即您的示例中的 a 和 b 是布尔值），您可以为它们计算出真值表，如果每种情况匹配然后你的表达式是等价的。

还有其他方法，但这似乎很容易实现。只需插入 a=true, b=true; a=真，b=假；a=假 b=真；a=false, b=false 看看你得到了什么。

Answer 2

除非您真的非常非常聪明，并且您的问题包含数百万个参数，否则我会说使用蛮力。

您正在做的事情称为“形式等价检查”，并且通常使用简化的有序二元决策图来完成，此时我正在撰写维基百科文章，但是由于有人已经麻烦地这样做了，在这里他们是。

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

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

...而且我不知道存在 linq Expressions 命名空间。在这种情况下，也许我会同意伊万所说的。

Answer 3

没有开箱即用的方法可以做到这一点。你得到的最接近的是Expression.Reduce()方法，它不会做你想要的减少。

您将需要编写一个表达式解析器来简化，比如布尔表达式，然后使用一些逻辑来验证简化的表达式是否相同。

示例类（没有验证，只是获取表达式的框架：

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

检查 a 和 b 是否具有相同的布尔值

private bool Equals(bool a, bool b) { return !(a ^ b); }

Answer 5

表达式S1和S2是等价的，如果(S1 == S2)所有a, b组合都为真。这种重言式检查可以C#作为真值表枚举实现，如下所示：

static bool S1(bool a, bool b)
{
    return a || b;
}

static bool S2(bool a, bool b)
{
    return (a && !b) || b;
}

static void Main(string[] args)
{
    bool[] tf = { true, false };
    bool bSame = true;

    foreach(bool a in tf)
        foreach(bool b in tf)
        {
            bSame = bSame && (S1(a, b) == S2(a, b));
        }

    Console.WriteLine("S1 {0} S2", bSame ? "==" : "!=");
}