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

Напомним, что линейными называются функции, представимые в виде , где ₁, . . . , _n+1  двоичные коэффициенты при переменных и свободном члене, равном 1.

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

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

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

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

и .

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

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

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

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

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

Доказательство

Пусть f(x₁ , . . . , x_n) L.

Возьмем полином Жегалкина R для f. Так как f  это нелинейная функция, то в полиноме R содержится слагаемое, включающее произведение некоторых двух переменных. Без ограничения общности можно считать, что такое произведение содержит вхождения переменных x₁ и x₂.

(Если все произведения двух и большего числа переменных не содержат одновременно эти переменные, то необходимо произвести соответствующее переименование переменных в f, используя подстановки переменных вместо переменных функции.)

Сгруппируем слагаемые в R и, вынося переменные x₁ и x₂ за скобки, представим его в виде

(1).

Здесь полином R₁ содержит хотя бы одно ненулевое слагаемое и поэтому представляет булевскую функцию, отличную от тождественного нуля.

Пусть . Подставим вместо переменных x₃, . . . , x_n конкретные значения . Тогда имеет место равенство:

= (2)

Здесь и .

Заменим x₁ на x₁ +  и х₂ на x₂ +. При этом, если  или , равно нулю, то соответствующая переменная не заменяется. В противном случае соответствующая переменная заменяется на отрицание этой переменной.

В результате такой замены выражение (2) преобразуется к виду

. (3)

Если , то функция x₁&x₂ уже получена.

В противном случае применим отрицание к функции вида (3) и также получим x₁&x₂.

Доказательство окончено.

Рассмотрим применение доказанной леммы к нелинейным функциям.

Пусть f = x₁  (x₂  x₃). Тогда полином Жегалкина для f имеет вид

f = x₁x₂x₃ + x₁x₂ + 1, т.е. x₁x₂ (x₃ + 1) + 1.

Полином равен единице при x₃ = 0. Тогда f(x₁, x₂, 0) = x₁x₂ + 1. Поэтому x₁  x₂.

Упражнение.

1.Доказать утверждение, обратное утверждению леммы о нелинейной функции.

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