Меню Главная Случайная статья Настройки Замкнутый класс булевых функций Материал из https://ru.wikipedia.org Замкнутый класс в теории булевых функций — такое множество ${\displaystyle P}$ функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: ${\displaystyle [P]=P}$. Другими словами, любая функция, которую можно выразить формулой с использованием функций множества ${\displaystyle P}$, снова входит в это же множество[1]. В 1941 году Эмиль Пост представил полное описание всех замкнутых классов булевых функций[2]. Множество всех замкнутых классов, упорядоченное отношением включения, образует решётку, называемую решёткой Поста[3]. Содержание 1 Определение 2 Примеры замкнутых классов 3 Свойства 4 Замыкание 5 Полные системы функций 5.1 Базис 5.2 Порядок 5.3 Критериальные системы 6 Список замкнутых классов 7 Примечания 8 Литература Определение Говорят, что функция ${\displaystyle f\in P_{2}}$ получена при помощи операции суперпозиции функций из множества ${\displaystyle F\subseteq P_{2}}$, если функция ${\displaystyle f}$ может быть получена из функций множества ${\displaystyle F}$ за конечное число шагов при помощью следующих операций: Перестеновка и отождествление переменных; Подстановка функций и переменных в качестве аргументов другой функции; Добавление и удаление фиктивных переменных. Если множество функций замкнуто относительно указанных операций, то оно называется замкнутым классом. В данном определении разрешается функциям иметь ноль аргументов, то есть быть нульарными[4]. В англоязычной литературе и некоторой русскоязычной зачастую используют другое определение, неэквивалентное данному. Замкнутому классу запрещают иметь нульарные функции и убирается требование замкнутости относительно операции удаления переменных. Замкнутые классы в этом определении идентичны замкнутым классам в первом, с точностью до нульарных функций[5]. Примеры замкнутых классов Простейшими замкнутыми классами являются класс всех булевых функций ${\displaystyle P_{2}}$[6] и пустое множество ${\displaystyle \varnothing }$[7]. Некоторые авторы не считают пустое множество замкнутым классом[8]; в таком случае множество всех замкнутых классов булевых функций с отношением включения не образуют решётку. Особо известными замкнутыми классами булевых функций являются следующие 5 классов: Класс ${\displaystyle T_{0}}$ функций, сохраняющих константу 0: ${\displaystyle T_{0}=\{\,f(x_{1},\dots ,x_{n})|f(0,\dots ,0)=0\,\}}$[9]. Класс ${\displaystyle T_{1}}$ функций, сохраняющих константу 1: ${\displaystyle T_{1}=\{\,f(x_{1},\dots ,x_{n})|f(1,\dots ,1)=1\,\}}$[9]. Класс ${\displaystyle S}$ самодвойственных функций: ${\displaystyle S=\{\,f(x_{1},\dots ,x_{n})|f({\overline {x_{1}}},\dots ,{\overline {x_{n}}})={\overline {f(x_{1},\dots ,x_{n})}}\,\}}$[10]. Класс ${\displaystyle M}$ монотонных булевых функций: ${\displaystyle M=\{\,f(x_{1},\dots ,x_{n})|\forall i(a_{i}\leq b_{i})\Rightarrow f(a_{1},\dots ,a_{n})\leq f(b_{1},\dots ,b_{n})\,\}}$[11]. Класс ${\displaystyle L}$ линейных булевых функций: ${\displaystyle L=\{\,f(x_{1},\dots ,x_{n})|f(x_{1},\dots ,x_{n})=a_{0}\oplus a_{1}x_{1}\oplus \dots \oplus a_{n}x_{n},a_{i}\in \{0,1\}\,\}}$[9]. Эти классы так известны, поскольку участвуют в формулировке критерия Поста. Любой замкнутый класс булевых функций, отличный от класса всех функций, вкладывается в хотя бы один из этих пяти классов[12]. Другими важными замкнутыми классами являются: Класс конъюнкций с константами ${\displaystyle K}$, представляющий собой множество функций вида ${\displaystyle c_{0}\wedge (c_{1}\vee x_{1})\wedge \ldots \wedge (c_{n}\vee x_{n})}$[13]. Класс дизъюнкций с константами ${\displaystyle D}$, представляющий собой множество функций вида ${\displaystyle c_{0}\vee (c_{1}\wedge x_{1})\vee \ldots \vee (c_{n}\wedge x_{n})}$[13]. Класс несущественных функций ${\displaystyle U}$, содержащий только константы, отрицания одного из своих аргументов и селекторы (функции, равные одному из своих аргументов на всех наборах их значений)[14]. Класс констант ${\displaystyle C}$, содержащий только константы[14]. Класс ${\displaystyle T_{1,m}}$ функций (m — любое натуральное, большее единицы число), удовлетворяющих условию ${\displaystyle \langle 0^{m}\rangle }$: для любых m наборов, на которых функция принимает нулевое значение, найдется переменная, также принимающая нулевое значение на всех этих наборах[14]. Класс ${\displaystyle T_{1,\infty }}$ функций, для которых выполнено условие ${\displaystyle \langle 0^{\infty }\rangle }$: ${\displaystyle f(x_{1},\ldots ,x_{n})\geq x_{i}}$, где ${\displaystyle x_{i}}$ — одна из переменных функции[15]. Класс ${\displaystyle T_{0,m}}$ функций (m — любое натуральное, большее единицы число), удовлетворяющих условию ${\displaystyle \langle 1^{m}\rangle }$: для любых m наборов, на которых функция принимает единичное значение, найдется переменная, также принимающая единичное значение на всех этих наборах[14]. Класс ${\displaystyle T_{0,\infty }}$ функций, для которых выполнено условие ${\displaystyle \langle 1^{\infty }\rangle }$: ${\displaystyle f(x_{1},\ldots ,x_{n})\leq x_{i}}$, где ${\displaystyle x_{i}}$ — одна из переменных функции[15]. Любой замкнутый класс булевых функций является пересечением конечного числа классов ${\displaystyle P_{2},T_{0},T_{1},S,M,L,K,D,U,C,T_{1,m},T_{0,m}}$, где ${\displaystyle m\in \{2,3,4\ldots ,\infty \}}$[16]. Свойства Пересечение любого числа замкнутых классов снова является замкнутым классом[17] (если не считать пустое множество замкнутым классом, то пересечение замкнутых классов является замкнутым классом тогда и только тогда, когда оно не пусто). Объединение замкнутых классов может замкнутым классом не являться (например объединение класса нулей и класса селекторов с отрицаниями не является замкнутым классом, поскольку отрицание нуля даст единицу). Замкнутый класс булевых функций, содержащий не только константы, обязательно содержит все селекторы. Дополнение замкнутого класса булевых функций до множества всех булевых функций ${\displaystyle P_{2}}$ замкнутым классом не является. Замыкание Замыканием (относительно суперпозиции) системы функций ${\displaystyle F}$ называется множество всех функций, которые могут быть получены из функций множества ${\displaystyle F}$ при помощи суперпозиции. Замыкание системы функций ${\displaystyle F}$ обозначается ${\displaystyle [F]}$.[18]. Замыкание любой системы функций является замкнутым классом. Система функций ${\displaystyle F}$ является замкнутым классом тогда и только тогда, когда ${\displaystyle F=[F]}$[19]. Класс ${\displaystyle [F]}$ является наименьшим по включению замкнутым классом, включающим ${\displaystyle F}$. Класс ${\displaystyle [F]}$ можно получить как пересечение всех замкнутых классов, содержащих ${\displaystyle F}$. Замыкание относительно суперпозиции является частым случаем теоретико-множественного замыкания, то есть для него выполнены следующие свойства: Любое множество является подмножеством своего замыкания: ${\displaystyle F\subseteq [F]}$. Замыкание подмножества является подмножеством замыкания: ${\displaystyle F\subseteq G\Rightarrow [F]\subseteq [G]}$. Следует заметить, что из строгого вложения множеств следует лишь нестрогое вложение их замыканий: ${\displaystyle F\subset G\Rightarrow [F]\subseteq [G]}$ Многократное применение операции замыкания эквивалентно однократному: ${\displaystyle [[F]]=[F]}$. Замыкание относительно суперпозиции также удовлетворяет свойству финитарности, то есть является алгебраическим: ${\displaystyle [F]=\bigcup _{G\in \Phi (F)}[G]}$, где ${\displaystyle \Phi (F)}$ — множество всех конечных подможеств ${\displaystyle F}$.[20] Полные системы функций Система функций ${\displaystyle F\in V}$ называется полной системой в замкнутом классе ${\displaystyle V}$, если любую функцию класса ${\displaystyle V}$ можно получить при помощи суперпозиции функций множества ${\displaystyle F}$. Эквивалентное определение: система ${\displaystyle F}$ полна в ${\displaystyle V}$, если ${\displaystyle [F]=V}$. Полную систему также называют порождающей системой и говорят, что она порождает класс ${\displaystyle V}$[21]. Примеры полных систем: В любом замкнутом классе ${\displaystyle V}$ сам класс ${\displaystyle V}$ является полной системой. Система ${\displaystyle \{\,\land ,\lor ,\lnot \,\}}$ является полной системой в классе всех булевых функций, так как любую функцию можно задать при помощи СДНФ, а ${\displaystyle 0=x\land {\overline {x}}}$[22]. Система ${\displaystyle \{\,\oplus ,1\,\}}$ является полной системой в классе линейных функций, так как любую линейную функцию можно задать при помощи полинома Жегалкина без конъюнкций, а ${\displaystyle 0=1\oplus 1}$. Система ${\displaystyle \{\,\land ,\lor ,0,1\,\}}$ является полной системой в классе монотонных функций, так как любую монотонную функцию можно задать при помощи сокДНФ без отрицаний. Функция, которая сама по себе образует полную систему в замкнутом классе ${\displaystyle V}$, называется шефферовой функцией в классе ${\displaystyle V}$. Штрих Шеффера и Стрелка Пирса являются шефферовыми функциями в классе всех булевых функций. Отрицание функции голосования является шефферовой функцией в классе самодвойственных функций. В классах монотонных функций и линейных функций шефферовых функций нет. Базис Полная система функций ${\displaystyle F}$ в замкнутом классе ${\displaystyle V}$ называется базисом в замкнутом классе ${\displaystyle V}$, если никакая собственная подсистема ${\displaystyle F}$ не является полной в ${\displaystyle V}$. Таким образом базис — это минимальная по включению полная система класса[10]. Приведённая выше система ${\displaystyle \{\,\land ,\lor ,\lnot \,\}}$, полная в классе всех булевых функций, не является базисом, поскольку ${\displaystyle \land }$ можно выразить через ${\displaystyle \lor ,\lnot }$ при помощи законов де-Моргана. Базисами в классе всех булевых функций являются системы ${\displaystyle \{\,\land ,\lnot \,\}}$ и ${\displaystyle \{\,\lor ,\lnot \,\}}$. Система ${\displaystyle \{\,\oplus ,1\,\}}$ является базисом в классе линейных функций. Система ${\displaystyle \{\,\land ,\lor ,0,1\,\}}$ является базисом в классе монотонных функций. У любого замкнутого класса булевых функций есть конечный базис. Все базисы всех замкнутых классов имеют не более четырёх функций. Порядок Идейно, порядок замкнутого класса есть минимальная арность функций базиса. Существует несколько определений порядка. В одном из определений сначала определяется порядок функции как количество её существенных переменных. Порядок базиса определяется как максимальный из порядков входящих в него функций. Порядок замкнутого класса определяется как минимальный из порядков его базисов. В другом определении порядок замкнутого класса определяется как минимальное число ${\displaystyle r}$ такое, что множество всех функций арности ${\displaystyle r}$ этого класса порождает весь этот класс. Если рассматривается суперпозиция с удалениями фиктивных переменных, то оба определения эквивалентны. Если же замкнутому классу разрешается иметь только функции положительной арности, то все классы, имеющие порядок 0 в первом определении, имеют порядок 1 во втором; других отличий нет. Первое определение используется в терминологии, в которой отождествляются функции, отличающиеся лишь фиктивными переменными. В такой терминологии не имеет смысла рассматривать общее количество аргументов, поэтому в качестве порядка функций рассматривается количество существенных переменных. Критериальные системы Система замкнутых подклассов ${\displaystyle {\mathcal {Q}}}$ класса ${\displaystyle V}$ называется критериальной в замкнутом классе ${\displaystyle Q}$, если каждый собственный подкласс ${\displaystyle V}$ вкладывается в некоторый класс из ${\displaystyle {\mathcal {Q}}}$[23]. Простейший пример критериальной системы для произвольного класса ${\displaystyle V}$ — множество всех собственных подклассов ${\displaystyle V}$. Критерий Поста устанавливает, что система классов ${\displaystyle \{\,T_{0},T_{1},S,M,L\,\}}$ является критериальной для класса всех булевых функций. Критериальная система класса ${\displaystyle V}$ называется минимальной, если никакая её собственная подсистема не является критериальной в ${\displaystyle V}$. Замкнутый класс ${\displaystyle U\subset V}$ называется предполным в замкнутом классе ${\displaystyle V}$, если для любой функции ${\displaystyle f\in V\setminus U}$ система ${\displaystyle V\cup \{f\}}$ является полной в ${\displaystyle V}$. У каждого замкнутого класса булевых функций конечное количество предполных классов, причём оно не больше 5. Для каждого замкнутого класса ${\displaystyle V}$ его собственный замкнутый подкласс ${\displaystyle U}$ можно дополнить до некоторого предполного в ${\displaystyle V}$. Минимальная критериальная система замкнутого класса булевых функций есть множество всех его предполных классов. Это позволяет сформулировать для каждого из замкнутых классов простой критерий полноты, состоящий в том, что система функций полна в этом классе тогда и только тогда, когда она полностью не лежит ни в одном из его предполных классов. Частный случай этого критерия для класса всех булевых функций называется критерием Поста или малой теорема Поста. Примеры минимальных критериальных систем: Для класса всех булевых функций минимальная критериальная система есть ${\displaystyle \{\,T_{0},T_{1},S,M,L\,\}}$. Для класса всех линейных функций минимальная критериальная система есть ${\displaystyle \{\,L\cap T_{0},L\cap T_{1},L\cap S,U\,\}}$. Для класса всех самодвойственных функций минимальная критериальная система есть ${\displaystyle \{\,S\cap T_{0},S\cap L\,\}}$. Список замкнутых классов В 1941 году Эмиль Пост привёл полное описание структуры замкнутых классов двузначной логики. Также Пост установил, что любой замкнутый класс может быть порожден конечным базисом[2]. Список всех замкнутых классов булевой логики представлен в следующей таблице. Таблица разделена на блоки по порядкам классов. Всего существует 4 класса порядка 0 (или 3 если не считать пустое множество замкнутым классом), 6 классов порядка 1, 20 классов порядков 2, 20 классов порядка 3 и по 8 классов для каждого из порядков больше 3. В столбце "П" указано обозначение Поста[24], в столбце "ЯГК" — обозначение Яблонского, Гаврилова и Кудрявцева[25], в столбце "У" — обозначение Угольникова[8] и в столбце "Л" — обозначение Лау[26]. Название П ЯГК У Л Примеры базисов Предполные классы Порядок 0 Пустое множество — ${\displaystyle \Lambda }$ — ${\displaystyle \varnothing }$ ${\displaystyle \varnothing }$ Нули ${\displaystyle R_{3}}$ ${\displaystyle O_{3}}$ ${\displaystyle C_{0}}$ ${\displaystyle C_{0}}$ ${\displaystyle \{\,0\,\}}$ Пустое множество. Единицы ${\displaystyle R_{2}}$ ${\displaystyle O_{2}}$ ${\displaystyle C_{1}}$ ${\displaystyle C_{1}}$ ${\displaystyle \{\,1\,\}}$ Пустое множество. Константы ${\displaystyle R_{9}}$ ${\displaystyle O_{7}}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle \{\,0,1\,\}}$ Класс нулей; Класс единиц. Порядок 1 Селекторы ${\displaystyle R_{1}}$ ${\displaystyle O_{1}}$ ${\displaystyle U_{01}}$ ${\displaystyle I}$ ${\displaystyle \{\,x\,\}}$ Пустое множество. Селекторы с нулями ${\displaystyle R_{8}}$ ${\displaystyle O_{6}}$ ${\displaystyle U_{0}}$ ${\displaystyle I\cup C_{0}}$ ${\displaystyle \{\,x,0\,\}}$ Класс селекторов; Класс нулей. Селекторы с единицами ${\displaystyle R_{6}}$ ${\displaystyle O_{5}}$ ${\displaystyle U_{1}}$ ${\displaystyle I\cup C_{1}}$ ${\displaystyle \{\,x,1\,\}}$ Класс селекторов; Класс единиц. Селекторы с константами ${\displaystyle R_{11}}$ ${\displaystyle O_{8}}$ ${\displaystyle MU}$ ${\displaystyle I\cup C}$ ${\displaystyle \{\,x,0,1\,\}}$ Класс селекторов с нулями; Класс селекторов с единицами; Класс констант. Селекторы с отрицаниями ${\displaystyle R_{4}}$ ${\displaystyle O_{4}}$ ${\displaystyle SU}$ ${\displaystyle {\overline {I}}}$ ${\displaystyle \{\,{\overline {x}}\,\}}$ Класс селекторов. Несущественные функции ${\displaystyle R_{13}}$ ${\displaystyle O_{9}}$ ${\displaystyle U}$ ${\displaystyle [P_{2}^{1}]}$ ${\displaystyle \{\,{\overline {x}},0\,\}}$ ${\displaystyle \{\,{\overline {x}},1\,\}}$ Класс селекторов с отрицаниями; Класс селекторов с константами. Порядок 2 Булевы функции ${\displaystyle C_{1}}$ ${\displaystyle C_{1}}$ ${\displaystyle P_{2}}$ ${\displaystyle P_{2}}$ ${\displaystyle P_{2}}$ ${\displaystyle \{\,|\,\}}$ ${\displaystyle \{\,\downarrow \,\}}$ Класс функций, сохраняющих 0; Класс функций, сохраняющих 1; Класс монотонных функций; Класс линейных функций; Класс самодвойственных функций. Функции, сохраняющие 0 ${\displaystyle C_{3}}$ ${\displaystyle C_{3}}$ ${\displaystyle T_{0}}$ ${\displaystyle T_{0}}$ ${\displaystyle T_{0}}$ ${\displaystyle \{\,\land ,\oplus \,\}}$ Класс функций, сохраняющих константы; Класс монотонных функций, сохраняющих 0; Класс линейных функций, сохраняющих 0; Класс функций, удовлетворяющих условию 1. Функции, сохраняющие 1 ${\displaystyle C_{2}}$ ${\displaystyle C_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{1}}$ ${\displaystyle \{\,\lor ,\leftrightarrow \,\}}$ Класс функций, сохраняющих константы; Класс монотонных функций, сохраняющих 1; Класс линейных функций, сохраняющих 1; Класс функций, удовлетворяющих условию 0; Монотонные функции ${\displaystyle A_{1}}$ ${\displaystyle A_{1}}$ ${\displaystyle M_{1}}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle \{\,\land ,\lor ,0,1\,\}}$ Класс монотонных функций, сохраняющих 0; Класс монотонных функций, сохраняющих 1; Класс конъюнкций с константами; Класс дизъюнкций с константами. Монотонные функции без единиц ${\displaystyle A_{3}}$ ${\displaystyle A_{3}}$ ${\displaystyle M_{3}}$ ${\displaystyle M_{0}}$ ${\displaystyle M\cap T_{0}}$ ${\displaystyle \{\,\land ,\lor ,0\,\}}$ Класс монотонных функций, сохраняющих константы; Класс конъюнкций с нулями; Класс монотонных функций, удовлетворяющих условию 1. Монотонные функции без нулей ${\displaystyle A_{2}}$ ${\displaystyle A_{2}}$ ${\displaystyle M_{2}}$ ${\displaystyle M_{1}}$ ${\displaystyle M\cap T_{1}}$ ${\displaystyle \{\,\land ,\lor ,1\,\}}$ Класс монотонных функций, сохраняющих константы; Класс конъюнкций с единицами; Класс монотонных функций, удовлетворяющих условию 0. Монотонные функции без констант ${\displaystyle A_{4}}$ ${\displaystyle A_{4}}$ ${\displaystyle M_{4}}$ ${\displaystyle M_{01}}$ ${\displaystyle M\cap T_{0}\cap T_{1}}$ ${\displaystyle \{\,\land ,\lor \,\}}$ Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 0; Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 1. Конъюнкции с константами ${\displaystyle P_{6}}$ ${\displaystyle P_{6}}$ ${\displaystyle K}$ ${\displaystyle K\cup C}$ ${\displaystyle \{\,\land ,0,1\,\}}$ Класс конъюнкций с единицами; Класс конъюнкций с нулями Класс селекторов с константами. Конъюнкции с нулями ${\displaystyle P_{4}}$ ${\displaystyle P_{3}}$ ${\displaystyle K_{0}}$ ${\displaystyle K\cup C_{0}}$ ${\displaystyle \{\,\land ,0\,\}}$ Класс конъюнкций без констант; Класс селекторов с нулями. Конъюнкции с единицами ${\displaystyle P_{5}}$ ${\displaystyle P_{5}}$ ${\displaystyle K_{1}}$ ${\displaystyle K\cup C_{1}}$ ${\displaystyle \{\,\land ,1\,\}}$ Класс конъюнкций без констант; Класс селекторов с единицами. Конъюнкции без констант ${\displaystyle P_{2}}$ ${\displaystyle P_{1}}$ ${\displaystyle K_{01}}$ ${\displaystyle K}$ ${\displaystyle \{\,\land \,\}}$ Класс селекторов Дизъюнкции с константами ${\displaystyle S_{6}}$ ${\displaystyle S_{6}}$ ${\displaystyle D}$ ${\displaystyle D\cup C}$ ${\displaystyle \{\,\lor ,0,1\,\}}$ Класс дизъюнкций с единицами; Класс дизъюнкций с нулями; Класс селекторов с константами. Дизъюнкции с единицами ${\displaystyle S_{4}}$ ${\displaystyle S_{3}}$ ${\displaystyle D_{1}}$ ${\displaystyle D\cup C_{1}}$ ${\displaystyle \{\,\lor ,1\,\}}$ Класс дизъюнкций без констант; Класс селекторов с единицами. Дизъюнкции с нулями ${\displaystyle S_{5}}$ ${\displaystyle S_{5}}$ ${\displaystyle D_{0}}$ ${\displaystyle D\cup C_{0}}$ ${\displaystyle \{\,\lor ,0\,\}}$ Класс дизъюнкций без констант; Класс селекторов с нулями. Дизъюнкции без констант ${\displaystyle S_{2}}$ ${\displaystyle S_{1}}$ ${\displaystyle D_{01}}$ ${\displaystyle D}$ ${\displaystyle \{\,\lor \,\}}$ Класс селекторов. Линейные функции ${\displaystyle L_{1}}$ ${\displaystyle L_{1}}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle \{\,\oplus ,1\,\}}$ ${\displaystyle \{\,\leftrightarrow ,0\,\}}$ Класс линейных функций, сохраняющих 0; Класс линейных функций, сохраняющих 1; Класс линейных самодвойственных функций; Класс несущественных функций. Линейные функции, сохраняющие 0 ${\displaystyle L_{3}}$ ${\displaystyle L_{3}}$ ${\displaystyle L_{0}}$ ${\displaystyle L\cap T_{0}}$ ${\displaystyle \{\,\oplus \,\}}$ Класс линейных функций, сохраняющих константы; Класс селекторов с нулями. Линейные функции, сохраняющие 1 ${\displaystyle L_{2}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L\cap T_{1}}$ ${\displaystyle \{\,\leftrightarrow \,\}}$ Класс линейных функций, сохраняющих константы; Класс селекторов с единицами. Функции, удовлетворяющие условию 1 ${\displaystyle F_{8}^{\infty }}$ ${\displaystyle F_{8}^{\infty }}$ ${\displaystyle I^{\infty }}$ ${\displaystyle T_{0,\infty }}$ ${\displaystyle \{\,\not \leftarrow \,\}}$ Класс монотонных функций, удовлетворяющих условию 1; Класс функций, сохраняющих константы и удовлетворяющих условию 1. Функции, удовлетворяющие условию 0 ${\displaystyle F_{4}^{\infty }}$ ${\displaystyle F_{4}^{\infty }}$ ${\displaystyle O^{\infty }}$ ${\displaystyle T_{1,\infty }}$ ${\displaystyle \{\,\rightarrow \,\}}$ Класс монотонных функций, удовлетворяющих условию 0; Класс функций, сохраняющих константы и удовлетворяющих условию 0. Порядок 3 Функции, сохраняющие константы ${\displaystyle C_{4}}$ ${\displaystyle C_{4}}$ ${\displaystyle T_{01}}$ ${\displaystyle T_{0}\cap T_{1}}$ ${\displaystyle \{\,x\oplus y\oplus z,\land \,\}}$ ${\displaystyle \{\,x\oplus y\oplus z,\lor \,\}}$ Класс монотонных функций, сохраняющих константы; Класс самодвойственных функций, сохраняющих константы; Класс функций, сохраняющих константы и удовлетворяющих условию 1; Класс функций, сохраняющих константы и удовлетворяющих условию 0. Линейные самодвойственные функции ${\displaystyle L_{5}}$ ${\displaystyle L_{5}}$ ${\displaystyle SL}$ ${\displaystyle S\cap L}$ ${\displaystyle \{\,x\oplus y\oplus z\oplus 1\,\}}$ Класс линейных функций, сохраняющих константы; Класс селекторов с отрицаниями. Линейные функции, сохраняющие константы ${\displaystyle L_{4}}$ ${\displaystyle L_{4}}$ ${\displaystyle L_{01}}$ ${\displaystyle S\cap L\cap T_{0}}$ ${\displaystyle \{\,x\oplus y\oplus z\,\}}$ Класс линейных функций, сохраняющих константы; Класс селекторов с отрицаниями. Самодвойственные функции ${\displaystyle D_{3}}$ ${\displaystyle D_{3}}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \{\,{\overline {m}}(x,y,z)\,\}}$[27] Класс линейных самодвойственных функций; Класс самодвойственных функций, сохраняющих константы. Самодвойственные функции, сохраняющие константы ${\displaystyle D_{1}}$ ${\displaystyle D_{1}}$ ${\displaystyle S_{01}}$ ${\displaystyle S\cap T_{0}}$ ${\displaystyle \{\,m(x,y,z),x\oplus y\oplus z\,\}}$[28] Класс монотонных самодвойственных функций; Класс линейных функций, сохраняющих константы. Монотонные самодвойственные функции ${\displaystyle D_{2}}$ ${\displaystyle D_{2}}$ ${\displaystyle SM}$ ${\displaystyle S\cap M}$ ${\displaystyle \{\,m(x,y,z)\,\}}$ Класс селекторов. Монотонные функции, удовлетворяющие условию 1 ${\displaystyle F_{7}^{\infty }}$ ${\displaystyle F_{7}^{\infty }}$ ${\displaystyle MI^{\infty }}$ ${\displaystyle T_{0,\infty }\cap M}$ ${\displaystyle \{\,x(y\lor z),0\,\}}$ Класс конъюнкций с нулями; Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 1. Функции, сохраняющие константы и удовлетворяющие условию 1 ${\displaystyle F_{5}^{\infty }}$ ${\displaystyle F_{5}^{\infty }}$ ${\displaystyle I_{1}^{\infty }}$ ${\displaystyle T_{0,\infty }\cap T_{1}}$ ${\displaystyle \{\,x(y\lor {\overline {z}})\,\}}$ Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 1. Монотонные функции, сохраняющие константы и удовлетворяющие условию 1 ${\displaystyle F_{6}^{\infty }}$ ${\displaystyle F_{6}^{\infty }}$ ${\displaystyle MI_{1}^{\infty }}$ ${\displaystyle T_{0,\infty }\cap M\cap T_{1}}$ ${\displaystyle \{\,x(y\lor z)\,\}}$ Класс конъюнкций с константами. Монотонные функции, удовлетворяющие условию 0 ${\displaystyle F_{3}^{\infty }}$ ${\displaystyle F_{3}^{\infty }}$ ${\displaystyle MO^{\infty }}$ ${\displaystyle T_{1,\infty }\cap M}$ ${\displaystyle \{\,x\lor yz,1\,\}}$ Класс дизъюнкций с единицами; Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 0. Функции, сохраняющие константы и удовлетворяющие условию 0 ${\displaystyle F_{1}^{\infty }}$ ${\displaystyle F_{1}^{\infty }}$ ${\displaystyle O_{0}^{\infty }}$ ${\displaystyle T_{1,\infty }\cap T_{0}}$ ${\displaystyle \{\,x\lor y{\overline {z}}\,\}}$ Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 0. Монотонные функции, сохраняющие константы и удовлетворяющие условию 0 ${\displaystyle F_{2}^{\infty }}$ ${\displaystyle F_{2}^{\infty }}$ ${\displaystyle MO_{0}^{\infty }}$ ${\displaystyle T_{1,\infty }\cap M\cap T_{0}}$ ${\displaystyle \{\,x\lor yz\,\}}$ Класс дизъюнкций с константами. Функции, удовлетворяющие условию 1 ${\displaystyle F_{8}^{2}}$ ${\displaystyle F_{8}^{2}}$ ${\displaystyle I^{2}}$ ${\displaystyle T_{0,2}}$ ${\displaystyle \{\,m(x,y,z),x\not \leftarrow y\,\}}$ Класс функций, удовлетворяющих условию 1; Класс монотонных функций, удовлетворяющих условию 1; Класс функций, сохраняющих константы и удовлетворяющих условию 1. Монотонные функции, удовлетворяющие условию 1 ${\displaystyle F_{7}^{2}}$ ${\displaystyle F_{7}^{2}}$ ${\displaystyle MI^{2}}$ ${\displaystyle T_{0,2}\cap M}$ ${\displaystyle \{\,m(x,y,z),0\,\}}$ Класс монотонных функций, удовлетворяющих условию 1; Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 1. Функции, сохраняющие константы и удовлетворяющие условию 1 ${\displaystyle F_{5}^{2}}$ ${\displaystyle F_{5}^{2}}$ ${\displaystyle I_{1}^{2}}$ ${\displaystyle T_{0,2}\cap T_{1}}$ ${\displaystyle \{\,m(x,y,z),x(y\lor {\overline {z}})\,\}}$ Класс функций, сохраняющих константы и удовлетворяющих условию 1; Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 1. Монотонные функции, сохраняющие константы и удовлетворяющие условию 1 ${\displaystyle F_{6}^{2}}$ ${\displaystyle F_{6}^{2}}$ ${\displaystyle MI_{1}^{2}}$ ${\displaystyle T_{0,2}\cap M\cap T_{1}}$ ${\displaystyle \{\,m(x,y,z),x(y\lor z)\,\}}$ Класс функций, сохраняющих константы и удовлетворяющих условию 1; Класс монотонных самодвойственных функций. Функции, удовлетворяющие условию 0 ${\displaystyle F_{4}^{2}}$ ${\displaystyle F_{4}^{2}}$ ${\displaystyle O^{2}}$ ${\displaystyle T_{1,2}}$ ${\displaystyle \{\,m(x,y,z),x\rightarrow y\,\}}$ Класс функций, удовлетворяющих условию 0; Класс монотонных функций, удовлетворяющих условию 0; Класс функций, сохраняющих константы и удовлетворяющих условию 0. Монотонные функции, удовлетворяющие условию 0 ${\displaystyle F_{3}^{2}}$ ${\displaystyle F_{3}^{2}}$ ${\displaystyle MO^{2}}$ ${\displaystyle T_{1,2}\cap M}$ ${\displaystyle \{\,m(x,y,z),1\,\}}$ Класс монотонных функций, удовлетворяющих условию 0; Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 0. Функции, сохраняющие константы и удовлетворяющие условию 0 ${\displaystyle F_{1}^{2}}$ ${\displaystyle F_{1}^{2}}$ ${\displaystyle O_{0}^{2}}$ ${\displaystyle T_{1,2}\cap T_{0}}$ ${\displaystyle \{\,m(x,y,z),x\lor y{\overline {z}}\,\}}$ Класс функций, сохраняющих константы и удовлетворяющих условию 0; Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 0. Монотонные функции, сохраняющие константы и удовлетворяющие условию 0 ${\displaystyle F_{2}^{2}}$ ${\displaystyle F_{2}^{2}}$ ${\displaystyle MO_{0}^{2}}$ ${\displaystyle T_{1,2}\cap M\cap T_{0}}$ ${\displaystyle \{\,m(x,y,z),x\lor yz\,\}}$ Класс функций, сохраняющих константы и удовлетворяющих условию 0; Класс монотонных самодвойственных функций. Порядок ${\displaystyle m+1\geq 4}$ Функции, удовлетворяющие условию 1 ${\displaystyle F_{8}^{m}}$ ${\displaystyle F_{8}^{m}}$ ${\displaystyle I^{m}}$ ${\displaystyle T_{0,m}}$ ${\displaystyle \{\,h_{m}(x_{1},\ldots ,x_{m+1}),x\not \leftarrow y\,\}}$[29] Класс функций, удовлетворяющих условию 1m+1; Класс монотонных функций, удовлетворяющих условию 1; Класс функций, сохраняющих константы и удовлетворяющих условию 1. Монотонные функции, удовлетворяющие условию 1 ${\displaystyle F_{7}^{m}}$ ${\displaystyle F_{7}^{m}}$ ${\displaystyle MI^{m}}$ ${\displaystyle T_{0,m}\cap M}$ ${\displaystyle \{\,h_{m}(x_{1},\ldots ,x_{m+1}),0\,\}}$ Класс монотонных функций, удовлетворяющих условию 1m+1; Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 1. Функции, сохраняющие константы и удовлетворяющие условию 1 ${\displaystyle F_{5}^{m}}$ ${\displaystyle F_{5}^{m}}$ ${\displaystyle I_{1}^{m}}$ ${\displaystyle T_{0,m}\cap T_{1}}$ ${\displaystyle \{\,h_{m}(x_{1},\ldots ,x_{m+1}),x(y\lor {\overline {z}})\,\}}$ Класс функций, сохраняющих константы и удовлетворяющих условию 1m+1; Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 1. Монотонные функции, сохраняющие константы и удовлетворяющие условию 1 ${\displaystyle F_{6}^{m}}$ ${\displaystyle F_{6}^{m}}$ ${\displaystyle MI_{1}^{m}}$ ${\displaystyle T_{0,m}\cap M\cap T_{1}}$ ${\displaystyle \{\,h_{m}(x_{1},\ldots ,x_{m+1})\,\}}$ Класс функций, сохраняющих константы и удовлетворяющих условию 1m+1. Функции, удовлетворяющие условию 0 ${\displaystyle F_{4}^{m}}$ ${\displaystyle F_{4}^{m}}$ ${\displaystyle O^{m}}$ ${\displaystyle T_{1,m}}$ ${\displaystyle \{\,h_{m}^{*}(x_{1},\ldots ,x_{m+1}),x\rightarrow y\,\}}$[30] Класс функций, удовлетворяющих условию 0m+1; Класс монотонных функций, удовлетворяющих условию 0; Класс функций, сохраняющих константы и удовлетворяющих условию 0. Монотонные функции, удовлетворяющие условию 0 ${\displaystyle F_{3}^{m}}$ ${\displaystyle F_{3}^{m}}$ ${\displaystyle MO^{m}}$ ${\displaystyle T_{1,m}\cap M}$ ${\displaystyle \{\,h_{m}^{*}(x_{1},\ldots ,x_{m+1}),1\,\}}$ Класс монотонных функций, удовлетворяющих условию 0m+1; Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 0. Функции, сохраняющие константы и удовлетворяющие условию 0 ${\displaystyle F_{1}^{m}}$ ${\displaystyle F_{1}^{m}}$ ${\displaystyle O_{0}^{m}}$ ${\displaystyle T_{1,m}\cap T_{0}}$ ${\displaystyle \{\,h_{m}^{*}(x_{1},\ldots ,x_{m+1}),x\lor y{\overline {z}}\,\}}$ Класс функций, сохраняющих константы и удовлетворяющих условию 0m+1; Класс монотонных функций, сохраняющих константы и удовлетворяющих условию 0. Монотонные функции, сохраняющие константы и удовлетворяющие условию 0 ${\displaystyle F_{2}^{m}}$ ${\displaystyle F_{2}^{m}}$ ${\displaystyle MO_{0}^{m}}$ ${\displaystyle T_{1,m}\cap M\cap T_{0}}$ ${\displaystyle \{\,h_{m}^{*}(x_{1},\ldots ,x_{m+1})\,\}}$ Класс функций, сохраняющих константы и удовлетворяющих условию 0m+1. Примечания Марченков, 2000, с. 9. 1 2 Пост, 1941. Лау, 2006, с. 2. Подколзин, с. 6-7. Лау, 2006, с. 1. Яблонский, 1986, с. 33. Лау, 2006, с. 97. 1 2 Угольников, 1988, с. 84-85. 1 2 3 Марченков, 2000, с. 15. 1 2 Марченков, 2000, с. 11. Марченков, 2000, с. 13. Яблонский, 1986, с. 40-41. 1 2 Марченков, 2000, с. 19. 1 2 3 4 Марченков, 2000, с. 29. 1 2 Марченков, 2000, с. 19-20. Марченков, 2000, с. 29-30,41. Яблонский, Гаврилов, Кудрявцев, 1966, с. 19. Подколзин2, с. 5. Подколзин, с. 6. Лау, 2006, с. 45-47,97. Марченков, 2000, с. 10. Алексеев, Поспелов, с. 6. Буевич, Подколзина, 2007, с. 193. Пост, 1941, с. 101. Яблонский, Гаврилов, Кудрявцев, 1966, с. 101,112. Лау, 2006, с. 148. ${\displaystyle {\overline {m}}(x,y,z)}$ — отрицание функции голосования ${\displaystyle m(x,y,z)}$ — функция голосования ${\displaystyle h_{m}(x_{1},\ldots ,x_{m+1})}$ — равна ${\displaystyle 1}$, если как минимум ${\displaystyle m}$ аргументов равно ${\displaystyle 1}$, иначе ${\displaystyle 0}$ ${\displaystyle h_{m}^{*}(x_{1},\ldots ,x_{m+1})}$ — равна ${\displaystyle 0}$, если как минимум ${\displaystyle m}$ аргументов равно ${\displaystyle 0}$, иначе ${\displaystyle 1}$ Литература Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука. — 1969 Алексеев В. Б., Поспелов А. Д. Дискретная математика (курс лекций, II семестр) . Дата обращения: 24 августа 2025. Ахметова Н.А., Усманова З.М.Дискретная математика, функции алгебры логики. Угольников, А. Б. О замкнутых классах Поста (рус.) // Изв. вузов. Матем. : журнал. — М.: Soviet Math. (Iz. VUZ), 1988. — 16 февраля (т. 32, вып. 7). — С. 79-88. Подколзин А. С. 1 лекция курса «Теория дискретных функций»  (рус.). http://intsys.msu.ru. Дата обращения: 4 мая 2024. Подколзин А. С. 2 лекция курса «Теория дискретных функций»  (рус.). http://intsys.msu.ru. Дата обращения: 23 августа 2025. Буевич В. А., Подколзина М. А. Критерий полноты S-множеств детерминированных функций (рус.) // Математические вопросы кибернетики : журнал. — М.: ФИЗМАТЛИТ, 2007. — Вып. 16. — С. 191-238.