Замкнутый класс булевых функций

Замкнутый класс в теории булевых функций — такое множество ${\displaystyle P}$ функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: ${\displaystyle [P]=P}$. Другими словами, любая функция, которую можно выразить формулой с использованием функций множества ${\displaystyle P}$, снова входит в это же множество^[1].

В 1941 году Эмиль Пост представил полное описание всех замкнутых классов булевых функций^[2]. Множество всех замкнутых классов, упорядоченное отношением включения, образует решётку, называемую решёткой Поста^[3].

Говорят, что функция ${\displaystyle f\in P_{2}}$ получена при помощи операции суперпозиции функций из множества ${\displaystyle F\subseteq P_{2}}$, если функция ${\displaystyle f}$ может быть получена из функций множества ${\displaystyle F}$ за конечное число шагов при помощью следующих операций:

1. Перестановка и отождествление переменных;
2. Подстановка функций и переменных в качестве аргументов другой функции;
3. Добавление и удаление фиктивных переменных.

Если множество функций замкнуто относительно указанных операций, то оно называется замкнутым классом. В данном определении разрешается функциям иметь ноль аргументов, то есть быть нульарными^[4].

В англоязычной литературе и некоторой русскоязычной зачастую используют другое определение, неэквивалентное данному. Замкнутому классу запрещают иметь нульарные функции и убирается требование замкнутости относительно операции удаления переменных. Замкнутые классы в этом определении идентичны замкнутым классам в первом, с точностью до нульарных функций^[5].

Пусть дано множество ${\displaystyle F\subseteq P_{2}}$ функций положительной арности и множество ${\displaystyle X}$, ${\displaystyle X\cap F=\varnothing }$, называемое множеством переменных. Булевой формулой глубины 0 над множеством функций ${\displaystyle F}$ и множеством переменных ${\displaystyle X}$ называется однобуквенное слово из одного символа ${\displaystyle x\in X}$. Булевой формулой глубины ${\displaystyle n}$, где ${\displaystyle n\in \mathbb {N} }$, ${\displaystyle n>0}$ называется слово вида ${\displaystyle g(\varphi _{1},\ldots ,\varphi _{m})}$, где ${\displaystyle g\in F}$ ― функция, имеющая арность ${\displaystyle m}$, а ${\displaystyle \varphi _{i}}$ ― булевы формулы, глубины меньше ${\displaystyle n}$. Говорят, что функция ${\displaystyle f\in P_{2}}$ задаётся булевой формулой ${\displaystyle \varphi }$ относительно набора переменных ${\displaystyle (x_{1},\ldots ,x_{k})}$ (все ${\displaystyle x_{i}}$ в этом наборе отличаются и каждая переменная формулы входит в этот набор), если ${\displaystyle f(\alpha _{1},\ldots ,\alpha _{k})}$ равняется значению этой формулы, после подстановки вместо каждого ${\displaystyle x_{i}}$ значения ${\displaystyle \alpha _{i}}$. Тогда говорят, что функция ${\displaystyle f\in P_{2}}$ получена при помощи операции суперпозиции функций из множества ${\displaystyle F\subseteq P_{2}}$, если функция ${\displaystyle f}$ может быть задана булевой формулой положительной глубины над множеством функций ${\displaystyle F}$.

Данное определение эквивалентно второму определению выше (то есть тому, где запрещаются функции нулевой арности). Определение через формулы можно видоизменить для того, чтобы оно соответствовала первому определению (тому, где разрешается удаление фиктивных переменных). Для этого множеству ${\displaystyle F}$ разрешается иметь нульарные функции и вводится понятие фиктивной переменной формулы. Переменная ${\displaystyle x}$ называется фиктивной переменной булевой формулы ${\displaystyle \varphi }$, если любое изменение значения данной переменной при сохранении значений остальных переменных не меняет значения формулы; в противном случае переменная называется существенной. Тогда при определении того, что функция ${\displaystyle f}$ задаётся формулой относительно набора переменных ${\displaystyle (x_{1},\ldots ,x_{k})}$ на этот набор накладывается менее строгое ограничение: требуется не чтобы любая переменная формула обязательно входила в этот набор, а достаточно чтобы любая существенная переменная входила в него, а фиктивные могут и не входить. Формулировка определения того, что функция получена при помощи операции суперпозиции, остаётся без изменений. Такое определение будет эквивалентно определению через элементарные операции с удалением фиктивных переменных^[6].

