Линейная булева функция (Lnuywugx Qrlyfg srutenx)

Линейная булева функция — булева функция, полином Жегалкина которой имеет первую степень. Более развёрнуто булева функция $f(x_{1},\ldots ,x_{n})$ называется линейной, если она выражается в виде:

$f(x_{1},\ldots ,x_{n})=a_{1}x_{1}\oplus \ldots \oplus a_{n}x_{n}\oplus a_{0}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

• Капитонова Ю. В., Кривой С. Л., Летичевский А. А. Лекции по дискретной математике. — СПб.: БХВ-Петербург, 2004. — С. 112. — ISBN 5-94157-546-7.
• Couceiro, Miguel; Lehtonen, Erkko (Aug 2020). Linearly definable classes of Boolean functions. ALGOS 2020 - 1st International Conference on Algebras, Graphs and Ordered Sets. Nancy, France.
• Filmus, Yuval (Published 13 December 2021). "Boolean Functions on Sn Which Are Nearly Linear". DISCRETE ANALYSIS. 2021 (25): 27. {{cite journal}}: Проверьте значение даты: |date= (справка)
• Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — 384 с.
• Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. — М.: Наука, 1966. — 120 с.
• Lau D. Function Algebtas on Finite Sets. — Springer, 2006. — 668 с.