Упростить логический алгоритм выражения

Кто-нибудь знает об алгоритме для упрощения булевых выражений?

Я помню булевскую алгебру и карты Карнаутов, но это предназначено для цифрового оборудования, где EVERTHING является логическим. Я хотел бы что-то, что учитывает, что некоторые подвыражения не являются логическими.

Например:

a == 1 && a == 3

это может быть переведено в чисто булево выражение:

a1 && a3

но это выражение неприводимо, а с небольшим знанием арифметики everibody может определить, что выражение справедливо:

false

Кто-то знает некоторые ссылки?

Ответы

Ответ 1

Вам может быть интересно K-maps и Quine-McCluskey алгоритм.

Я думаю, что SymPy может решать и упрощать булевы выражения, глядя на источник, может быть полезно.

Ответ 2

Ваш конкретный пример будет решен с помощью SMT-решателя. (Это определило бы, что никакая настройка переменных не может сделать выражение true, поэтому оно всегда false. Более общее упрощение выходит за рамки для таких решателей.) Показывая, что выражение эквивалентно true или false конечно, NP-hard, даже не внося арифметики в сделку, так что довольно круто, что там практически программное обеспечение даже для этого. В зависимости от того, сколько арифметических знаний доступно, проблема может быть неразрешимой.

Ответ 3

Есть две части этой проблемы: упрощение логики и упрощение представлений.

Для логического упрощения, Quine-McCluskey. Для упрощения представления рекурсивно извлекают термины с использованием тождества распределения (0 & 1 | 0 & 2) == 0 & (1 | 2).

Я подробно описал процесс здесь. Это дает объяснение, используя только и и |, но его можно модифицировать, чтобы включить все логические операторы.

Ответ 4

Первый снимок с использованием Google нашел эту статью:

http://hopper.unco.edu/KARNAUGH/Algorithm.html

Конечно, это не касается небулевых подвыражений. Но эта последняя часть в ее общем виде действительно сложна, так как определенно нет алгоритма для проверки того, является ли произвольное арифметическое выражение истинным, ложным или каким-либо другим. То, о чем вы просите, глубоко уходит в область оптимизация компилятора.

Ответ 5

Является ли число возможных отдельных значений конечными и известными? Если это так, вы можете преобразовать каждое выражение в логическое выражение. Например, если a имеет 3 различных значения, тогда у вас могут быть переменные a1, a2 и a3, где a1 является истинным, означает, что a == 1 и т.д. После этого вы можете положиться на Quine- McCluskey (что, вероятно, лучше для более крупных примеров, чем карты Карно). Вот несколько Java-код для Quine-McCluskey.

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

Ответ 6

Это тяжелый человек. Алгоритм простейшим способом, который я нашел, соответствовал каждой выходной комбинации с каждым вводом каждой комбинации. Но что основной алгоритм не решал каждое выражение.

Если весь вывод (q1, q2, q3, q4) тот же, что и для входной комбинации A, результатом упрощения будет A.

Если нет, вы попробуете другую зависимость переменной/ввода.