Линейная булева функция — булева функция, полином Жегалкина которой имеет первую степень. Более развёрнуто булева функция называется линейной, если она выражается в виде:
Примеры линейных булевых функций: тождественный , тождественная , тождественная функция, отрицание, исключающее или, эквиваленция. Конъюнкция и дизъюнкция линейными не являются.
Линейные функции допускают также двойственное определение. Булева функция является линейной тогда и только тогда, когда её кополином Жегалкина имеет первую степень. Линейные функции легко переводятся между представлениями в виде полинома и кополинома при помощи следующих свойств:
Все коэффициенты при переменных у полинома и кополинома линейной функции равны; свободные члены равны, когда в полиноме (кополиноме) чётное число переменных с ненулевыми коэффициентами, а при нечётном — свободные члены противоположны.
Количество линейных функций переменных равно . Переменная линейной функции существенна тогда и только тогда, когда она входит в полином с ненулевым коэффициентом. Функция является линейной тогда и только тогда, когда значения функции на любых двух соседних по существенной переменной наборах отличаются. У любой линейной функции равное количество нулей и единиц.
Линейная булева функция без фиктивных переменных не меняет значение внутри одного слоя булева куба, однако на соседних слоях они противоположны. Поэтому линейная функция без фиктивных имеет характерное геометрическое представление: она просто чередует своё значение на слоях булева куба.
Класс линейных функций Множество всех линейных булевых функций образует замкнутый класс, предполный в . Таким образом, класс линейных функций является одним из пяти предполных классов булевой логики. Класс линейных функций обозначается или (обозначение Поста). В четыре предполных класса: (линейные, сохраняющие 0), (линейные сохраняющие 1), (линейные самодвойственные) и (класс всех функций с не более чем одной существенной переменной). Любой собственный подкласс может быть достроен до предполного в . Как и для всех замкнутых классов в , для класса линейных функций верен аналог малой теоремы Поста: система линейных функций полна в тогда и только тогда, когда в ней содержится несамодвойственная функция, не сохраняющая функция, не сохраняющая функция и функция, имеющая не менее двух существенных переменных.
Двойственная к линейной функции тоже линейна, то есть класс — самодвойственен. Примеры базисов в : ,. Минимальное количество функций в базисе — , максимальное — . В нет шефферовой функции. Порядок класса линейных функций равен .
Линейная функция сохраняет тогда и только тогда, когда в её полиноме Жегалкина свободным членом является . Линейная функция сохраняет тогда и только тогда, когда в её полиноме Жегалкина нечётное число ненулевых слагаемых. Двойственно, линейная функция сохраняет тогда и только тогда, когда в её кополиноме Жегалкина свободным членом является . Линейная функция сохраняет тогда и только тогда, когда в её кополиноме Жегалкина нечётное число неединичных слагаемых.
Линейная функция самодвойственна тогда и только тогда, когда она содержит нечётное число существенных переменных. Эквивалентно: линейная функция самодвойственна тогда и только тогда, когда в её полиноме (кополиноме) нечётное число переменных с ненулевым коэффициентом. Поэтому, если линейная функция не сохраняет и не сохраняет , то она самодвойственна. Отсюда следует ограничение на минимальное число функций в базисе. Монотонные линейные функции исчерпываются постоянными функциями и селекторами.
Леммы о нелинейных функциях Первая лемма о нелинейной функции. Из нелинейной функции, отрицания, тождественной и тождественного можно получить конъюнкцию.
Эта лемма используется в одном из доказательств малой теоремы Поста. Следствием из этой леммы является то, что из того же набора функций (нелинейной, отрицания и обеих констант) можно получить вообще любую булеву функцию.
Вторая лемма о нелинейной функции. Из нелинейной функции можно получить нелинейную функцию от трёх переменных такую, что тоже нелинейна.
Двойственное утверждение (что из нелинейной функции можно получить нелинейную функцию от трёх переменных такую, что тоже нелинейна) тоже верно. Из этой леммы следует, что из нелинейной функции и одной из констант можно получить нелинейную функцию от двух переменных. Данная лемма используется, например, в доказательстве малой теоремы Поста для класса самодвойственных функций.
См. также Предполные классы Монотонная булева функция
Примечания
Литература
Категория:Булева алгебра Категория:Теория дискретных функций