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

Булевой функцией (БФ) называется функция , у которой аргументы пробегают множество и которая на любом наборе значений аргументов принимает значение из того же множества . Например, функция вида где , является БФ.

Для удобства описания переключательных схем БФ обычно представляют в одной из стандартных форм: дизъюнктивной нормальной форме (ДНФ) или совершенной дизъюнктивной нормальной форме (СДНФ); конъюнктивной нормальной форме (КНФ) или совершенной конъюнктивной нормальной форме (СКНФ).

Представим произвольную БФ в СДНФ.

Введем следующие обозначения: Общее обозначение: Из вторых свойств идемпотентности и отрицания соответственно следует

Обобщая два последних тождества, получаем

Воспользовавшись первым свойством отрицания, можно осуществить следующий переход:

В результате обобщения получаем разложение Шеннона по :

Последовательно раскладывая по получаем:

Последнее соотношение является представлением БФ в СДНФ. Иначе говоря, БФ в СДНФ представляется в виде суммы произведений переменных или их отрицаний, причем ни в какое произведение не входит дважды одна и та же переменная. Если произведения не обязательно содержат все переменные – БФ представлена в виде ДНФ. Например, представление БФ

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

является ДНФ.

Представим произвольную БФ в СКНФ.

Разложим инвертированную БФ в СДНФ:

Выполним отрицание обеих частей и применим правило де Моргана:

Так как то можно записать:

Очевидно, если то В результате имеем:

Последнее соотношение является представлением БФ в СКНФ. Иначе говоря, БФ в СКНФ представляется в виде произведения сумм переменных или их отрицаний, причем ни в какую сумму не входит дважды одна и та же переменная. Если суммы не обязательно содержат все переменные – БФ представлена в виде КНФ. Например, представление БФ

является СКНФ, а полученное в результате перемножения содержимого двух первых скобок выражение

является КНФ.

Для перехода от СДНФ к СКНФ необходимо последовательно выполнить следующие действия: суммировать все произведения, не входящие в СДНФ; заменить все знаки умножения знаками произведения и наоборот; проинвертировать все переменные. В нашем примере БФ зависит от трех переменных, поэтому ее полная СДНФ будет равна

В результате исключения всех имеющихся в СДНФ произведений получаем

.

Заменяем знаки:

.

В результате инвертирования всех переменных получаем СКНФ:

.

Оказалось, что рассмотренные примеры СДНФ и СКНФ являются различными представлениями одной и той же БФ. Для перехода от СКНФ к СДНФ необходимо выполнить все перечисленные действия в обратной последовательности.