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

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

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

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

Литература

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