Классы Поста: замкнутые классы булевых функций

Классы Поста - это особый набор замкнутых классов булевых функций, через который формулируется критерий функциональной полноты. Замкнутый класс - это множество функций, устойчивое к операции суперпозиции: если подставлять функции класса друг в друга, результат снова останется в классе. Эмиль Пост в 1921 году описал решётку всех таких классов и доказал теорему: система булевых функций полна тогда и только тогда, когда она не целиком вкладывается ни в один из пяти специальных предполных классов. Инструмент ниже соберёт по вашему выбору функций запрос и проверит, образуют ли они полную систему - то есть базис, из которого суперпозицией строится любая булева функция.

Что такое замкнутый класс

Булева функция - это отображение из набора нулей и единиц снова в ноль или единицу, то есть $f: \{0,1\}^n \to \{0,1\}$. Множество всех булевых функций обозначают $P_2$ («два» - это размер множества значений). Над функциями определена операция суперпозиции: подстановка одних функций на места аргументов других, переименование и отождествление переменных. Так из дизъюнкции и отрицания строится, например, импликация.

Класс функций $K$ называют замкнутым, если любая суперпозиция функций из $K$ снова принадлежит $K$. Формально замыкание $[K]$ - это множество всех функций, выразимых через $K$ суперпозицией; класс замкнут, когда $[K] = K$. Само множество $P_2$ тривиально замкнуто, как и пустой класс. Между ними лежит вся решётка промежуточных замкнутых классов, которую и описал Пост.

Понятие замыкания тесно связано с понятием полной системы: система функций $\Sigma$ полна, если её замыкание совпадает со всем $P_2$, то есть $[\Sigma] = P_2$. Полная система без избыточности (удаление любой функции нарушает полноту) называется базисом. Классическая пара примеров полных систем - $\{\&, \lor, \neg\}$ и одиночные базисы из штриха Шеффера или стрелки Пирса.

Рассчитать для своей задачи

Пять предполных классов Поста

Критерий полноты опирается на пять конкретных замкнутых классов. Каждый из них предполный (или максимальный): он не совпадает с $P_2$, но добавление к нему любой не входящей в него функции порождает суперпозицией всё $P_2$. Именно эти пять классов перекрывают «все способы остаться неполной системой».

Класс $T_0$ - функции, сохраняющие ноль. Сюда входят те $f$, для которых $f(0, 0, \dots, 0) = 0$. Дизъюнкция и конъюнкция сохраняют ноль, отрицание - нет. Проверяется по верхней строке таблицы истинности.

Класс $T_1$ - функции, сохраняющие единицу: $f(1, 1, \dots, 1) = 1$. Проверяется по нижней строке таблицы. Конъюнкция и дизъюнкция сохраняют единицу, отрицание снова выпадает.

Класс $S$ - самодвойственные функции. Функция самодвойственна, если $f(\bar{x}_1, \dots, \bar{x}_n) = \overline{f(x_1, \dots, x_n)}$: инверсия всех входов инвертирует выход. Самодвойственна, например, медиана трёх переменных $xy \lor yz \lor zx$.

Класс $M$ - монотонные функции. Монотонность означает: если по всем аргументам набор $\alpha$ не больше набора $\beta$ (покоординатно $\alpha \le \beta$), то $f(\alpha) \le f(\beta)$. Усиление любого входа с нуля до единицы не может перевести выход с единицы в ноль. Конъюнкция и дизъюнкция монотонны, отрицание - нет.

Класс $L$ - линейные функции. Линейная функция представима полиномом Жегалкина без произведений переменных: $f = c_0 \oplus c_1 x_1 \oplus \dots \oplus c_n x_n$, где $\oplus$ - сложение по модулю два. Линейны отрицание и сложение по модулю два; конъюнкция - нет, у неё в полиноме есть член $x_1 x_2$.

Рассчитать для своей задачи

Теорема Поста о функциональной полноте

Главный результат формулируется удивительно компактно. Система булевых функций $\Sigma$ полна тогда и только тогда, когда она не содержится целиком ни в одном из пяти классов $T_0$, $T_1$, $S$, $M$, $L$. Иначе говоря, для каждого из пяти классов в системе должна найтись хотя бы одна функция, не принадлежащая этому классу.

Удобный способ проверки - таблица Поста: строки соответствуют функциям системы, столбцы - пяти классам, в ячейке ставится плюс, если функция входит в класс. Система полна, когда в каждом столбце есть хотя бы одна функция вне класса, то есть ни один столбец не заполнен плюсами целиком.

$\Sigma \text{ полна} \iff \Sigma \not\subseteq T_0 \ \wedge\ \Sigma \not\subseteq T_1 \ \wedge\ \Sigma \not\subseteq S \ \wedge\ \Sigma \not\subseteq M \ \wedge\ \Sigma \not\subseteq L$

Почему именно пять и почему этого достаточно - потому что каждый из них предполный (максимальный замкнутый класс, отличный от $P_2$), а любой собственный замкнутый класс содержится хотя бы в одном предполном. Если бы система целиком сидела в каком-то замкнутом классе, она сидела бы и в накрывающем его предполном - и не была бы полной. Пять перечисленных классов исчерпывают все предполные классы в $P_2$.