Простейшими замкнутыми классами являются класс всех булевых функций ${\displaystyle P_{2}}$^[7] и пустое множество ${\displaystyle \varnothing }$^[8]. Некоторые авторы не считают пустое множество замкнутым классом^[9]; в таком случае множество всех замкнутых классов булевых функций с отношением включения не образует решётку.

Особо известными замкнутыми классами булевых функций являются следующие 5 классов:

• Класс ${\displaystyle T_{0}}$ функций, сохраняющих константу 0:
  ${\displaystyle T_{0}=\{\,f(x_{1},\dots ,x_{n})|f(0,\dots ,0)=0\,\}}$^[10].
• Класс ${\displaystyle T_{1}}$ функций, сохраняющих константу 1:
  ${\displaystyle T_{1}=\{\,f(x_{1},\dots ,x_{n})|f(1,\dots ,1)=1\,\}}$^[10].
• Класс ${\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})}}\,\}}$^[11].
• Класс ${\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})\,\}}$^[12].
• Класс ${\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\}\,\}}$^[10].

Эти классы так известны, поскольку участвуют в формулировке критерия Поста. Любой замкнутый класс булевых функций, отличный от класса всех функций, вкладывается в хотя бы один из этих пяти классов^[13].

Другими важными замкнутыми классами являются:

• Класс конъюнкций с константами ${\displaystyle K}$, представляющий собой множество функций вида ${\displaystyle c_{0}\wedge (c_{1}\vee x_{1})\wedge \ldots \wedge (c_{n}\vee x_{n})}$^[14].
• Класс дизъюнкций с константами ${\displaystyle D}$, представляющий собой множество функций вида ${\displaystyle c_{0}\vee (c_{1}\wedge x_{1})\vee \ldots \vee (c_{n}\wedge x_{n})}$^[14].
• Класс несущественных функций ${\displaystyle U}$, содержащий только константы, отрицания одного из своих аргументов и селекторы (функции, равные одному из своих аргументов на всех наборах их значений)^[15].
• Класс констант ${\displaystyle C}$, содержащий только константы^[15].
• Класс ${\displaystyle T_{1,m}}$ функций (m — любое натуральное, большее единицы число), удовлетворяющих условию ${\displaystyle \langle 0^{m}\rangle }$: для любых m наборов, на которых функция принимает нулевое значение, найдется переменная, также принимающая нулевое значение на всех этих наборах^[15].
• Класс ${\displaystyle T_{1,\infty }}$ функций, для которых выполнено условие ${\displaystyle \langle 0^{\infty }\rangle }$: ${\displaystyle f(x_{1},\ldots ,x_{n})\geq x_{i}}$, где ${\displaystyle x_{i}}$ — одна из переменных функции^[16].
• Класс ${\displaystyle T_{0,m}}$ функций (m — любое натуральное, большее единицы число), удовлетворяющих условию ${\displaystyle \langle 1^{m}\rangle }$: для любых m наборов, на которых функция принимает единичное значение, найдется переменная, также принимающая единичное значение на всех этих наборах^[15].
• Класс ${\displaystyle T_{0,\infty }}$ функций, для которых выполнено условие ${\displaystyle \langle 1^{\infty }\rangle }$: ${\displaystyle f(x_{1},\ldots ,x_{n})\leq x_{i}}$, где ${\displaystyle x_{i}}$ — одна из переменных функции^[16].

