Оптимизация логических выражений
Цель данной статьи - познакомить с алгеброй логики, важной задачей которой является оптимизация логических выражений, т.е. приведение выражений к виду, содержащему наименьшее число аргументов или операций над ними. Заметьте: в разных случаях критерии оптимальности могут кардинально отличаться, и не всегда оптимизация одних критериев благотворно влияет на другие критерии.
Вот пример фрагмента из программы на C со сложными условиями (здесь "&&", "||" и "!" - специальная форма конъюнкции, дизъюнкции и отрицания):
if(dirFind == 0 || !ftime || notCHANGE){
msg = "/c only when compare date/time";
if(invert == 0 || notCHANGE && !arg){
msg = "No date/time or attributes option";
if(!notCHANGE || (arg | ftime)) msg = NULL;
}
}
Построим выражение, истинное, когда координаты точки находятся в границах квадрата (при условии, что абсцисса идёт слева направо, а ось ординат сверху вниз):
ЕСЛИ точка.X >= квадрат.левый.X И
точка.X <= квадрат.правый.X И
точка.Y >= квадрат.верхний.Y И
точка.Y <= квадрат.нижний.Y,
ТО точка лежит в квадрате.
Выбрать наименьшее из трёх A, B, C:
если A < B и A < C то наименьшее = A,
если A >= B и B < C то наименьшее = B,
если A >= C и B >= C то наименьшее = C.
Внимание! Приведённый пример не оптимален. Сократим его, вынеся за скобки некоторые сравнения:
если A < B то
если A < C то наименьшее = A,
иначе наименьшее = C.
иначе
если B < C то наименьшее = B,
иначе наименьшее = C.
В оптимизированном примере всего три сравнения вместо шести. Более того, если в первом примере для достижения результата всегда выполняется шесть сравнений, то во втором примере всегда выполняется только два сравнения! Замечательный результат. Пример сокращения, учитывающий особенности натурального ряда:
если x >= 1 то
если x >= 0 то результат = 3*x
иначе результат = -x
иначе результат = x
Эта конструкция сокращается до следующей (если x >= 1, то x также >= 0):
если x >= 1 то результат = 3*x иначе результат = x
Вот пример формального сокращения с учётом основных законов:
(a and b) or (not a and b) or (a and not b)
= ((a and b) or (not a and b)) or (a and not b)
= ((a or not a) and b) or (a and not b)
= (1 and b) or (a and not b) = b or (a and not b) = a or b
Иногда встречаются сложные разборы случаев (разновидность таблицы решений). Рассмотрим следующую таблицу расценок на билеты в бассейн. Здесь переменные A (возраст < 14 лет), B (возраст <= 18 лет), C (группа), D (студенты) - результаты опроса.
если a and not b то ошибка в опросе
если a and b and c and d то 1 рубль
если a and b and c and not d то 1 рубль
если a and b and not c and d то 2 рубля
если a and b and not c and not d то 2 рубля
если not a and b and c and d то 1 рубль
если not a and b and c and not d то 2 рубля
если not a and b and not c and d то 2 рубля
если not a and b and not c and not d то 3 рубля
если not a and not b and c and d то 1 рубль
если not a and not b and c and not d то 3 рубля
если not a and not b and not c and d то 2 рубля
если not a and not b and not c and not d то 4 рубля
Вариантов сокращения этого разбора несколько. Вот первый вариант с пятью ветвями (ветви с одинаковым результатом объединены):
если a and not b то ошибка в опросе
если c and ((a and b) or (not a and d)) то 1 рубль
если (not c and ((a and b) or (not a and d)))
or (not a and b and c and not d) то 2 рубля
если not a and not d and
((b and not c) or (not b and c)) то 3 рубля
если not a and not b and not c and not d то 4 рубля
Вот вариант с сокращённым числом "задаваемых вопросов", хотя и с большим количеством ветвей. Основание - зависимость переменных A и B.
если a and not b то ошибка в опросе
если a and c то 1 рубль
если not a and c and d то 1 рубль
если a and not c то 2 рубля
если not a and b and c and not d то 2 рубля
если not a and not c and d то 2 рубля
если not a and b and not c and not d то 3 рубля
если not b and c and not d то 3 рубля
если not b and not c and not d то 4 рубля
Выше разборы случаев независимы и все ветви можно отрабатывать одновременно. Последовательный разбор с выносом условий "за скобку" позволяет ещё больше сократить сложность разбора (глубина 9 при 12 вопросах):
если a and not b то ошибка в опросе
иначе если a and c то 1 рубль
иначе если а то 2 рубля
иначе если c and d то 1 рубль
иначе если b and c то 2 рубля
иначе если d то 2 рубля
иначе если b то 3 рубля
иначе если c то 3 рубля
иначе 4 рубля
Если продолжить вынос за скобки, то можно получить древовидный разбор (всего 11 вопросов, глубина 5):
если a and not b то ошибка в опросе
иначе если (a and b) or (not a and d) то
если c то 1 рубль
иначе 2 рубля
иначе если b and c то 2 рубля
иначе если not b and not c то 4 рубля
иначе 3 рубля
Наконец, доведя вынос за скобки до конца, можно получить следующий разбор (всего 9 вопросов, глубина 6):
если a and not b то ошибка в опросе
иначе если not d то
если not c то
если a то 2 рубля
иначе если b то 3 рубля
иначе 4 рубля
иначе
если a то 1 рубль
иначе если b то 2 рубля
иначе 3 рубля
иначе
если not c то 2 рубля
иначе 1 рубль
Обратите внимание! Помимо размера опросника сократилась и сложность его применения. Если в первом варианте при последовательном переборе ветвей в худшем случае (4 рубля) получается 50 вопросов (обращений к переменным), то в последнем варианте в худшем случае (например, "больше 14 лет и больше 18 лет, не студенты, группа") получается 6 вопросов. Сокращение в 8 раз!
К сожалению, до сих пор нет эффективных алгоритмов, целенаправленно и быстро минимизирующих функции и подбирающих наиболее экономичные схемы реализации заданных выражений. Найти гарантированно минимальное выражение произвольной функции можно лишь методом полного перебора вариантов различных способов группировки, а это реально осуществимо лишь при небольшом числе аргументов. С ростом же числа аргументов сложность минимизации растёт экспоненциально и быстро становится не под силу ни человеку, ни компьютеру. Но расстраиваться не стоит - на практике сложные, плохо оптимизируемые выражения встречаются не часто, а основные законы тождественных преобразований позволяют неплохо сократить сложность большинства выражений без особых усилий.