Класс линейных булевых функций

Сумма по модулю два монотонных элементарных конъюнкций называется полиномом Жегалкина. Наибольший ранг монотонных элементарных конъюнкций, входящих в полином Жегалкина, называется его степенью. Булева функция, представимая в виде полинома Жегалкина степени не выше первой, называется линейной. В соответствии с этим определением константы 0 и 1 отнесем к линейным булевым функциям. Множество всех линейных булевых функций обозначается через L. Этому классу принадлежат тождественная функция, функция отрицания, сумма по модулю два, эквиваленция. Конъюнкция, дизъюнкция, импликация – нелинейные булевы функции. Точно так же, как доказывали ранее, можно доказать следующие теоремы.

ТЕОРЕМА. Число всех различных n- местных линейных булевых функций равно

ТЕОРЕМА. Класс линейных булевых функций замкнут.

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

Таблица 4.1