Теорема Поста¶

Теорема Поста — это фундаментальное утверждение в математической логике и теории булевых функций, устанавливающее необходимое и достаточное условие для того, чтобы система булевых функций была функционально полной, то есть позволяла выразить любую булеву функцию. Теорема была сформулирована и доказана американским математиком Эмилем Постом в 1920-х годах и является одним из центральных результатов в теории функциональных систем.

¶История

¶Предпосылки

В конце XIX — начале XX века развитие математической логики, связанное с работами Джорджа Буля, Августа де Моргана и Чарльза Пирса, привело к необходимости изучения свойств булевых функций. Ключевым вопросом стало определение того, какие наборы логических операций (например, конъюнкция, дизъюнкция, отрицание) являются достаточными для построения произвольного логического выражения.

¶Работа Эмиля Поста

Эмиль Пост в своей диссертации 1921 года и последующих публикациях (особенно в статье 1941 года «Двухзначные итеративные системы») систематически исследовал все возможные замкнутые классы булевых функций. Он показал, что существует ровно пять предпорных классов (максимальных по включению замкнутых классов, не являющихся полными), и что система функций полна тогда и только тогда, когда она не содержится целиком ни в одном из этих классов. Этот результат стал известен как теорема Поста.

¶Основные понятия

Для понимания теоремы Поста необходимо определить несколько ключевых понятий теории булевых функций.

¶Булева функция

Булевой функцией от \( n \) переменных называется отображение \( f: \{0,1\}^n \to \{0,1\} \). Примеры: конъюнкция (\( x \land y \)), дизъюнкция (\( x \lor y \)), отрицание (\( \neg x \)), импликация (\( x \rightarrow y \)), сложение по модулю 2 (XOR, \( x \oplus y \)).

¶Суперпозиция

Суперпозиция — это способ получения новой функции из заданных путём подстановки одних функций в другие, переименования переменных и отождествления переменных. Например, из функций \( \neg \) и \( \land \) можно получить функцию \( \neg (x \land y) \).

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

Множество булевых функций \( K \) называется замкнутым классом, если оно содержит все функции, получаемые из функций \( K \) с помощью операции суперпозиции. Иными словами, если \( f \in K \) и \( g \in K \), то любая функция, полученная их подстановкой друг в друга, также принадлежит \( K \).

¶Замыкание

Замыканием системы функций \( A \) (обозначается \( [A] \)) называется наименьший замкнутый класс, содержащий \( A \). Это множество всех функций, которые можно получить из \( A \) с помощью суперпозиции.

¶Функциональная полнота

Система булевых функций \( A \) называется функционально полной, если её замыкание \( [A] \) совпадает с множеством всех булевых функций \( P_2 \). То есть любая булева функция может быть выражена через функции из \( A \) с помощью суперпозиции.

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

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

¶Класс \( T_0 \) — функции, сохраняющие 0

Класс \( T_0 \) состоит из всех булевых функций \( f \), для которых выполняется условие: \( f(0, 0, \dots, 0) = 0 \). То есть на нулевом наборе аргументов функция принимает значение 0.

• Примеры: конъюнкция (\( 0 \land 0 = 0 \)), дизъюнкция (\( 0 \lor 0 = 0 \)), сложение по модулю 2 (\( 0 \oplus 0 = 0 \)).
• Контрпример: отрицание (\( \neg 0 = 1 \)), импликация (\( 0 \rightarrow 0 = 1 \)).

¶Класс \( T_1 \) — функции, сохраняющие 1

Класс \( T_1 \) состоит из всех булевых функций \( f \), для которых выполняется условие: \( f(1, 1, \dots, 1) = 1 \). То есть на единичном наборе аргументов функция принимает значение 1.

• Примеры: конъюнкция (\( 1 \land 1 = 1 \)), дизъюнкция (\( 1 \lor 1 = 1 \)), импликация (\( 1 \rightarrow 1 = 1 \)).
• Контрпример: отрицание (\( \neg 1 = 0 \)), сложение по модулю 2 (\( 1 \oplus 1 = 0 \)).

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

Класс \( S \) состоит из всех булевых функций \( f \), для которых выполняется условие: \( f(x_1, x_2, \dots, x_n) = \neg f(\neg x_1, \neg x_2, \dots, \neg x_n) \). Такие функции называются самодвойственными.

• Примеры: отрицание (\(\neg x\)), функция \( x \), функция \( \neg (x \oplus y) \) (эквивалентность).
• Контрпример: конъюнкция (не является самодвойственной, так как \( x \land y \neq \neg(\neg x \land \neg y) \)).

¶Класс \( M \) — монотонные функции

Класс \( M \) состоит из всех булевых функций, которые являются монотонными. Функция \( f \) называется монотонной, если для любых двух наборов аргументов \( \alpha \) и \( \beta \) таких, что \( \alpha \leq \beta \) (покомпонентно), выполняется \( f(\alpha) \leq f(\beta) \). То есть увеличение значений аргументов не приводит к уменьшению значения функции.

