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

Предполный класс в теории булевых функций — замкнутый класс булевых функций, обладающий следующим свойством — замыкание объединения этого класса с любой булевой функцией, не принадлежащей ему, порождает все $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}\leq b_{i})\Rightarrow f(a_{1},\dots ,a_{n})\leq 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_{1}x_{1}\oplus \dots \oplus a_{n}x_{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