Любой замкнутый класс булевых функций является пересечением конечного числа классов ${\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 \}}$^[17].

• Пересечение любого числа замкнутых классов снова является замкнутым классом^[18] (если пустое множество считать замкнутым классом).
• Объединение замкнутых классов может замкнутым классом не являться (например объединение класса нулей и класса селекторов с отрицаниями не является замкнутым классом, поскольку отрицание нуля даст единицу).
• Замкнутый класс булевых функций, содержащий не только константы, обязательно содержит все селекторы.
• Дополнение замкнутого класса булевых функций до множества всех булевых функций ${\displaystyle P_{2}}$ может замкнутым классом не являться (если пустое множество не считать замкнутым классом, то дополнение не является замкнутым классом никогда).

Замыканием (относительно суперпозиции) системы функций ${\displaystyle F}$ называется множество всех функций, которые могут быть получены из функций множества ${\displaystyle F}$ при помощи суперпозиции. Замыкание системы функций ${\displaystyle F}$ обозначается ${\displaystyle [F]}$.^[19]. Замыкание любой системы функций является замкнутым классом. Система функций ${\displaystyle F}$ является замкнутым классом тогда и только тогда, когда ${\displaystyle F=[F]}$^[6]. Класс ${\displaystyle [F]}$ является наименьшим по включению замкнутым классом, включающим ${\displaystyle F}$. Класс ${\displaystyle [F]}$ можно получить как пересечение всех замкнутых классов, содержащих ${\displaystyle F}$.

Замыкание относительно суперпозиции является частым случаем теоретико-множественного замыкания, то есть для него выполнены следующие свойства:

1. Любое множество является подмножеством своего замыкания: ${\displaystyle F\subseteq [F]}$.
2. Замыкание подмножества является подмножеством замыкания: ${\displaystyle F\subseteq G\Rightarrow [F]\subseteq [G]}$.
   Следует заметить, что из строгого вложения множеств следует лишь нестрогое вложение их замыканий: ${\displaystyle F\subset G\Rightarrow [F]\subseteq [G]}$
3. Многократное применение операции замыкания эквивалентно однократному: ${\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}$. Таким образом базис — это минимальная по включению полная система класса^[11].

Приведённая выше система ${\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 Q}$ класса ${\displaystyle V}$ называется критериальной в замкнутом классе ${\displaystyle Q}$, если каждый собственный подкласс ${\displaystyle V}$ вкладывается в некоторый класс из ${\displaystyle 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].

