Меню Главная Случайная статья Настройки Булева функция, сохраняющая константу Материал из https://ru.wikipedia.org Булева функция, сохраняющая 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] Содержание 1 Класс функций, сохраняющих 0 2 Класс функций, сохраняющих 1 3 Лемма о функции, не сохраняющей константу 4 Примечания 5 Литература Класс функций, сохраняющих 0 Множество всех функций, сохраняющих 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 Множество всех функций, сохраняющих 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] Примечания 1 2 3 Яблонский, 2008, с. 33-34. 1 2 Яблонский, 2008, с. 34. Яблонский, 2008, с. 41. Класс булевых функций, сохраняющих константу 0 1 2 3 4 5 Яблонский, Гаврилов, Кудрявцев, 1966, с. 46. 1 2 Яблонский, Гаврилов, Кудрявцев, 1966, с. 101. 15.1. Класс булевых функций, сохраняющих константу 0 . Дата обращения: 3 января 2025. Архивировано 3 января 2025 года. Полнота системы булевых функций, с. 6 Полнота системы булевых функций, с. 7 Литература Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста (рус.) / под ред. В. В. Донченко. — М.: Наука, 1966. — 120 с. — 10 000 экз.