Предполные классы

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

• Класс $T_0$ функций, сохраняющих константу 0:
  $T_0=\{f(x_1,\dots ,x_n)|f(0,\dots ,0)=0\}$.
• Класс $T_1$ функций, сохраняющих константу 1:
  $T_1=\{f(x_1,\dots ,x_n)|f(1,\dots ,1)=1\}$.
• Класс $S$ самодвойственных функций:
  $S=\{f(x_1,\dots ,x_n)|f(\overline{x_1},\dots ,\overline{x_n})=\overline{f(x_1,\dots ,x_n)}\}$.
• Класс $M$ монотонных функций:
  $M=\{f(x_1,\dots ,x_n)|\mathrm{\forall }i(a_i\le b_i)\Rightarrow f(a_1,\dots ,a_n)\le f(b_1,\dots ,b_n)\}$.
• Класс $L$ линейных функций — представимых полиномом Жегалкина первой степени:
  $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\}\}$.

Также говорят о предполноте одного замкнутого класса в другом. Класс A предполон в классе B, если замыкание класса A с любой функцией, принадлежащей B, но не принадлежащей A, порождает класс B. Например, класс $M\cap T_0$ предполон в классах $T_0$ и $M$.

В многозначной логике предполные классы аналогично определяются как замкнутые классы, обладающие свойством — замыкание объединения этого класса с любой функцией из $P_k$, не принадлежащей ему, порождает все $P_k$. В случае k>2 структура предполных классов описывается теоремой Розенберга.

Литература

• Яблонский С. В. Введение в дискретную математику. — М.: Наука. — 1986