Список всех замкнутых классов булевой логики представлен в следующей таблице. Таблица разделена на блоки по порядкам классов. Определение порядка класса здесь используется первое (во втором все классы, у которых здесь указан порядок 0, имеют порядок 1). Всего существует 4 класса порядка 0 (или 3 если не считать пустое множество замкнутым классом), 6 классов порядка 1, 20 классов порядков 2, 20 классов порядка 3 и по 8 классов для каждого из порядков больше 3. В столбце "П" указано обозначение Поста^[24], в столбце "ЯГК" — обозначение Яблонского, Гаврилова и Кудрявцева^[25], в столбце "У" — обозначение Угольникова^[9] и в столбце "Л" — обозначение Лау^[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⟩.

Клоном называется замкнутый класс, содержащий все селекторы^[31]. Любой замкнутый класс, содержащий не константную функцию, является клоном. Всего есть 4 замкнутых класса, не являющиеся клонами: пустое множество, класс единиц, класс нулей и класс констант.

Для клонов понятия замыкания, полной системы и базиса несколько отличаются от таковых для замкнутых классов. Замыканием (в смысле клона) системы функций ${\displaystyle F}$ называется минимальный по включению клон, содержащий все функции ${\displaystyle F}$. Такой клон всегда существует, поскольку его можно найти как пересечение всех клонов, содержащих ${\displaystyle F}$. Система функций ${\displaystyle F}$ называется полной в клоне ${\displaystyle Q}$, если замыкание ${\displaystyle F}$ (в смысле клона) даёт ${\displaystyle Q}$. Базисом клона называется минимальная по включению полная система функций.

Нетрудно привести примеры, когда понятия базисов для клонов и замкнутых классов не совпадают. Например, для класса селекторов с единицами система ${\displaystyle \{\,x,1\,\}}$ является базисом как для замкнутого класса, но не является базисом как для клона, а система ${\displaystyle \{\,1\,\}}$ является базисом как для клона, но не является базисом как для замкнутого класса.

Клон ${\displaystyle S}$ называется максимальным в клоне ${\displaystyle Q}$, если для любой ${\displaystyle f\in Q\setminus S}$ замыкание (в смысле клона) системы ${\displaystyle S\cup \{f\}}$ даёт ${\displaystyle Q}$. Это является прямым аналогом понятия предполного класса, для них также верны все замечания про критериальные системы и тд. Конечно, минимальные критериальные системы как для клона и как для класса могут отличаться, однако таких отличий довольно мало и они все будут приведены в таблице клонов.

Для клонов можно дать определение через формулы. Если в определении суперпозиции через формулы убрать требование, что формулы должны иметь положительную глубину, и разрешить глубину 0, то множество функций, которое может быть задано всеми такими формулами над множеством ${\displaystyle F}$, есть замыкание (в смысле клона) множества ${\displaystyle F}$.

Таблица клонов булевых функций для порядков больше 1 полностью совпадает с таблицей замкнутых классов, поэтому здесь будет приведена таблица только для клонов порядков 0 и 1. Всего есть 4 клона порядка 0 и 2 клона порядка 1.

Название	П	ЯГК	У	Л	Примеры базисов	Максимальные клоны
Порядок 0
Селекторы	${\displaystyle R_{1}}$	${\displaystyle O_{1}}$	${\displaystyle U_{01}}$	${\displaystyle I}$	${\displaystyle \varnothing }$
Селекторы с нулями	${\displaystyle R_{8}}$	${\displaystyle O_{6}}$	${\displaystyle U_{0}}$	${\displaystyle I\cup C_{0}}$	${\displaystyle \{\,0\,\}}$	Класс селекторов.
Селекторы с единицами	${\displaystyle R_{6}}$	${\displaystyle O_{5}}$	${\displaystyle U_{1}}$	${\displaystyle I\cup C_{1}}$	${\displaystyle \{\,1\,\}}$	Класс селекторов.
Селекторы с константами	${\displaystyle R_{11}}$	${\displaystyle O_{8}}$	${\displaystyle MU}$	${\displaystyle I\cup C}$	${\displaystyle \{\,0,1\,\}}$	Класс селекторов с нулями; Класс селекторов с единицами.
Порядок 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\,\}}$	Класс селекторов с отрицаниями; Класс селекторов с константами.

Сам Эмиль Пост в своей монографии строил свою классификацию для замыкания, отличного от вышерассмотренных. У него также запрещались нульарные функции, но при этом добавление фиктивных переменных было также запрещено. Замкнутые множества относительно такого замыкания он называл итеративными системами^[32]. Таблица для них в большинстве систем совпадает с таблицей для замкнутых классов, однако в некоторых случаях всё же не совпадают, а также появляются новые множества. Здесь будут приведены только те итеративные системы, которые отличаются от соответствующих в таблице замкнутых классов, а также новые. Все те классы, что здесь не будут приведены, без изменений переносятся сюда из таблицы замкнутых классов. Далее за ${\displaystyle e_{1}^{2}}$ обозначена функция ${\displaystyle e_{1}^{2}(x_{1},x_{2})=x_{1}}$, за ${\displaystyle e_{1}^{1}}$ функция ${\displaystyle e_{1}^{1}(x)=x}$, за ${\displaystyle 0^{1}}$ функция ${\displaystyle 0^{1}(x)=0}$, за ${\displaystyle 1^{1}}$ функция ${\displaystyle 1^{1}(x)=1}$, за ${\displaystyle 0^{2}}$ функция ${\displaystyle 0^{2}(x_{1},x_{2})=0}$, а за ${\displaystyle 0^{1}}$ функция ${\displaystyle 1^{2}(x)=1}$. Постом также было использовано второе определение порядка (то есть с учётом фиктивных переменных), и на этот раз в таблице будет использовано именно оно. Существует 10 итеративных систем порядка 1 (9, если не считать пустое множество итеративной системой), 37 итеративных систем порядка 2, 20 итеративных систем порядка 3, и по 8 итеративных систем для каждого из порядков больше 2^[33].

