Решение логических выражений с использованием прямой цепочки

Может ли кто-нибудь помочь мне с решением логических выражений с помощью прямой цепочки. Хороший учебник также поможет мне.

Пример: A.(A + B) = A

A.(A + B) => A.A + A.B [Применение дистрибьюторского права]

A.A + A.B => A + A.B [Применение закона идемпотентности]

A + A.B => A.(1 + B)

A.(1 + B) => A.(1) => A

Я приложил огромные усилия, но до сих пор не могу этого сделать. Процедура потребует синтаксического анализа логического выражения, а затем рекурсивной проверки правил. Я думал о создании двоичного дерева выражения, а затем о проверке правил. Верен ли мой подход? Если нет, то предложите мне альтернативу.


c++ algorithm chaining boolean-expression
person Shivam Dixit    schedule 31.08.2013    source источник
comment
Мне не ясны ваши точные требования, но переход к дизъюнктивной нормальной форме кажется хорошим первым шагом.   -  person aschepler    schedule 31.08.2013

Ответы (2)


arrow_upward
0
arrow_downward

Одним из подходов к вашей проблеме может быть использование метода грубой силы. Под этим я подразумеваю: попробуйте все возможные комбинации значений A и B (или столько значений, сколько у вас есть) и создайте таблицу истинности результатов.

Следующий пример иллюстрирует это (хотя он больше похож на C, чем на C++).

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cassert>

const unsigned g_unValues = 2;

bool expression(int values[])
{
    return !!(values[0] * (values[0] + values[1]));
}

void truth_table(bool (*func)(int[]), unsigned nvalues);

int main(int argc, char** argv)
{
    truth_table(expression, g_unValues);

    return 0;
}

void truth_table(bool (*func)(int[]), unsigned nvalues)
{
    assert(pow(2, nvalues) <= sizeof(unsigned));

    int values[nvalues];
    unsigned individuals[nvalues];
    unsigned result = 0;

    std::fill_n(individuals, nvalues, 0);

    // Display truth table header
    for (unsigned j = 0; j < nvalues; j++) std::cout << char('A'+j) << ' ';
    std::cout << "| Result" << std::endl;

    for (unsigned i = 1; i <= pow(2, nvalues); i++)
    {
        for (unsigned j = 0; j < nvalues; j++)
        {
            values[j] = i & 0x1<<j;
            if (values[j]) individuals[j] |= 0x1<<i;
        }

        bool eval = func(values);
        if (eval) result |= 0x1<<i;

        // Display truth table entry
        for (unsigned j = 0; j < nvalues; j++) std::cout << !!values[j] << ' ';
        std::cout << "| " << eval << std::endl;
    }

    for (unsigned j = 0; j < nvalues; j++)
    {
        if (result != individuals[j]) continue;
        std::cout << "Expression equivalence: " << char('A'+j) << std::endl;
        break;
    }
}

Этот код сам по себе не очень полезен, но он может дать вам некоторые идеи, если вы выберете метод грубой силы. Вы можете адаптировать код для создания expression из предоставленной пользователем строки. Для выражений, которые не упрощаются до одного вывода, вы можете заменить код, который сравнивает входные столбцы таблицы истинности со столбцом результата, на метод генерации минимальной строки (упрощение начального входного логического выражения).

Надеюсь, это как-то полезно, удачи :)

person ilent2    schedule 31.08.2013

arrow_upward
0
arrow_downward

я предполагаю, что библиотека С++ Prop ( http://www.cs.nyu.edu/leunga/prop.html ) может быть полезен для этого: он обеспечивает представление символических терминов и поддержку перезаписи, которые можно использовать для реализации вашей системы.

person louis35    schedule 03.10.2013