• Примеры: конъюнкция, дизъюнкция, константы 0 и 1.
• Контрпример: отрицание (\( 0 \leq 1 \), но \( \neg 0 = 1 \not\leq \neg 1 = 0 \)), сложение по модулю 2 (\( 0 \oplus 1 = 1 \), но \( 1 \oplus 1 = 0 \) — нарушение монотонности).

¶Класс \( L \) — линейные функции

Класс \( L \) состоит из всех булевых функций, которые могут быть представлены в виде полинома Жегалкина (суммы по модулю 2) степени не выше 1. Такие функции имеют вид: \( 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\} \).

• Примеры: константы, отрицание (\( 1 \oplus x \)), сложение по модулю 2 (\( x \oplus y \)), эквивалентность (\( 1 \oplus x \oplus y \)).
• Контрпример: конъюнкция (\( x \land y \)), дизъюнкция (\( x \lor y = x \oplus y \oplus xy \) — содержит член \( xy \) степени 2).

¶Формулировка теоремы

Теорема Поста утверждает: Система булевых функций \( A \) является функционально полной тогда и только тогда, когда она не содержится целиком ни в одном из пяти классов: \( T_0, T_1, S, M, L \).

Другими словами, для полноты системы необходимо и достаточно, чтобы в ней нашлась хотя бы одна функция, не сохраняющая 0, хотя бы одна, не сохраняющая 1, хотя бы одна несамодвойственная, хотя бы одна немонотонная и хотя бы одна нелинейная.

¶Критерий полноты (таблица)

¶Примеры применения

¶Пример 1: Система {\( \land, \lor, \neg \)}

• \( \neg \) не сохраняет 0 и 1, не является монотонной.
• \( \land \) не является самодвойственной и нелинейна.
• \( \lor \) не является самодвойственной и нелинейна.
• Система не содержится ни в одном из классов, следовательно, полна. Это классический базис Буля.

¶Пример 2: Система {\( \downarrow \)} (стрелка Пирса)

• \( x \downarrow y = \neg (x \lor y) \).
• Проверка: \( 0 \downarrow 0 = 1 \) — не сохраняет 0; \( 1 \downarrow 1 = 0 \) — не сохраняет 1; несамодвойственна (проверяется вычислением); немонотонна (так как \( 0 \leq 1 \), но \( 0 \downarrow 0 = 1 \not\leq 0 \downarrow 1 = 0 \)); нелинейна (полином Жегалкина: \( 1 \oplus x \oplus y \oplus xy \)). Система полна.

¶Пример 3: Система {\( \land, \oplus, 1 \)}

• \( \land \) — нелинейна, несамодвойственна.
• \( \oplus \) — не сохраняет 0? \( 0 \oplus 0 = 0 \) — сохраняет. Не сохраняет 1? \( 1 \oplus 1 = 0 \) — не сохраняет 1.
• \( 1 \) — константа 1 сохраняет 1, не сохраняет 0.
• Система не содержится ни в одном классе, полна. Это базис Жегалкина.

¶Пример 4: Неполная система {\( \land, \lor \)}

• Обе функции сохраняют 0 и 1, монотонны, несамодвойственны и нелинейны.
• Система содержится в классах \( T_0, T_1, M \). Следовательно, неполна. Из них нельзя получить, например, отрицание.

¶Следствия и обобщения

Теорема Поста имеет ряд важных следствий:

1. Существование минимальных полных систем. Любая полная система содержит полную подсистему, состоящую не более чем из четырёх функций (по одной на каждый «недостающий» класс).
2. Классификация замкнутых классов. Теорема Поста является частью более общей теории, которая описывает решётку всех замкнутых классов булевых функций. Эмиль Пост показал, что эта решётка счётна и имеет сложную структуру, включающую бесконечные цепочки классов.
3. Обобщения на многозначные логики. Для \( k \)-значных логик (\( k > 2 \)) ситуация значительно сложнее. Полная классификация замкнутых классов для \( k \geq 3 \) неизвестна, и теорема Поста в её исходном виде не обобщается напрямую. Однако существуют аналогичные критерии для некоторых частных случаев.

¶Критика и ограничения

Хотя теорема Поста является мощным инструментом, она имеет ограничения:

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

¶Источники

1. Post, E. L. (1941). The two-valued iterative systems of mathematical logic. Annals of Mathematics Studies, 5. Princeton University Press.
2. Яблонский, С. В. (1986). Введение в дискретную математику. Москва: Наука.
3. Гаврилов, Г. П., Сапоженко, А. А. (1992). Задачи и упражнения по дискретной математике. Москва: Наука.
4. Кузнецов, О. П. (2002). Дискретная математика для инженера. Санкт-Петербург: Лань.