Название	П	Примеры базисов	Максимальные итеративные системы
Порядок 1
Пустое множество	—	${\displaystyle \varnothing }$
Унарный 0	${\displaystyle O_{3}}$	${\displaystyle \{\,0^{1}\,\}}$	Пустое множество.
Унарная 1	${\displaystyle O_{2}}$	${\displaystyle \{\,1^{1}\,\}}$	Пустое множество.
Унарные константы	${\displaystyle O_{7}}$	${\displaystyle \{\,0^{1},1^{1}\,\}}$	Унарный 0; Унарная 1.
Тождественная функция	${\displaystyle O_{1}}$	${\displaystyle \{\,e_{1}^{1}\,\}}$	Пустое множество.
Тождественная функция с унарным 0	${\displaystyle O_{6}}$	${\displaystyle \{\,e_{1}^{1},0^{1}\,\}}$	Тождественная функция; Унарный 0.
Тождественная функция с унарным 1	${\displaystyle O_{5}}$	${\displaystyle \{\,e_{1}^{1},1^{1}\,\}}$	Тожественная функция; Унарный 1.
Тождественная функция с унарными константами	${\displaystyle O_{8}}$	${\displaystyle \{\,e_{1}^{1},0^{1},1^{1}\,\}}$	Тождественная функция с унарным 0; Тождественная функция с унарным 1; Унарные константы.
Тождественная функция с отрицанием	${\displaystyle O_{4}}$	${\displaystyle \{\,{\overline {e_{1}^{1}}}\,\}}$	Тождественная функция.
Унарные функции	${\displaystyle O_{9}}$	${\displaystyle \{\,{\overline {e_{1}^{1}}},0^{1}\,\}}$ ${\displaystyle \{\,{\overline {e_{1}^{1}}},1^{1}\,\}}$	Тождественная функция с отрицанием; Тождественная функция с унарными константами.
Порядок 2
Нули	${\displaystyle R_{3}}$	${\displaystyle \{\,0^{2}\,\}}$	Унарный 0.
Единицы	${\displaystyle R_{2}}$	${\displaystyle \{\,1^{2}\,\}}$	Унарная 1.
Константы	${\displaystyle R_{9}}$	${\displaystyle \{\,0^{2},1^{1}\,\}}$ ${\displaystyle \{\,0^{1},1^{2}\,\}}$	Класс нулей; Класс единиц; Унарные константы.
Тождественная функция с нулями	${\displaystyle R_{7}}$	${\displaystyle \{\,0^{2},e_{1}^{1}\,\}}$	Тождественная функция с унарным 0; Класс нулей.
Тождественная функция с единицами	${\displaystyle R_{5}}$	${\displaystyle \{\,1^{2},e_{1}^{1}\,\}}$	Тождественная функция с унарной 1; Класс единиц.
Тождественная функция с константами	${\displaystyle R_{10}}$	${\displaystyle \{\,0^{2},1^{1},e_{1}^{1}\,\}}$ ${\displaystyle \{\,0^{1},1^{2},e_{1}^{1}\,\}}$	Тождественная функция с нулями; Тождественная функция с единицами; Класс констант; Тождественная функция с унарными константами.
Тождественная функция с отрицанием и константами	${\displaystyle R_{12}}$	${\displaystyle \{\,0^{2},{\overline {e_{1}^{1}}}\,\}}$ ${\displaystyle \{\,1^{2},{\overline {e_{1}^{1}}}\,\}}$	Тождественная функция с константами; Унарные функции.
Селекторы	${\displaystyle R_{1}}$	${\displaystyle \{\,e_{1}^{2}\,\}}$	Тождественная функция.
Селекторы с нулями	${\displaystyle R_{8}}$	${\displaystyle \{\,e_{1}^{2},0^{1}\,\}}$	Класс селекторов; Тождественная функция с нулями.
Селекторы с единицами	${\displaystyle R_{6}}$	${\displaystyle \{\,e_{1}^{2},1^{1}\,\}}$	Класс селекторов; Тождественная функция с единицами.
Селекторы с константами	${\displaystyle R_{11}}$	${\displaystyle \{\,e_{1}^{2},0^{1},1^{1}\,\}}$	Класс селекторов с нулями; Класс селекторов с единицами; Тождественная функция с константами.
Селекторы с отрицаниями	${\displaystyle R_{4}}$	${\displaystyle \{\,{\overline {e_{1}^{2}}}\,\}}$	Класс селекторов; Тождественная функция с отрицаниями.
Несущественные функции	${\displaystyle R_{13}}$	${\displaystyle \{\,{\overline {e_{1}^{2}}},0^{1}\,\}}$ ${\displaystyle \{\,{\overline {e_{1}^{2}}},1^{1}\,\}}$	Класс селекторов с отрицаниями; Класс селекторов с константами; Тождественная функция с отрицанием и константами.
Конъюнкции без фиктивных переменных и констант	${\displaystyle P_{1}}$	${\displaystyle \{\,\land \,\}}$	Тождественная функция.
Конъюнкции без фиктивных переменных с нулями	${\displaystyle P_{3}}$	${\displaystyle \{\,\land ,0^{1}\,\}}$	Конъюнкции без фиктивных переменных и констант; Тождественная функция с нулями.
Конъюнкции без констант	${\displaystyle P_{2}}$	${\displaystyle \{\,\land ,e_{1}^{2}\,\}}$	Класс селекторов; Конъюнкции без фиктивных переменных и констант.
Конъюнкции с нулями	${\displaystyle P_{4}}$	${\displaystyle \{\,\land ,0^{1},e_{1}^{2}\,\}}$	Класс конъюнкций без констант; Класс селекторов с нулями; Конъюнкции без фиктивных переменных с нулями.
Дизъюнкции без фиктивных переменных и констант	${\displaystyle S_{1}}$	${\displaystyle \{\,\lor \,\}}$	Тождественная функция.
Дизъюнкции без фиктивных переменных с единицами	${\displaystyle S_{3}}$	${\displaystyle \{\,\lor ,1^{1}\,\}}$	Дизъюнкции без фиктивных переменных и констант; Тождественная функция с единицами
Дизъюнкции без констант	${\displaystyle S_{2}}$	${\displaystyle \{\,\lor ,e_{1}^{2}\,\}}$	Класс селекторов; Дизъюнкции без фиктивных переменных и констант.
Дизъюнкции с единицами	${\displaystyle S_{4}}$	${\displaystyle \{\,\lor ,1^{1},e_{1}^{2}\,\}}$	Класс дизъюнкций без констант; Класс селекторов с единицами Дизъюнкции без фиктивных переменных с единицами.

