Замкнутый класс

Замкнутый класс (в теории функциональных систем, в частности, в алгебре логики) — это множество булевых функций (функций, принимающих значения 0 или 1 от аргументов, также принимающих значения 0 или 1), которое содержит суперпозицию (подстановку) любых своих функций. Иными словами, если из функций, принадлежащих данному классу, с помощью операций подстановки и переименования переменных образовать новую функцию, то эта новая функция также будет принадлежать этому классу. Понятие замкнутого класса является фундаментальным в теории булевых функций и тесно связано с понятием функциональной полноты, а также с критерием Поста — одним из центральных результатов в математической логике и кибернетике.

Определение и основные понятия

Пусть \( P_2 \) — множество всех булевых функций (функций алгебры логики) от конечного числа переменных. Подмножество \( K \subseteq P_2 \) называется замкнутым классом, если для любой функции \( f(x_1, \dots, x_n) \in K \) и любых функций \( g_1, \dots, g_n \in K \) (возможно, от других переменных) функция \( f(g_1, \dots, g_n) \) также принадлежит \( K \). Операция, при которой из исходных функций строится новая, называется суперпозицией (или подстановкой).

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

Замыкание

Для произвольного множества функций \( M \subseteq P_2 \) его замыканием (обозначается \([M]\)) называется множество всех функций, которые можно получить из функций \( M \) с помощью суперпозиции. Множество \( M \) называется замкнутым, если \([M] = M\). Таким образом, замкнутый класс — это множество, совпадающее со своим замыканием.

Классификация замкнутых классов (предполные классы Поста)

Американский математик Эмиль Пост в 1920-х годах (опубликовано в 1941 году) полностью описал решётку всех замкнутых классов в двузначной логике. Он выделил пять основных (предполных) замкнутых классов, которые не являются полными (то есть их замыкание не совпадает с \( P_2 \)), но добавление любой функции, не принадлежащей классу, делает систему полной. Эти классы называются предполными или максимальными. К ним относятся:

1. Класс функций, сохраняющих константу 0 (\( T_0 \))

Класс \( T_0 \) состоит из всех булевых функций, которые на нулевом наборе аргументов (все аргументы равны 0) принимают значение 0. Формально: \( f(0, 0, \dots, 0) = 0 \). Примеры: конъюнкция (\( x \land y \)), дизъюнкция (\( x \lor y \)), константа 0, функция \( x \). Функция, не принадлежащая \( T_0 \): отрицание (\( \neg x \)), так как \( \neg 0 = 1 \).

2. Класс функций, сохраняющих константу 1 (\( T_1 \))

Класс \( T_1 \) состоит из всех булевых функций, которые на единичном наборе аргументов (все аргументы равны 1) принимают значение 1. Формально: \( f(1, 1, \dots, 1) = 1 \). Примеры: конъюнкция, дизъюнкция, константа 1, функция \( x \). Функция, не принадлежащая \( T_1 \): отрицание (\( \neg 1 = 0 \)).

3. Класс самодвойственных функций (\( S \))

Функция \( f(x_1, \dots, x_n) \) называется самодвойственной, если она совпадает со своей двойственной функцией, то есть \( f(x_1, \dots, x_n) = \neg f(\neg x_1, \dots, \neg x_n) \). Класс \( S \) состоит из всех таких функций. Примеры: функция \( x \) (тождественная), отрицание (\( \neg x \)), функция \( x \oplus y \oplus z \) (сложение по модулю 2 от трёх переменных). Функция, не принадлежащая \( S \): конъюнкция, так как \( x \land y \neq \neg ( \neg x \land \neg y ) = x \lor y \).

4. Класс монотонных функций (\( M \))

Функция \( f(x_1, \dots, x_n) \) называется монотонной, если для любых двух наборов аргументов \( \alpha = (\alpha_1, \dots, \alpha_n) \) и \( \beta = (\beta_1, \dots, \beta_n) \) таких, что \( \alpha_i \leq \beta_i \) для всех \( i \) (покомпонентное сравнение), выполняется \( f(\alpha) \leq f(\beta) \). Класс \( M \) состоит из всех монотонных функций. Примеры: конъюнкция, дизъюнкция, константы 0 и 1, функция \( x \). Функция, не принадлежащая \( M \): отрицание, так как \( 0 \leq 1 \), но \( \neg 0 = 1 \not\leq \neg 1 = 0 \).

