Булева функция, сохраняющая константу

Булева функция, сохраняющая 0, — булева функция ${\displaystyle f\colon E_{2}^{n}\to E_{2}}$ такая, что ${\displaystyle f(0,\ldots ,0)=0}$.^[1]

Булева функция, сохраняющая 1, — булева функция ${\displaystyle f\colon E_{2}^{n}\to E_{2}}$ такая, что ${\displaystyle f(1,\ldots ,1)=1}$.^[2]

Множество булевых функций, сохраняющих 0, образует замкнутый класс, предполный в ${\displaystyle P_{2}}$. Множество булевых функций, сохраняющих 1, тоже образует замкнутый класс, предполный в ${\displaystyle P_{2}}$.^[3]

Всего существует ${\displaystyle 2^{2^{n}-1}}$ функций от ${\displaystyle n}$ переменных, сохраняющих 0, и столько же функций от ${\displaystyle n}$ переменных, сохраняющих 1.^[2] Примеры функций, сохраняющих 0: ${\displaystyle 0,x,\land ,\lor ,\oplus ,\not \leftarrow ,\not \rightarrow ,h_{2}}$ (функция голосования).^[4] Примеры функций, сохраняющих 1: ${\displaystyle 1,x,\land ,\lor ,\leftrightarrow ,\rightarrow ,\leftarrow ,h_{2}}$ (функция голосования). Двойственная функции к функции, сохраняющей 0, сохраняет 1. Двойственная функции к функции, сохраняющей 1, сохраняет 0. Если функция сохраняющая константу самодвойственна, то она сохраняет и другую константу.

Булева функция сохраняет 0 тогда и только тогда, когда она является ${\displaystyle \alpha }$- или ${\displaystyle \gamma }$- функцией (то есть отождествление всех переменных функции ${\displaystyle f(x,\ldots ,x)=x}$ или ${\displaystyle f(x,\ldots ,x)=0}$). Булева функция сохраняет 1 тогда и только тогда, когда она является ${\displaystyle \alpha }$- или ${\displaystyle \beta }$- функцией (${\displaystyle f(x,\ldots ,x)=x}$ или ${\displaystyle f(x,\ldots ,x)=1}$). В старой литературе именно это определение использовалось как основное.^[5]

Булева функция сохраняет ${\displaystyle 0}$ тогда и только тогда, когда её полином Жегалкина не содержит свободного члена. Булева функция сохраняет ${\displaystyle 1}$ тогда и только тогда, когда её кополином Жегалкина не содержит свободного члена (то есть он равен ${\displaystyle 1}$, что для кополинома одно и то же). Из этого моментально следует, что ${\displaystyle \{\land ,\oplus \}}$ порождает всё ${\displaystyle T_{0}}$, а ${\displaystyle {\lor ,\leftrightarrow }}$ порождает всё ${\displaystyle T_{1}}$.^[5]

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

Примеры базисов в ${\displaystyle T_{0}}$: ${\displaystyle \{\land ,\oplus \},\{\lor ,\oplus \},\{\lor ,\not \leftarrow \},\{\oplus ,\not \leftarrow \},}$^[5]${\displaystyle \{x{\overline {y}}\lor y{\overline {z}}\},\{0,x\oplus y\oplus z,h_{2}\}}$. Минимальное количество элементов в базисе — ${\displaystyle 1}$, максимальное — ${\displaystyle 3}$. В ${\displaystyle T_{0}}$ есть шефферовы функции, например ${\displaystyle x{\overline {y}}\lor y{\overline {z}}}$.

${\displaystyle T_{0}}$ содержит в себе счётное число замкнутых подклассов. Монотонная функция сохраняет 0 тогда и только тогда, когда она тождественно не равна единице. Линейная функция сохраняет 0 тогда и только тогда, когда её свободный член в полиноме Жегалкина равен ${\displaystyle 0}$ (или число не равных тождественно ${\displaystyle 1}$ членов в кополиноме нечётно). Самодвойственная функция сохраняет ${\displaystyle 0}$ тогда и только тогда, когда она сохраняет ${\displaystyle 1}$. Самодвойственная функция сохраняет ${\displaystyle 0}$ (а значит и ${\displaystyle 1}$) тогда и только тогда, когда её ${\displaystyle x_{i}}$-компонента сохраняет ${\displaystyle 1}$ (переменную ${\displaystyle x_{i}}$ можно выбрать произвольно). Самодвойственная функция сохраняет ${\displaystyle 0}$ (а значит и ${\displaystyle 1}$) тогда и только тогда, когда её ${\displaystyle {\overline {x_{i}}}}$-компонента сохраняет ${\displaystyle 0}$ (переменную ${\displaystyle x_{i}}$ можно выбрать произвольно).

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

Примеры базисов в ${\displaystyle T_{1}}$: ${\displaystyle \{\lor ,\leftrightarrow \},\{\land ,\leftrightarrow \},\{\land ,\rightarrow \},\{\leftrightarrow ,\rightarrow \},\{(x\lor {\overline {y}})(y\lor {\overline {z}})\},\{1,x\leftrightarrow y\leftrightarrow z,m\}}$. Минимальное количество элементов в базисе — ${\displaystyle 1}$, максимальное — ${\displaystyle 3}$. В ${\displaystyle T_{1}}$ есть шефферовы функции, например ${\displaystyle (x\lor {\overline {y}})(y\lor {\overline {z}})}$.

${\displaystyle T_{1}}$ содержит в себе счётное число замкнутых подклассов. Монотонная функция сохраняет 1 тогда и только тогда, когда она тождественно не равна нулю. Линейная функция сохраняет 1 тогда и только тогда, когда её свободный член в кополиноме Жегалкина равен ${\displaystyle 1}$ (или число ненулевых членов в полиноме нечётно). Самодвойственная функция сохраняет ${\displaystyle 1}$ тогда и только тогда, когда она сохраняет ${\displaystyle 0}$. Самодвойственная функция сохраняет ${\displaystyle 1}$ (а значит и ${\displaystyle 0}$) тогда и только тогда, когда её ${\displaystyle x_{i}}$-компонента сохраняет ${\displaystyle 1}$ (переменную ${\displaystyle x_{i}}$ можно выбрать произвольно). Самодвойственная функция сохраняет ${\displaystyle 1}$ (а значит и ${\displaystyle 0}$) тогда и только тогда, когда её ${\displaystyle {\overline {x_{i}}}}$-компонента сохраняет ${\displaystyle 0}$ (переменную ${\displaystyle x_{i}}$ можно выбрать произвольно).

Лемма о функции, не сохраняющей 0. Из функции, не сохраняющей 0, можно получить константу ${\displaystyle 1}$ или отрицание.^[7]

Лемма о функции, не сохраняющей 1. Из функции, не сохраняющей 1, можно получить константу ${\displaystyle 0}$ или отрицание.^[8]

Оба утверждения являются следствием того факта, что ${\displaystyle \alpha }$- и ${\displaystyle \gamma }$-функции сохраняют 0, и ${\displaystyle \alpha }$- и ${\displaystyle \beta }$-функции сохраняют 1. Чтобы получить указанные в леммах функции достаточно отождествить переменные у исходной функции.^[9]

• Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста (рус.) / под ред. В. В. Донченко. — М.: Наука, 1966. — 120 с. — 10 000 экз.
• Яблонский С. В. Введение в дискретную математику. — 5-е изд. — М.: Высшая школа, 2008. — 384 с. — ISBN 978-5-06-005943-4.