Материал: 2160

выделяет на гиперкубе 0,1 n некоторое подмножество вершин – область истинности этой функции.

Если эта область содержит только одну вершину a a1, a2,...,an , то согласно установленному выше правилу (замечание 1.1) формулу данной функции можно построить по координатам данной вершиныa1,a2,...,an . Такая формула будет представлять конъюнкцию n булевых величин вида

Такую матрицу называют булевой. Каждый из ее столбцов опреде-

Определение 2. Формула (1.12) называется совершенной дизъюнктивной нормальной формой булевой функции fk x1, x2,..., xn . Она пред-

ставляет собой дизъюнкцию всех полных конъюнкций для всех вершин области истинности этой функции.

11

Очевидно, полная конъюнкция является частным случаем совершенной д.н.ф. (подобно тому, как столбец является частным случаем матрицы). Поэтому можно утверждать, что формулу (1.12) можно по-

строить для любой булевой функции, имеющей непустую область истинности. Иначе говоря, совершенная д.н.ф. существует для любой булевой функции, кроме константы «ложь». Однако эту константу можно определить более простой формулой 0 xi & xi , использующей только две из трех основных (теперь их так уже можно называть с полным правом!) лог ческ х операций.

Сдизъюнкц я. помощью их различных композиций получаются любые друг е булевы функции. Это означает, что система из данных трех ло-

Итак, основу м роздания булевых функций могут составлять всего лишь три простейш е логические операции – инверсия, конъюнкция и

х операц й является функционально полной системой булевых

схем: НЕлюбую, И, ИЛИ, достаточно лишь соединить их выводы соответствующим образом.

функц й [1, с. 62 – 64].

Примеры построения совершенных д.н.ф. по заданным облас-

которая, как показано выше, равна троичному вектору 1ХХ, записанному здесь в виде вектор-столбца. Согласно (1.12) получим формулу

Такое сокращение словосочетания дизъюнктивная нормальная форма считается общепринятым, так же как и к.н.ф. – конъюнктивная нормальная форма, определение которой будет дано позже.

12

воря, любая булева функция есть композиция одной изначальной функции – стрелки Пирса (штриха Шафера).

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

Унарную функцию (одноместный предикат) можно получить из бинарной (двуместного предиката) с помощью подстановки вместо од-

рассмотримx 0. Тогда на своем входе стрелка Пирса и штрих Шеффера имеют пару 0,0 . Данная вершина принадлежит области истинности данных

Следовательноработают, на выходе получается единица, значение противоположное значению x. Теперь пусть x 1. В этом случае на входе у на-

функц й (см. та л. 1.1, первый элемент строк y9 и y15 соответственно).

ших функций удет пара 1,1 , принадлежащая их области ложности (см. табл. 1.1, четвертый элемент строк y9 и y15 соответственно), т.е. на

Эти формулы можно представить в виде логических схем (рис. 1.5 и 1.6). На них операции « » и « » изображены в виде черного ящика с двумя входами и одним выходом. Спаяв два входа в один, мы получили из них устройство, выполняющее функцию инверсии.

14

Теперь рассмотрим действие формулы x1 x1 x2 x2 . Ее логическая схема приведена на рис. 1.7.

Следовательно, область истинности данной формулы та же, что и у дизъюнкции (см. табл. 1.2), а значит справедливо следующее равенство

x1 x2 x1 x2 x1 x2 .

15