В книге Яблонского, Гаврилова и Кудрявцева булевы функции понимаются с точности до добавления и удаления фиктивных переменных, то есть функции, сводящиеся друг у другу добавлением/удалением фиктивных переменных считаются равными. Таким образом, по сути там рассматриваются не сами функции, а множества функций, замкнутые относительно операций добавления и удаления фиктивных переменных. Поэтому проблем с различиями разных определений замкнутых классов там нет: добавление и удаление фиктивных переменных не дают новых функций. Отсюда и идёт определение порядка замкнутого класса через количество существенных переменных функций, поскольку учитывать фиктивные переменные становится бессмысленно^[34]. Решётка замкнутых классов получается изоморфной решёткам замкнутых классов и для определения с удалением фиктивных переменных, и для определения без нульарных функций^[35]. Обозначения классов здесь используются такие же как у Поста, однако из-за того, что некоторые итеративные системы незамкнуты относительно добавления фиктивных переменных, классов становятся меньше. При этом Яблонский, Гаврилов и Кудрявцев для классов, базис как для итеративной системы которых мог породить незамкнутую относительно добавления фиктивных переменных систему, использовали обозначение именно незамкнутой итеративной системы. Из-за этого у них нет классов с обозначениями ${\displaystyle R_{i}}$, а также ${\displaystyle P_{2},P_{4},S_{2},S_{4}}$^[36]. Данная терминология (с понимаем функций с точностью до фиктивных переменных) нередко используется в русской литературе^[37]. Также в литературе встречается такое, что автор понимает функции и замкнутые классы в обычном смысле и решает использовать обозначения Поста, но так, как они используются у Яблонского, Гаврилова и Кудрявцева. Благодаря этому, определённое множество может быть обозначено не так, как у Поста; например множество селекторов, обозначенное у Поста как ${\displaystyle R_{1}}$, у них обозначается как ${\displaystyle O_{1}}$^[38].

