Линейная булева функция

Линейная булева функция — булева функция, полином Жегалкина которой имеет первую степень.Шаблон:Sfn Более развёрнуто булева функция $f(x_1,\dots ,x_n)$ называется линейной, если она выражается в виде:

$f(x_1,\dots ,x_n)=a_1{x}_1\oplus \dots \oplus a_n{x}_n\oplus a_0$Шаблон:Sfn

Примеры линейных булевых функций: тождественный $0$, тождественная $1$, тождественная функция, отрицание, исключающее или, эквиваленция. Конъюнкция и дизъюнкция линейными не являются.Шаблон:Sfn

Линейные функции допускают также двойственное определение. Булева функция является линейной тогда и только тогда, когда её кополином Жегалкина имеет первую степень. Линейные функции легко переводятся между представлениями в виде полинома и кополинома при помощи следующих свойств:

• $x\leftrightarrow y=x\oplus y\oplus 1$
• $x\oplus y=x\leftrightarrow y\leftrightarrow 0$

Все коэффициенты при переменных у полинома и кополинома линейной функции равны; свободные члены равны, когда в полиноме (кополиноме) чётное число переменных с ненулевыми коэффициентами, а при нечётном — свободные члены противоположны.

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

Линейная булева функция без фиктивных переменных не меняет значение внутри одного слоя булева куба, однако на соседних слоях они противоположны. Поэтому линейная функция без фиктивных имеет характерное геометрическое представление: она просто чередует своё значение на слоях булева куба.

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

Множество всех линейных булевых функций образует замкнутый класс,Шаблон:Sfn предполный в $P_2$. Таким образом, класс линейных функций является одним из пяти предполных классов булевой логики. Класс линейных функций обозначается $L$Шаблон:Sfn или $L_1$Шаблон:Sfn (обозначение Поста). В $L$ четыре предполных класса: $L\cap T_0$ (линейные сохраняющие $0$)Шаблон:Sfn, $L\cap T_1$ (линейные сохраняющие $1$)Шаблон:Sfn, $L\cap S$ (линейные самодвойственные)Шаблон:Sfn и $U$ (класс всех функций с не более чем одной существенной переменной)Шаблон:Sfn. Любой собственный подкласс $L$ может быть достроен до предполного в $L$.Шаблон:Sfn Как и для всех замкнутых классов в $P_2$, для класса линейных функций верен аналог малой теоремы Поста: система линейных функций полна в $L$ тогда и только тогда, когда в ней содержится несамодвойственная функция, не сохраняющая $0$ функция, не сохраняющая $1$ функция и функция, имеющая не менее двух существенных переменных.

Двойственная к линейной функции тоже линейна, то есть класс $L$ — самодвойственнен. Примеры базисов в $L$: $\{\oplus ,1\},\{\leftrightarrow ,0\}$,Шаблон:Sfn$\{x\oplus y\oplus z,0,1\}$. Минимальное количество функций в базисе — $2$, максимальное — $3$. В $L$ нет шефферовой функции. Порядок класса линейных функций равен $2$.Шаблон:Sfn

Линейная функция сохраняет $0$ тогда и только тогда, когда в её полиноме Жегалкина свободным членом является $0$. Линейная функция сохраняет $1$ тогда и только тогда, когда в её полиноме Жегалкина нечётное число ненулевых слагаемых. Двойственно, линейная функция сохраняет $1$ тогда и только тогда, когда в её кополиноме Жегалкина свободным членом является $1$. Линейная функция сохраняет $0$ тогда и только тогда, когда в её кополиноме Жегалкина нечётное число неединичных слагаемых.

Линейная функция самодвойственна тогда и только тогда, когда она содержит нечётное число существенных переменных. Эквивалентно: линейная функция самодвойственна тогда и только тогда, когда в её полиноме (кополиноме) нечётное число переменных с ненулевым коэффициентом. Поэтому, если линейная функция не сохраняет $0$ и не сохраняет $1$, то она самодвойственна. Отсюда следует ограничение на минимальное число функций в базисе. Монотонные линейные функции исчерпываются постоянными функциями и селекторами.

Леммы о нелинейных функциях

Первая лемма о нелинейной функции. Из нелинейной функции, отрицания, тождественной $1$ и тождественного $0$ можно получить конъюнкцию.Шаблон:Sfn

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

Вторая лемма о нелинейной функции. Из нелинейной функции можно получить нелинейную функцию от трёх переменных $f(x,y,z)$ такую, что $f(1,x,y)$ тоже нелинейна.Шаблон:Sfn

Двойственное утверждение (что из нелинейной функции можно получить нелинейную функцию от трёх переменных $f(x,y,z)$ такую, что $f(0,x,y)$ тоже нелинейна) тоже верно. Из этой леммы следует, что из нелинейной функции и одной из констант можно получить нелинейную функцию от двух переменных. Данная лемма используется, например, в доказательстве малой теоремы Поста для класса самодвойственных функций.

См. также

• Предполные классы
• Монотонная булева функция

Литература

• Шаблон:Книга
• Шаблон:Cite conference
• Шаблон:Cite journal
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга