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

Предполный класс в теории булевых функций - замкнутый класс булевых функций, обладающий следующим свойством - замыкание объединения этого класса с любой булевой функцией, не принадлежащей ему, порождает все $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\}$.

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

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

Литература

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