Бериш рассматривает клоны и замкнутые классы (в его терминологии полуклоны), которым разрешается иметь нульарные функции, но при этом нельзя удалять фиктивные переменные. В определении через формулы это соответствует определению без упоминания фиктивных переменных с тем изменением, что разрешается иметь нульарные функции. Решётки замкнутых классов и клонов Бериша уже не изоморфны решёткам через первые два определения^[39][40].

• Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.
• Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2000.
• Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука. — 1969
• Алексеев В. Б., Поспелов А. Д. Дискретная математика (курс лекций, II семестр) . Дата обращения: 24 августа 2025.
• Ахметова Н.А., Усманова З.М.Дискретная математика, функции алгебры логики.
• Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста (рус.) / под ред. В. В. Донченко. — М.: Наука, 1966. — 120 с. — 10 000 экз.
• Угольников, А. Б. О замкнутых классах Поста (рус.) // Изв. вузов. Матем. : журнал. — М.: Soviet Math. (Iz. VUZ), 1988. — 16 февраля (т. 32, вып. 7). — С. 79-88.
• Lau, D. Function Algebras on Finite Sets: A Basic Course on Many-Valued Logic and Clone Theory (англ.). — Springer, 2006. — 668 p.
• Post E. L. The Two-Valued Iterative Systems Of Mathematical Logic. — 1941.
• Подколзин А. С. 1 лекция курса «Теория дискретных функций»  (рус.). http://intsys.msu.ru. Дата обращения: 4 мая 2024.
• Подколзин А. С. 2 лекция курса «Теория дискретных функций»  (рус.). http://intsys.msu.ru. Дата обращения: 23 августа 2025.
• Буевич В. А., Подколзина М. А. Критерий полноты S-множеств детерминированных функций (рус.) // Математические вопросы кибернетики : журнал. — М.: ФИЗМАТЛИТ, 2007. — Вып. 16. — С. 191-238.
• Жук Д .Н. Предикатный метод построения решетки Поста (рус.) // Дискретная математика : журнал. — М., 2011. — Т. 23, вып. 2. — С. 115–128.
• Behrisch M. A note on clones with nullary operations (англ.) // MATH-AL. — 2011.
• Behrisch M. Galois theory for semiclones (англ.). — 2015.