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

Булева функция, сохраняющая 0, — булева функция $E_2^n\to E_2$ такая, что $f(0,\dots ,0)=0$.Шаблон:Sfn

Булева функция, сохраняющая 1, — булева функция $E_2^n\to E_2$ такая, что $f(1,\dots ,1)=1$.Шаблон:Sfn

Множество булевых функций, сохраняющих 0, образует замкнутый класс, предполный в $P_2$. Множество булевых функций, сохраняющих 1, тоже образует замкнутый класс, предполный в $P_2$.Шаблон:Sfn

Всего существует $2^{2^n-1}$ функций от $n$ переменных, сохраняющих 0, и столько же функций от $n$ переменных, сохраняющих 1.Шаблон:Sfn Примеры функций, сохраняющих 0: $0,x,\wedge ,\vee ,\oplus ,\leftarrow ̸,\to ̸,h_2$ (функция голосования). Примеры функций, сохраняющих 1: $1,x,\wedge ,\vee ,\leftrightarrow ,\to ,\leftarrow ,h_2$ (функция голосования). Двойственная функции к функции, сохраняющей 0, сохраняет 1. Двойственная функции к функции, сохраняющей 1, сохраняет 0. Если функция сохраняющая константу самодвойственна, то она сохраняет и другую константу.

Булева функция сохраняет 0 тогда и только тогда, когда она является $\alpha$- или $\gamma$- функцией (то есть отождествление всех переменных функции $f(x,\dots ,x)=x$ или $f(x,\dots ,x)=0$). Булева функция сохраняет 1 тогда и только тогда, когда она является $\alpha$- или $\beta$- функцией ($f(x,\dots ,x)=x$ или $f(x,\dots ,x)=1$). В старой литературе именно это определение использовалось как основное.Шаблон:Sfn

Булева функция сохраняет $0$ тогда и только тогда, когда её полином Жегалкина не содержит свободного члена. Булева функция сохраняет $1$ тогда и только тогда, когда её кополином Жегалкина не содержит свободного члена (то есть он равен $1$, что для кополинома одно и то же). Из этого моментально следует, что $\{\wedge ,\oplus \}$ порождает всё $T_0$, а $\vee ,\leftrightarrow$ порождает всё $T_1$.Шаблон:Sfn

Класс функций, сохраняющих 0

Множество всех функций, сохраняющих 0, образует замкнутый класс, предполный в $P_2$. Таким образом, класс функций, сохраняющих 0, является одним из пяти предполных классов булевой логики. Класс функций, сохраняющих 0, обозначается $T_0$Шаблон:Sfn или $C_3$Шаблон:Sfn (обозначение Поста). В $T_0$ четыре предполных класса: $T_0\cap T_1$ (класс функций, сохраняющих обе константы), $T_0\cap M$ (класс монотонных функций, сохраняющих 0), $T_0\cap L$ (класс линейных функций, сохраняющих 0) и $T_{0,2}$ (класс функций, удовлетворяющий условию $⟨1^2⟩$).Шаблон:Sfn Любой собственный подкласс $T_0$ может быть достроен до предполного в $T_0$. Как и для всех замкнутых классов в $P_2$, для класса функций, сохраняющих 0, верен аналог малой теоремы Поста: система функций, сохраняющих 0, полна в $T_0$ тогда и только тогда, когда в ней содержится не сохраняющая $1$ функция, не монотонная функция, не линейная функция и функцию, не удовлетворяющий условию $⟨1^2⟩$.

Примеры базисов в $T_0$: $\{\wedge ,\oplus \},\{\vee ,\oplus \},\{\vee ,\leftarrow ̸\},\{\oplus ,\leftarrow ̸\},$Шаблон:Sfn$\{x\bar{y}\vee y\bar{z}\},\{0,x\oplus y\oplus z,h_2\}$. Минимальное количество элементов в базисе — $1$, максимальное — $3$. В $T_0$ есть шефферовы функции, например $x\bar{y}\vee y\bar{z}$.

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

Класс функций, сохраняющих 1

Множество всех функций, сохраняющих 1, образует замкнутый класс, предполный в $P_2$. Таким образом, класс функций, сохраняющих 1, является одним из пяти предполных классов булевой логики. Класс функций, сохраняющих 1, обозначается $T_1$Шаблон:Sfn или $C_2$Шаблон:Sfn (обозначение Поста). В $T_1$ четыре предполных класса: $T_0\cap T_1$ (класс функций, сохраняющих обе константы), $T_1\cap M$ (класс монотонных функций, сохраняющих 1), $T_1\cap L$ (класс линейных функций, сохраняющих 1) и $T_{1,2}$ (класс функций, удовлетворяющий условию $⟨0^2⟩$).Шаблон:Sfn Любой собственный подклассa $T_1$ может быть достроен до предполного в $T_1$. Как и для всех замкнутых классов в $P_2$, для класса функций, сохраняющих 1, верен аналог малой теоремы Поста: система функций, сохраняющих 1, полна в $T_1$ тогда и только тогда, когда в ней содержится не сохраняющая $0$ функция, не монотонная функция, не линейная функция и функцию, не удовлетворяющий условию $⟨0^2⟩$.

Примеры базисов в $T_1$: $\{\vee ,\leftrightarrow \},\{\wedge ,\leftrightarrow \},\{\wedge ,\to \},\{\leftrightarrow ,\to \},\{(x\vee \bar{y})(y\vee \bar{z})\},\{1,x\leftrightarrow y\leftrightarrow z,m\}$. Минимальное количество элементов в базисе — $1$, максимальное — $3$. В $T_1$ есть шефферовы функции, например $(x\vee \bar{y})(y\vee \bar{z})$.

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

Лемма о функции, не сохраняющей константу

Лемма о функции, не сохраняющей 0. Из функции, не сохраняющей 0, можно получить константу $1$ или отрицание.

Лемма о функции, не сохраняющей 1. Из функции, не сохраняющей 1, можно получить константу $0$ или отрицание.

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

Литература

• Шаблон:Книга
• Шаблон:Книга