9.2. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ БУЛЕВЫХ ФУНКЦИИ

Выше упоминалось о существовании аналитических форм представления булевых функций, были приведены простейшие примеры. Здесь рассмотрим универсальные (канонические) формы представления, дающие возможность получить аналитическую форму непосредственно по таблице истинности для произвольной булевой функции. Эта форма в дальнейшем может быть упрощена. Поскольку между множеством аналитических представлений и множеством схем, реализующих булеву функцию, существует взаимнооднозначное соответствие, отыскание канонической формы представления булевой функции является начальным этапом синтеза схемы, ее реализующей. Наиболее широкое распространение получила совершенная дизъюнктивная нормальная форма Прежде чем перейти к ее изучению, приведем определение конституенты единицы — понятия, которым будем широко пользоваться в дальнейшем.

Определение. Конституентой единицы называется функция принимающая значение 1 только на единственном наборе.

Конституента единицы записывается как логическое произведение различных булевых переменных, некоторые из них могут быть с отрицаниями (это положение может быть строго доказано Например, — элементарное логическое произведение, являющееся конституентой единицы переменных принимает значение 1 на единственном наборе 1001. Понятно, что на остальных 15 наборах эта конституента единицы равна нулю.

Если вспомнить, что дизъюнкция равна 1, когда бы одна из переменных принимает значение 1, то можно легко выразить любую булеву функцию как дизъюнкцию конституент единицы, соответствующих тем наборам, на которых функция равна I. В более общем

Таблица 9.9

виде это можно записать следующим образом:

где

Эта форма и есть СДНФ. Заметим, что наборы, на которых функция принимает значение часто называются единичными, остальные — нулевыми наборами. Выписывать в СДНФ имеет смысл только конституенты единицы, соответствующие единичным наборам,

Пример. Выпишем СДНФ для функций, заданных таблицей истинности <табл. 9.9).

Функция нам знакома как сумма по модулю 2 трех переменных

Функция называется мажоритарной (она принимает значение, которое принимает большинство переменных) и обозначается знаком

Другая известная форма носит название совершенной конъюнктивной нормальной формы (СКНФ). Она строится аналогично СДНФ.

Определение. Конституентой нуля называется функция, принимающая значение 0 на единственном наборе.

Конституента нуля записывается в виде элементарной дизъюнкции всех переменных. Каждому набору соотнетствует своя конституента 0, Например, набору ОНО переменных соответствует конституента нуля представляется как конъюнкция конституент нуля, соответствующих нулевым наборам функции.

Пример. Для рассмотренных выше функций (см. табл. 9.9) построим СКНФ:

Легко видеть, что в СДНФ можно заменить операцию дизъюнкции операцией суммы по модулю 2, причем равенство сохранится. Эта форма называется совершенной полиномиальной нормальной формой (СПНФ). Для нашего примера

Если в СПНФ заменить все переменные с отрицаниями в соответствии с соотношением (справедливость которого можно

легко установить, раскрыв скобки и приведя подобные члены, имея в виду, что два одинаковых члена в сумме равны 0), то получится канонический нолином Жегалкина вида

где

Пример. Для тех же функций найдем канонический полином Жегалина:

Аналогично получаем

В булевой алгебре широко используется разложение Шеннона — формула, позволяющая перейти к представлению функции от -переменных через функции от -переменных!

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

Отметим, что если произвести такое разложение по всем переменным, получится СДНФ.