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

Question

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

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

Например:

a == 1 && a == 3

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

a1 && a3 

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

false

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

Answer 6

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

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

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