Получение
дизъюнктивных форм

[предыдущая глава]  [оглавление]  [следующая глава]

На примере СДНФ и СКНФ мы видели, что всякую булеву функцию, представленную в виде таблицы истинности, можно выразить через три операции: &, , ~. В современной булевой алгебре вопрос выражения булевых функций через те или иные операции проработан весьма глубоко. Очень много исследований проведено и по вопросу максимального упрощения таких формул. Эти исследования находят широкое применение в компьютерной технике, в проектировании микросхем. Булева алгебра на современном этапе представляет собой довольно обширный раздел, хотя большая его часть специфична, узкоспециализирована, поэтому в более-менее полном объеме вряд ли может представлять интерес для широкого читателя. Здесь мы коснемся лишь верхушки этого айсберга, рассмотрев кое-какие общие принципы сведения булевых функций и формул к небольшому количеству операций.

В предыдущих главах мы рассматривали выражение через конъюнкцию, дизъюнкцию и отрицание произвольной функции, представленной в виде таблицы истинности. А что, если функция представлена в виде булевой формулы? В этом случае мы можем попробовать решить задачу "в лоб", просто составив таую таблицу и вычислив все ее строки. Этот путь вполне реален, хотя иногда может оказаться долгим.

В качестве альтернативы можно применить метод составления цепочек формул. Дело в том, что любую из оставшихся операций можно выразить через эти три:

x y = x&~y
x y = ~x&y
x y = x&~y ~x&y
x y = ~x&~y
x y = x&y ~x&~y
x y = x ~y
x y = ~x y
x | y = ~x ~y

Последовательно применяя перечисленные формулы мы можем избавиться от всех операций, кроме трех. Этим доказан тот факт, что любую булеву формулу можно выразить через данные три операции, получив равноистинную ей формулу. Что дальше? А дальше можно попытаться ее упростить. Для этого понадобится получить дизъюнктивную форму, чтобы применить метод карт Карно или метод приведения подобных членов. Но в дизъюнктивной форме нет скобок, а после применения выписанных выше формул нам, возможно, придется их поставить, чтобы сохранить прядок операций. Например:

(a b) | y = ~(a b) ~y    (0)

- как видите, здесь нельзя просто взять и убрать скобки, не нарушив порядок операций. Значит, надо уметь раскрывать скобки. Для этого есть свои формулы (мы их уже доказывали), напоминающие то, что делается в школе. Раскрытие скобок перед дизъюнкцией:

a & (b c) = (a&c) (b&c)    (1)

Неправда ли, очень напоминает школьную формулу раскрытия скобок для числовых переменных:

a (b + c) = (ac) + (bc)

Интересно, что скобки можно раскрывать похожим способом и тогда, когда операция конъюнкции внутри, а дизъюнкция - снаружи:

a (b & c) = (ac) & (bc)    (2)

Эта красивая симметрия между формулами (1) и (2) характерна только для булевой алгебры. В числовой алгебре нет похожей формулы:

a + (b c) = (a+c) (b+c)

- что лишний раз демонстрирует важный факт: аналогии между булевой алгеброй и обычной срабатывают далеко не всегда, все надо перепроверять. Формулы (1) и (2) понадобятся для раскрытия лишних скобок. "Для полного счастья" не хватает только формул раскрытия скобок, перед которыми стоит отрицание. Такие формулы мы уже видели ранее:

~(x & y) = ~x ~y    (3)

~(x y) = ~x & ~y    (4)

Формул (1), (3) и (4) достаточно для того, чтобы избавиться от всех возможных скобок в любой булевой формуле, использующей только операции &, , ~. Что и требуется для получения дизъюнктивной формы и дальнейшего ее упрощения. Для получения конъюнктивной формы понадобятся формулы (2), (3) и (4).

Теперь мы можем завершить преобразование нашего примера (0) в дизъюнктивную форму:

... = ~(a b) ~y = ~a & ~b ~y

Кстати говоря, использование констант true и false для составления дизъюнктивных и конъюнктивных форм необязательно. Константу true можно выразить в виде: true = x ~x, а false в виде: false = x & ~x.

Вопросы и задания для самостоятельной работы

1. Придумайте самостоятельно формулу, содержащую скобки и операции, отличные от &, , ~, и преобразуйте ее в дизъюнктивную форму, составив цепочку равноистинных формул.
2. Придумайте самостоятельно формулу, содержащую скобки и операции, отличные от &, , ~, и преобразуйте ее в конъюнктивную форму, составив цепочку равноистинных формул.