Линейные функции

Напомним, что линейными называются функции, представимые в виде , где a₁,..., a _{n +1} - двоичные коэффициенты при переменных и свободном члене, равном 1.

Класс линейных функций обозначается как L.

Из установленного способа представления линейных функций следует, что существует ровно 2 ^{n +1} различных линейных функций, зависящих от n переменных. Действительно, записи линейных функций являются частным случаем полиномов Жегалкина, поэтому представление всякой линейной функции в виде единственное. Поэтому линейных функций от n переменных ровно столько, сколько имеется способов составления различных записей вида: .

Класс L является замкнутым, поскольку преобразование всякой суперпозиции линейных функций к виду полинома Жегалкина не приводит к появлению нелинейных слагаемых.

Замечание. Только две линейные функции n переменных существенно зависят от всех своих переменных:

и .

Всякая другая линейная функция n переменных, полином Жегалкина для которых не содержит вхождения некоторых переменных, имеет несущественные переменные.

Все 4 функции одной переменной: 0, 1, x и являются линейными.

Простейшим примером нелинейной функции можно считать x ₁& x ₂, поскольку ее представление в виде полинома Жегалкина содержит одно произведение переменных. Покажем, что эта простейшая нелинейная функция может быть выражена из любой нелинейной функции.

Лемма (О нелинейной функции)

Если f (x ₁,..., x _n) L, то подстановкой вместо переменных этой функции функций-констант 0, 1, тождественных функции x и отрицанию , а также применением отрицания к f можно получить функцию .