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

${\displaystyle f(x_{1},\ldots ,x_{n})=a_{1}x_{1}\oplus \ldots \oplus a_{n}x_{n}\oplus a_{0}}$^[2]

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

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

• ${\displaystyle x\leftrightarrow y=x\oplus y\oplus 1}$
• ${\displaystyle x\oplus y=x\leftrightarrow y\leftrightarrow 0}$

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

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

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

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

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

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

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

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

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

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

Двойственное утверждение (что из нелинейной функции можно получить нелинейную функцию от трёх переменных ${\displaystyle f(x,y,z)}$ такую, что ${\displaystyle 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 с.

Это заготовка статьи. Помогите Википедии, дополнив её. Это примечание по возможности следует заменить более точным.