Нормальные формы и полиномы

Запишем по таблице истинности заданной функции совершенную дизъюнктивную нормальную форму (СДНФ). Для этого рассмотрим наборы, где функция принимает значение 1. В результате получим

Запишем по таблице истинности заданной функции совершенную конъюнктивную нормальную форму (СКНФ). Для этого рассмотрим наборы, где функция принимает значение 0 и возьмем каждый набор с отрицанием. В результате получим

.

Построим полином Жегалкина, рассмотрев наборы, где булева функция принимает значение 1, и воспользовавшись формулой

.

В формуле надо раскрыть скобки и упростить выражения с помощью соотношений , , .

Для заданной функции получим

Степень полинома – 3.

Проверим правильность преобразований с помощью таблицы истинности.

f

Результат совпадает с исходной таблицей истинности.

Все три представления булевой функции эквивалентны. Далее будем рассматривать булеву функцию в классе ДНФ и полиномов Жегалкина.