Меню Главная Случайная статья Настройки Предполный класс Материал из https://ru.wikipedia.org Предполный класс в теории булевых функций — замкнутый класс булевых функций, обладающий следующим свойством: замыкание объединения этого класса с любой булевой функцией, не принадлежащей ему, порождает все ${\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}$ предполон в классе 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.