Как определить, совпадают ли два логических выражения

Question

Мне нужно определить, совпадают ли два разных логических выражения.Например:

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

Эти два фактически одинаковыПоэтому мне нужно определить, совпадают ли они.Я использую C #.

Answer 1

Я не уверен, что буду следовать тому, что вы спрашиваете ... Если это выражения, использующие логические значения (т. Е. A и b в вашем примере - логические значения), вы можете составить для них таблицу истинности если каждый случай совпадает, то ваши выражения эквивалентны.

Существуют и другие способы, но их реализация довольно проста. Просто подключите a = true, b = true; a = правда, b = ложь; a = false b = true; 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

Выражения 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 ? "==" : "!=");
}

Answer 5

Проверка, имеют ли a и b одинаковое логическое значение

private bool Equals (bool a, bool b) { вернуть! (a ^ b); }