Разбор примера: проверяем штрих Шеффера

Покажем механику на классическом одиночном базисе - штрихе Шеффера $x \mid y = \overline{x \& y}$ (антиконъюнкция, «И-НЕ»). Таблица истинности: на наборе $(0,0)$ функция даёт $1$, на $(1,1)$ даёт $0$.

Сохранение нуля: $f(0,0) = 1 \ne 0$, значит функция не сохраняет ноль, $f \notin T_0$. Сохранение единицы: $f(1,1) = 0 \ne 1$, значит $f \notin T_1$. Самодвойственность: $f(0,0) = 1$ и $f(1,1) = 0$ - инверсия входов инвертирует выход на этой паре, но проверка на остальных наборах показывает $f(0,1) = f(1,0) = 1$, тогда как самодвойственность требует $f(0,1) = \overline{f(1,0)}$, то есть $1 = 0$ - неверно, $f \notin S$. Монотонность: при переходе от $(0,0)$ к $(1,1)$ значение падает с $1$ до $0$, монотонность нарушена, $f \notin M$. Линейность: полином Жегалкина штриха равен $1 \oplus xy$, в нём есть произведение $xy$, значит $f \notin L$.

Функция не лежит ни в одном из пяти классов - значит одного штриха Шеффера достаточно для полноты. То же верно для стрелки Пирса $x \downarrow y = \overline{x \lor y}$. Эти две функции - единственные булевы функции двух переменных, образующие базис в одиночку.

Рассчитать для своей задачи

Связь с решёткой Поста и предполными классами

Пять классов критерия - вершина гораздо более богатой структуры. Эмиль Пост описал полную решётку всех замкнутых классов $P_2$ относительно включения. Эта решётка счётна, у неё есть наибольший элемент $P_2$, наименьший (класс констант и проекций) и сложная сеть промежуточных классов, многие из которых задаются бесконечными сериями условий сохранения предикатов.

Для критерия полноты важна только верхушка: предполные классы - это атомы «снизу от $P_2$», максимальные собственные замкнутые классы. В $P_2$ их ровно пять, и это редкая удача - в логиках с тремя и более значениями ($P_k$ при $k \ge 3$) предполных классов уже бесконечно много, и аналог простого критерия Поста там не работает. Конечность системы предполных классов в двузначной логике - то, что делает теорему Поста таким удобным инструментом.

Понимание решётки помогает в смежных задачах дискретной математики: линейный класс $L$ возникает как естественная граница при работе с полиномами Жегалкина, а двойственность связывает $T_0$ и $T_1$ через инверсию входов. Те же приёмы суперпозиции и подсчёта структур встречаются и в теории графов - например, при выводе хроматического полинома графа.

Частые ошибки

• Проверяют принадлежность только нужным классам. Для полноты надо убедиться, что для каждого из пяти классов в системе есть функция вне него; пропуск даже одного столбца таблицы Поста ломает вывод.
• Путают «функция полна» и «функция не в классе». Одиночная функция образует базис, только если она выпадает сразу из всех пяти классов; принадлежность хотя бы к одному классу делает её недостаточной для полноты в одиночку.
• Считают отрицание линейным «потому что простое». Отрицание $\bar{x} = 1 \oplus x$ действительно линейно, но конъюнкцию по той же логике в $L$ записать нельзя - её полином Жегалкина содержит произведение.
• Забывают, что самодвойственность проверяется на всех наборах. Совпадение на паре крайних наборов не гарантирует самодвойственности; нужно проверить тождество $f(\bar{x}) = \overline{f(x)}$ на всей таблице.
• Смешивают замкнутость и полноту. Замкнутый класс - устойчивый к суперпозиции; полная система - та, чьё замыкание равно всему $P_2$. Это разные свойства.

FAQ

Сколько всего предполных классов в двузначной логике? Ровно пять: $T_0$, $T_1$, $S$, $M$, $L$. Именно их конечность и даёт простой критерий полноты. В $k$-значных логиках при $k \ge 3$ предполных классов бесконечно много.

Почему штрих Шеффера полон сам по себе? Потому что он не сохраняет ноль, не сохраняет единицу, не самодвойствен, не монотонен и не линеен - выпадает сразу из всех пяти классов Поста. По теореме Поста этого достаточно для полноты системы из одной функции.

Чем замкнутый класс отличается от полной системы? Замкнутый класс устойчив к суперпозиции: $[K] = K$. Полная система $\Sigma$ - та, чьё замыкание равно всему множеству булевых функций: $[\Sigma] = P_2$. Полная система не содержится целиком ни в одном собственном замкнутом классе.

Коротко

Классы Поста - это пять предполных замкнутых классов булевых функций: сохраняющие ноль $T_0$, сохраняющие единицу $T_1$, самодвойственные $S$, монотонные $M$ и линейные $L$. Замкнутый класс устойчив к суперпозиции, а система функций полна по теореме Поста тогда и только тогда, когда она не вкладывается целиком ни в один из этих пяти классов. Удобная проверка - таблица Поста: в каждом столбце должна быть хотя бы одна функция вне соответствующего класса.