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

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

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

Например:

a == 1 && a == 3

это можно перевести в чистое логическое выражение:

a1 && a3

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

false

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


boolean algorithm boolean-logic boolean-expression
person Olmo    schedule 15.03.2011    source источник
comment
Что, если a объявлено как изменчивая переменная/поле в языках/средах выполнения, которые это допускают, а значение колеблется между 1 и 3 в другом потоке? Я не говорю, что это хороший дизайн, но в программном обеспечении «всегда» и «никогда» обычно являются относительными терминами.   -  person Lasse V. Karlsen    schedule 15.03.2011
comment
Это не проблема, фактическое использование для поставщика LINQ, а фактические значения - это те, которые были на момент перевода запроса. Если запрос будет выполнен снова, упрощение будет запущено снова с обновленными значениями.   -  person Olmo    schedule 15.03.2011
comment
Это невозможно в общем. Например, a > 0 and b > 0 and n > 2 and a^n + b^n = c^n всегда ложно, но это не так просто доказать. Это означает, что вы застряли со специальными упрощениями, и на ваш вопрос нет четкого ответа (поскольку это будет зависеть от характера выражений, которые вы, вероятно, увидите).   -  person    schedule 15.03.2011
comment
Вы правы, но поскольку это просто алгоритм упрощения, я согласен с любым алгоритмом, который улучшает ситуацию, даже если это не лучшее решение. Основной сценарий - это равенство и отдельные операторы в основном для перечислимых и ссылочных типов. Целые числа с == ›= › ‹ ‹= != было бы неплохо иметь.   -  person Olmo    schedule 16.03.2011

Ответы (6)


arrow_upward
10
arrow_downward

Вас могут заинтересовать K-карты и алгоритм Куайна-МакКласки.

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

person Benjamin    schedule 15.03.2011

arrow_upward
6
arrow_downward

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

person Darius Bacon    schedule 15.03.2011

arrow_upward
5
arrow_downward

Эта проблема состоит из двух частей: логического упрощения и упрощения представления.

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

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

person douggard    schedule 05.03.2014

arrow_upward
2
arrow_downward

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

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

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

person Doc Brown    schedule 15.03.2011
comment
Я читал статью раньше, но также обнаружил, что она совершенно не детализирована и не содержит кода. - person Olmo; 16.03.2011

arrow_upward
2
arrow_downward

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

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

person Michael McGowan    schedule 15.03.2011
comment
точно!, это то, что я имею в виду, но в этом случае алгоритм не будет знать, что в моем примере a1 && a3 на самом деле ложно. так как не может быть 1 и 3 одновременно. Я думаю, что мне нужно привязать значения к переменным и найти противоречия в терминах Карнота. - person Olmo; 16.03.2011

arrow_upward
-1
arrow_downward

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

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

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

person The Mr. Totardo    schedule 24.03.2015