5. Класс линейных функций (\( L \))

Функция \( f(x_1, \dots, x_n) \) называется линейной, если её можно представить в виде полинома Жегалкина (суммы по модулю 2) первой степени, то есть \( 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\} \). Класс \( L \) состоит из всех таких функций. Примеры: константы 0 и 1, функция \( x \), отрицание (\( \neg x = 1 \oplus x \)), функция \( x \oplus y \). Функция, не принадлежащая \( L \): конъюнкция (\( x \land y \)), так как её полином Жегалкина имеет степень 2: \( x \land y = x \oplus y \oplus (x \oplus y) \).

Критерий полноты (теорема Поста)

Теорема Поста (критерий функциональной полноты) утверждает, что система булевых функций \( M \) является полной (то есть её замыкание \([M] = P_2\)) тогда и только тогда, когда она не содержится целиком ни в одном из пяти предполных классов: \( T_0, T_1, S, M, L \). Иными словами, для полноты системы необходимо и достаточно, чтобы в ней нашлась функция, не сохраняющая 0, функция, не сохраняющая 1, несамодвойственная функция, немонотонная функция и нелинейная функция.

Этот критерий является основным инструментом для проверки, можно ли с помощью данного набора логических операций выразить любую булеву функцию. Например, система {И, НЕ} (конъюнкция и отрицание) является полной, так как конъюнкция принадлежит \( T_0, T_1, M \), но не принадлежит \( S \) и \( L \), а отрицание не принадлежит \( T_0, T_1, M \), но принадлежит \( S \) и \( L \). Вместе они покрывают все пять классов.

Решётка замкнутых классов

Эмиль Пост показал, что множество всех замкнутых классов в \( P_2 \) образует счётную решётку (частично упорядоченное множество), в которой каждый класс имеет конечное или счётное число подклассов. Всего существует бесконечно много замкнутых классов, но все они могут быть описаны через комбинации пяти предполных классов и их пересечений. Например, класс \( T_0 \cap T_1 \) — это функции, сохраняющие обе константы (например, конъюнкция, дизъюнкция, константы 0 и 1). Класс \( T_0 \cap L \) — это линейные функции, сохраняющие 0, и так далее.

Решётка Поста имеет сложную структуру, включающую несколько бесконечных серий классов (например, классы, порождённые одной функцией, или классы, связанные с монотонными функциями). Однако для практических задач в теории схем и математической логике достаточно знать пять предполных классов и критерий полноты.

Применение

Понятие замкнутого класса и критерий Поста имеют широкое применение:

• Теория цифровых схем: позволяет определить, из каких логических элементов (например, И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ) можно построить любую комбинационную схему. Например, элемент И-НЕ (штрих Шеффера) сам по себе образует полную систему, так как он не принадлежит ни одному из пяти предполных классов.
• Математическая логика: используется для изучения выразительных возможностей формальных языков и систем аксиом.
• Кибернетика и теория автоматов: применяется при синтезе и минимизации логических схем, а также в задачах распознавания образов и машинного обучения (например, в нейронных сетях с пороговыми функциями).

Интересные факты

• Теорема Поста является одним из первых примеров полной классификации замкнутых классов в многозначной логике. Для логик с числом значений больше двух (например, трёхзначной) задача описания всех замкнутых классов значительно сложнее и до сих пор полностью не решена.
• Пять предполных классов Поста иногда называют «постовскими классами». Они являются максимальными по включению: любой замкнутый класс, не совпадающий с \( P_2 \), содержится хотя бы в одном из них.
• В русскоязычной литературе замкнутые классы часто изучаются в курсе «Дискретная математика» или «Математическая логика и теория алгоритмов» в рамках темы «Функциональные системы».

Источники

• Пост Э. Л. «Введение в общую теорию элементарных предложений» (1941) — оригинальная работа.
• Яблонский С. В. «Введение в дискретную математику» (1986) — классический учебник, содержащий подробное изложение теории замкнутых классов.
• Гаврилов Г. П., Сапоженко А. А. «Задачи и упражнения по дискретной математике» (2004) — сборник задач с теоретическим введением.
• Кузнецов О. П., Адельсон-Вельский Г. М. «Дискретная математика для инженера» (1988) — прикладной аспект.