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

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

• класс ${\displaystyle T_{0}}$ функций, сохраняющих константу 0:
  ${\displaystyle T_{0}=\left\{f(x_{1},\dots ,x_{n})|f(0,\dots ,0)=0\right\}}$;
• класс ${\displaystyle T_{1}}$ функций, сохраняющих константу 1:
  ${\displaystyle T_{1}=\left\{f(x_{1},\dots ,x_{n})|f(1,\dots ,1)=1\right\}}$;
• класс ${\displaystyle S}$ самодвойственных функций:
  ${\displaystyle S=\left\{f(x_{1},\dots ,x_{n})|f({\overline {x_{1}}},\dots ,{\overline {x_{n}}})={\overline {f(x_{1},\dots ,x_{n})}}\right\}}$;
• класс ${\displaystyle M}$ монотонных функций:
  ${\displaystyle 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\}}$;
• класс ${\displaystyle L}$ линейных функций — представимых полиномом Жегалкина первой степени:
  ${\displaystyle 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\}}$.

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

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

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