Линейная булева функция (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$, тождественная функция, отрицание, исключающее или, эквиваленция. Конъюнкция и дизъюнкция линейными не являются.

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

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

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

Множество всех линейных булевых функций образует замкнутый класс, предполный в $P_{2}$. Таким образом, класс линейных функций является одним из пяти предполных классов булевой логики.

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

См. также

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

Литература

• Капитонова Ю. В., Кривой С. Л., Летичевский А. А. Лекции по дискретной математике. — СПб.: БХВ-Петербург, 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= (справка)