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

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

В 1941 году Эмиль Пост представил полное описание системы замкнутых классов, называемое также решеткой Поста.

Свойства замыкания функции с переменными

1. Любое множество является подмножеством своего замыкания: $A\subseteq[A]$.
2. Замыкание подмножества является подмножеством замыкания: $A\subseteq B \Rightarrow [A]\subseteq[B]$.
   Следует заметить, что из строгого вложения множеств следует лишь нестрогое вложение их замыканий: $A\subset B \Rightarrow [A]\subseteq[B]$.
3. Многократное применение операции замыкания эквивалентно однократному: $[[A]]=[A]$.

Примеры замкнутых классов

Множество $P_2$ всех возможных булевых функций замкнуто.

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

• Класс $T_0$ функций, сохраняющих константу 0:
  $T_0=\left\{f(x_1,\dots,x_n)|f(0,\dots,0)=0\right\}$.
• Класс $T_1$ функций, сохраняющих константу 1:
  $T_1=\left\{f(x_1,\dots,x_n)|f(1,\dots,1)=1\right\}$.
• Класс $S$ самодвойственных функций:
  $S=\left\{f(x_1,\dots,x_n)|f(\overline{x_1},\dots,\overline{x_n})=\overline{f(x_1,\dots,x_n)}\right\}$.
• Класс $M$ монотонных функций:
  $M=\left\{f(x_1,\dots,x_n)|\forall i (a_i\le b_i) \Rightarrow f(a_1,\dots,a_n)\le f(b_1,\dots,b_n)\right\}$.
• Класс $L$ линейных функций:
  $L=\left\{f(x_1,\dots,x_n)|f(x_1,\dots,x_n)=a_0\oplus a_1x_1\oplus\dots\oplus a_nx_n,a_i\in\{0,1\}\right\}$.

Любой замкнутый класс булевых функций, отличный от $P_2$, целиком содержится хотя бы в одном из пяти предполных классов.

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

• Класс конъюнкций K, являющийся замыканием множества $\{\wedge,0,1\}$. Он представляет собой множество функций вида $c_0\wedge(c_1\vee x_1)\wedge\ldots\wedge(c_n\vee x_n)$.
• Класс дизъюнкций D, являющийся замыканием множества $\{\vee,0,1\}$. Он представляет собой множество функций вида $c_0\vee(c_1\wedge x_1)\vee\ldots\vee(c_n\wedge x_n)$.
• Класс функций одной переменной U, содержащий только константы, отрицание и селектор (функцию, равную одному из своих аргументов на всех наборах их значений).
• Класс $O^m$ функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает нулевое значение, найдется переменная, также принимающая нулевое значение на всех этих наборах.
• Класс $O^\infty$ функций, для которых выполнено условие $f(x_1,\ldots,x_n)\ge x_i$, где $x_i$ — одна из переменных функции.
• Класс $I^m$ функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает единичное значение, найдется переменная, также принимающая единичное значение на всех этих наборах.
• Класс $I^\infty$ функций, для которых выполнено условие $f(x_1,\ldots,x_n)\le x_i$, где $x_i$ — одна из переменных функции.

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

Некоторые свойства замкнутых классов

• Непустое пересечение замкнутых классов снова является замкнутым классом.
• Объединение замкнутых классов может замкнутым классом не являться.
• Замкнутый класс булевых функций, содержащий не только константы, обязательно содержит тождественную функцию.
• Дополнение замкнутого класса булевых функций до множества всех булевых функций $P_2$ замкнутым классом не является.

Полные системы функций

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

Критерий Поста формулирует необходимое и достаточное условие полноты системы булевых функций:
Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов $T_0$, $T_1$, $S$, $M$, $L$.
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать функцию Шеффера (отрицание конъюнкции).

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

• $\left\{\land,\lor,\neg\right\}$ (конъюнкция, дизъюнкция, отрицание);
• $\left\{\land,\oplus,1\right\}$ (конъюнкция, сложение по модулю 2, константа 1).

Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.

Полная система функций называется базисом, если она перестаёт быть полной при исключении из неё любого элемента. Первая из упоминавшихся выше полных систем базисом не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является базисом — все три её элемента необходимы для полноты. Максимально возможное число булевых функций в базисе — 4.

Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему $\left\{\oplus,1\right\}$ можно назвать базисом класса линейных функций.

Примечания

Литература

• Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.
• Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2000.
• Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука. — 1969
• Алексеев В. Б. Дискретная математика (курс лекций, II семестр). Сост. А. Д. Поспелов
• Ахметова Н.А., Усманова З.М.Дискретная математика, функции алгебры логики.

Для улучшения этой статьи желательно?: Проставив сноски, внести более точные указания на источники.