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

Question

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

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

Пример:
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

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

4

algorithm boolean-expression c++chaining

Решение

Другие решения

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

0

Источник

Accepted Answer

Одним из подходов к вашей проблеме может быть использование метода грубой силы. Под этим я подразумеваю: попробуйте все возможные комбинации значений 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 из предоставленной пользователем строки. Для выражений, которые не упрощаются вплоть до одного вывода, вы можете заменить код, который сравнивает входные столбцы таблицы истинности с результирующим столбцом, методом генерации минимальной строки (упрощение начального входного логического выражения).

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

0