Меню Главная Случайная статья Настройки Пересечения предполных классов булевой логики Материал из https://ru.wikipedia.org Пересечения предполных классов булевой логики являются замкнутыми классами в ${\displaystyle P_{2}}$. Пересечениями предполных классов не исчерпываются все замкнутые классы в ${\displaystyle P_{2}}$, так как пересечений конечное число, а всего замкнутых классов счётное число. Содержание 1 Функции, сохраняющие константы 2 Монотонные функции без 1 3 Монотонные функции без 0 4 Монотонные функции без констант 5 Линейные функции, сохраняющие 0 6 Линейные функции, сохраняющие 1 7 Линейные самодвойственные функции 8 Самодвойственные функции, сохраняющие константы 9 Линейные функции, сохраняющие константы 10 Монотонные самодвойственные функции 11 Селекторы с константами 12 Селекторы с 0 13 Селекторы с 1 14 Селекторы 15 Примечания 16 Литература Функции, сохраняющие константы Функция, сохраняющая константы, — функция ${\displaystyle f\colon E_{2}^{n}\to E_{2}}$, для которой выполняются два условия: ${\displaystyle f(0,\ldots ,0)=0}$; ${\displaystyle f(1,\ldots ,1)=1}$. Примеры: тождественная функция ${\displaystyle x}$, конъюнкция ${\displaystyle \land }$, дизъюнкция ${\displaystyle \lor }$, функция голосования ${\displaystyle m(x,y,z)}$, ${\displaystyle x\oplus y\oplus z}$. Для ${\displaystyle n>0}$ количество ${\displaystyle n}$-арных функций, сохраняющих константы, равно ${\displaystyle 2^{2^{n}-2}}$. Нульарных функций, сохраняющих константы, нет. Класс функций, сохраняющих константы, является замкнутым и равен ${\displaystyle T_{0}\cap T_{1}}$ (обозначение Поста — ${\displaystyle C_{4}}$[1]). Он является предполным в ${\displaystyle T_{0}}$ и ${\displaystyle T_{1}}$. В ${\displaystyle T_{0}\cap T_{1}}$ 4 предполных класса: ${\displaystyle T_{0,2}\cap T_{1}}$, ${\displaystyle T_{1,2}\cap T_{0}}$, ${\displaystyle M\cap T_{0}\cap T_{1}}$, ${\displaystyle T_{0}\cap S=T_{1}\cap S}$[2]. Примеры базисов: ${\displaystyle \{x\oplus y\oplus z,\land \}}$, ${\displaystyle \{x\oplus y\oplus z,\lor \}}$, ${\displaystyle \{xy\oplus y\oplus z\}}$[3]. Порядок ${\displaystyle T_{0}\cap T_{1}}$ равен ${\displaystyle 3}$[4]. В ${\displaystyle T_{0}\cap T_{1}}$ есть шефферовы функции, например ${\displaystyle xy\oplus y\oplus z}$. Минимальное количество функций в базисе — ${\displaystyle 1}$, максимальное — ${\displaystyle 2}$. Функция сохраняет константы тогда и только тогда, когда она является ${\displaystyle \alpha }$-функцией (то есть отождествление переменных ${\displaystyle f(x,\ldots ,x)=x}$). Поэтому, класс ${\displaystyle T_{0}\cap T_{1}}$ можно определить как множество всех ${\displaystyle \alpha }$-функций. Именно так он определялся в некоторой старой литературе, включая монографию Поста[5][1]. Класс ${\displaystyle T_{0}\cap T_{1}}$ самодвойственен. Монотонные функции без 1 Монотонные функции, не равные тождественно 1, образуют замкнутый класс, равный ${\displaystyle M\cap T_{0}}$. Класс ${\displaystyle M\cap T_{0}}$ двойственен к ${\displaystyle M\cap T_{1}}$. Он является предполным в классах ${\displaystyle T_{0}}$ и ${\displaystyle M}$. Обозначение Поста — ${\displaystyle A_{3}}$[6]. Предполных класса 3: ${\displaystyle M\cap T_{0}\cap T_{1}}$ (класс монотонных функций, не равных тождественно константе), ${\displaystyle M\cap T_{0,2}}$ (класс монотонных фукнций, удовлетворяющих условию ${\displaystyle \langle 1^{2}\rangle }$) и ${\displaystyle D\cap T_{0}}$ (класс дизъюнкций с константами)[2]. Примеры базисов: ${\displaystyle \{0,\lor ,\land \}}$, ${\displaystyle \{0,m(x,y,z)\}}$[7]. Минимальное количество функций в базисе — ${\displaystyle 2}$, максимальное — ${\displaystyle 3}$. В классе монотонных функций, не равных тождественно 1, нет шефферовой функции. Порядок класса монотонных функций, не равных тождественно 1, равен ${\displaystyle 2}$[2]. Любой базис класса монотонных функций без 1 имеет функцию, тождественно равную ${\displaystyle 0}$. Монотонные функции без 0 Монотонные функции, не равные тождественно 0, образуют замкнутый класс, равный ${\displaystyle M\cap T_{1}}$. Класс ${\displaystyle M\cap T_{1}}$ двойственен к ${\displaystyle M\cap T_{0}}$. Он является предполным в классах ${\displaystyle T_{1}}$ и ${\displaystyle M}$. Обозначение Поста — ${\displaystyle A_{2}}$[8]. Предполных класса 3: ${\displaystyle M\cap T_{0}\cap T_{1}}$ (класс монотонных функций, не равных тождественно константе), ${\displaystyle M\cap T_{1,2}}$ (класс монотонных функций, удовлетворяющих условию ${\displaystyle \langle 0^{2}\rangle }$) и ${\displaystyle D\cap T_{1}}$ (класс дизъюнкций с константами)[2]. Примеры базисов: ${\displaystyle \{1,\lor ,\land \}}$, ${\displaystyle \{1,m(x,y,z)\}}$[3]. Минимальное количество функций в базисе — ${\displaystyle 2}$, максимальное — ${\displaystyle 3}$. В классе монотонных функций, не равных тождественно 0, нет шефферовой функции. Порядок класса монотонных функций, не равных тождественно 0, равен ${\displaystyle 2}$[2]. Любой базис класса монотонных функций без 0 имеет функцию, тождественно равную ${\displaystyle 1}$. Монотонные функции без констант Монотонные функции, не равные тождественно константе, образуют замкнутый класс, равный ${\displaystyle M\cap T_{0}\cap T_{1}}$. Он является предполным в классах ${\displaystyle T_{0}\cap T_{1}}$, ${\displaystyle M\cap T_{0}}$ и ${\displaystyle M\cap T_{1}}$. Обозначение Поста — ${\displaystyle A_{4}}$[1]. Предполных класса 2: ${\displaystyle T_{0,2}\cap T_{1}\cap M}$ (класс монотонных фукнций, удовлетворяющих условию ${\displaystyle \langle 1^{2}\rangle }$ и сохраняющих 1) и ${\displaystyle T_{1,2}\cap T_{0}\cap M}$ (класс монотонных функций, удовлетворяющих условию ${\displaystyle \langle 0^{2}\rangle }$ и сохраняющих 0)[2]. Примеры базисов: ${\displaystyle \{\lor ,\land \}}$[3], ${\displaystyle \{xy\lor zw\}}$. В ${\displaystyle M\cap T_{0}\cap T_{1}}$ есть шефферовы функции, например ${\displaystyle \{xy\lor zw\}}$. Минимальное количество функций в базисе — ${\displaystyle 1}$, максимальное — ${\displaystyle 2}$. Порядок класса монотонных функций без констант равен ${\displaystyle 2}$[2]. Класс ${\displaystyle M\cap T_{0}\cap T_{1}}$ самодвойственен. Линейные функции, сохраняющие 0 Линейные функции, сохраняющие 0, образуют замкнутый класс ${\displaystyle L\cap T_{0}}$. Обозначение Поста — ${\displaystyle L_{3}}$[9]. Булева функция является линейной, сохраняющей 0, тогда и только тогда, когда её полином Жегалкина линейный без свободного члена. То есть она имеет вид: ${\displaystyle x_{i_{1}}\oplus \ldots \oplus x_{i_{k}}}$ Булева функция является линейной, сохраняющей 0, тогда и только тогда, когда её кополином Жегалкина линейный и имеет нечётное число на равных тождественно ${\displaystyle 1}$ членов. То есть она имеет один из двух видов: ${\displaystyle x_{i_{1}}\leftrightarrow \ldots \leftrightarrow x_{i_{2k-1}}}$ ${\displaystyle x_{i_{1}}\leftrightarrow \ldots \leftrightarrow x_{i_{2k}}\leftrightarrow 0}$ Класс ${\displaystyle L\cap T_{0}}$ является предполным в ${\displaystyle T_{0}}$ и в ${\displaystyle L}$. Предполных класса 2: ${\displaystyle L\cap T_{0}\cap T_{1}}$ и ${\displaystyle U\cap T_{0}}$ (все селекторы и функции, тождественно равные 0)[2]. Примеры базисов: ${\displaystyle \{x\oplus y\}}$, ${\displaystyle \{x\oplus y\oplus z,0\}}$. В ${\displaystyle L\cap T_{0}}$ есть шефферовы функции, например ${\displaystyle \{x\oplus y\}}$. Минимальное количество функций в базисе — ${\displaystyle 1}$, максимальное — ${\displaystyle 2}$. Порядок класса линейных функций, сохраняющих 0, равен ${\displaystyle 2}$. Класс ${\displaystyle L\cap T_{0}}$ двойственен классу ${\displaystyle L\cap T_{1}}$. Линейные функции, сохраняющие 1 Линейные функции, сохраняющие 1, образуют замкнутый класс ${\displaystyle L\cap T_{1}}$. Обозначение Поста — ${\displaystyle L_{2}}$[9]. Булева функция является линейной, сохраняющей 1, тогда и только тогда, когда её кополином Жегалкина линейный без свободного члена. То есть она имеет вид: ${\displaystyle x_{i_{1}}\leftrightarrow \ldots \leftrightarrow x_{i_{k}}}$ Булева функция является линейной, сохраняющей 1, тогда и только тогда, когда её полином Жегалкина линейный и имеет нечётное число ненулевых членов. То есть она имеет один из двух видов: ${\displaystyle x_{i_{1}}\oplus \ldots \oplus x_{i_{2k-1}}}$ ${\displaystyle x_{i_{1}}\oplus \ldots \oplus x_{i_{2k}}\oplus 1}$ Класс ${\displaystyle L\cap T_{1}}$ является предполным в ${\displaystyle T_{1}}$ и в ${\displaystyle L}$. Предполных класса 2: ${\displaystyle L\cap T_{0}\cap T_{1}}$ и ${\displaystyle U\cap T_{1}}$ (все селекторы и функции, тождественно равные 1)[2]. Примеры базисов: ${\displaystyle \{x\leftrightarrow y\}}$, ${\displaystyle \{x\oplus y\oplus z,1\}}$. В ${\displaystyle L\cap T_{1}}$ есть шефферовы функции, например ${\displaystyle \{x\leftrightarrow y\}}$. Минимальное количество функций в базисе — ${\displaystyle 1}$, максимальное — ${\displaystyle 2}$. Порядок класса линейных функций, сохраняющих 1, равен ${\displaystyle 2}$. Класс ${\displaystyle L\cap T_{1}}$ двойственен классу ${\displaystyle L\cap T_{0}}$. Линейные самодвойственные функции Линейные самодвойственные функции образуют замкнутый класс ${\displaystyle L\cap S}$. Обозначение Поста — ${\displaystyle L_{5}}$[10]. Булева функция является линейной самодвойственной тогда и только тогда, когда её полином Жегалкина линейный и в него входит нечётное число переменных. То есть он имеет вид: ${\displaystyle x_{i_{1}}\oplus \ldots \oplus x_{i_{2k-1}}\oplus c}$ Двойственно, функция является линейной самодвойственной тогда и только тогда, когда её кополином Жегалкина линейный и в него входит нечётное число переменных. То есть он имеет вид: ${\displaystyle x_{i_{1}}\leftrightarrow \ldots \leftrightarrow x_{i_{2k-1}}\leftrightarrow c}$ Класс ${\displaystyle L\cap S}$ является предполным в ${\displaystyle S}$ и в ${\displaystyle L}$. Предполных класса 2: ${\displaystyle L\cap T_{0}\cap T_{1}}$ и ${\displaystyle U\cap S}$ (все селекторы и отрицания селекторов)[2]. Примеры базисов: ${\displaystyle \{x\oplus y\oplus z\oplus 1\}}$, ${\displaystyle \{x\oplus y\oplus z,{\overline {x}}\}}$. В ${\displaystyle L\cap S}$ есть шефферовы функции, например ${\displaystyle \{x\oplus y\oplus z\oplus 1\}}$. Минимальное количество функций в базисе — ${\displaystyle 1}$, максимальное — ${\displaystyle 2}$. Порядок класса линейных самодвойственных функций равен ${\displaystyle 3}$. Класс ${\displaystyle L\cap S}$ самодвойственен. Самодвойственные функции, сохраняющие константы Самодвойственные функции, сохраняющие константы, образуют замкнутый класс ${\displaystyle S\cap T_{0}\cap T_{1}=S\cap T_{0}=S\cap T_{1}}$. Обозначение Поста — ${\displaystyle D_{1}}$[11]. Самодвойственная функция сохраняет одну из констант тогда и только тогда, когда она сохраняет другую константу. Количество самодвойственных функций, сохраняющих константы, арности ${\displaystyle n}$ равно ${\displaystyle 2^{2^{n-1}-1}}$. Класс ${\displaystyle S\cap T_{0}\cap T_{1}}$ является предполным в ${\displaystyle S}$ и в ${\displaystyle T_{0}\cap T_{1}}$. Предполных класса 2: ${\displaystyle L\cap T_{0}\cap T_{1}}$ и ${\displaystyle S\cap M}$[2]. Примеры базисов: ${\displaystyle \{xy\lor x{\overline {z}}\lor y{\overline {z}}\}}$[12], ${\displaystyle \{x\oplus y\oplus z,m\}}$. В ${\displaystyle S\cap T_{0}\cap T_{1}}$ есть шефферовы функции, например ${\displaystyle \{xy\lor x{\overline {z}}\lor y{\overline {z}}\}}$. Минимальное количество функций в базисе — ${\displaystyle 1}$, максимальное — ${\displaystyle 2}$. Порядок класса самодвойственных функций, сохраняющих константы, равен ${\displaystyle 3}$. Класс ${\displaystyle L\cap T_{0}\cap T_{1}}$ самодвойственен. Линейные функции, сохраняющие константы Линейные функции, сохраняющие константы, образуют замкнутый класс ${\displaystyle L\cap T_{0}\cap T_{1}=L\cap T_{0}\cap S=L\cap T_{1}\cap S=L\cap T_{0}\cap T_{1}\cap S}$. Обозначение Поста — ${\displaystyle L_{4}}$[11]. Булева функция является линейной, сохраняющей константы, тогда и только тогда, когда её полином Жегалкина линейный без свободного члена и содержит нечётное число ненулевых членов. То есть она имеет вид: ${\displaystyle x_{i_{1}}\oplus \ldots \oplus x_{i_{2k-1}}}$ Двойственно, булева функция является линейной, сохраняющей константы, тогда и только тогда, когда её кополином Жегалкина линейный без свободного члена и содержит нечётное число входящих в него членов. То есть она имеет вид: ${\displaystyle x_{i_{1}}\leftrightarrow \ldots \leftrightarrow x_{i_{2k-1}}}$ Для линейной функции равносильны следующие 3 условия: сохранение констант; сохранение ${\displaystyle 0}$ и самодвойственность; сохранение ${\displaystyle 1}$ и самодвойственность. Класс ${\displaystyle L\cap T_{0}\cap T_{1}}$ является предполным в ${\displaystyle L\cap T_{0}}$, ${\displaystyle L\cap T_{1}}$, ${\displaystyle L\cap S}$ и в ${\displaystyle S\cap T_{0}\cap T_{1}}$. Предполный класс один — класс селекторов ${\displaystyle U\cap T_{0}\cap T_{1}}$[2]. Базис всегда состоит из одной функции, например: ${\displaystyle \{x\oplus y\oplus z\}}$. Любая линейная функция, сохраняющая константы, не являющаяся при этом селектором, образует базис и является шефферовой. Этим исчерпываются все базисы ${\displaystyle L\cap T_{0}\cap T_{1}}$. Порядок класса линейных функций, сохраняющих константы, равен ${\displaystyle 3}$. Класс ${\displaystyle L\cap T_{0}\cap T_{1}}$ самодвойственный. Монотонные самодвойственные функции Монотонные самодвойственные функции образуют замкнутый класс ${\displaystyle M\cap S=M\cap S\cap T_{0}=M\cap S\cap T_{1}=M\cap S\cap T_{0}\cap T_{1}}$. Обозначение Поста — ${\displaystyle D_{3}}$[13]. Любая монотонная самодвойственная функция сохраняет константы. Класс ${\displaystyle M\cap S}$ является предполным в ${\displaystyle L\cap S}$, ${\displaystyle T_{0,2}\cap T_{1}\cap M}$ и в ${\displaystyle T_{1,2}\cap T_{0}\cap M}$. Предполный класс один — класс селекторов ${\displaystyle U\cap T_{0}\cap T_{1}}$[2]. Базис всегда состоит из одной функции, например: ${\displaystyle \{m(x,y,z)\}}$. Любая монотонная самодвойственная функция, не являющаяся при этом селектором, образует базис и является шефферовой. Этим исчерпываются все базисы ${\displaystyle M\cap S}$. Порядок класса монотонных самодвойственных функций равен ${\displaystyle 3}$. Класс ${\displaystyle M\cap S}$ самодвойственный. Селекторы с константами Селекторы с константами образуют замкнутый класс ${\displaystyle M\cap L=U\cap M}$ (${\displaystyle U}$ здесь класс всех несущественных функций). Обозначение Поста — ${\displaystyle R_{11}}$[14][15]; Яблонский, Гаврилов и Кудрявцев используют обозначение ${\displaystyle O_{8}}$. Все функции этого класса имеют один из трёх видов: ${\displaystyle f(x_{1},\ldots ,x_{n})=x_{i}}$; ${\displaystyle f(x_{1},\ldots ,x_{n})=0}$; ${\displaystyle f(x_{1},\ldots ,x_{n})=1}$. Класс ${\displaystyle U\cap M}$ является предполным в ${\displaystyle K}$, ${\displaystyle D}$ и в ${\displaystyle U}$. Предполных класса 3: ${\displaystyle M\cap L\cap T_{0}}$, ${\displaystyle M\cap L\cap T_{1}}$ и класс констант ${\displaystyle C}$[2]. Минимальных клона 2: ${\displaystyle U\cap T_{0}}$ и ${\displaystyle U\cap T_{1}}$. Базис ${\displaystyle U\cap M}$ как замкнутого класса: ${\displaystyle \{x,0,1\}}$[12]; базис ${\displaystyle U\cap M}$ как как клона: ${\displaystyle \{0,1\}}$. В ${\displaystyle U\cap M}$ нет шефферовых функций и как для замкнутого класса, и как для клона. Система функций является базисом в ${\displaystyle U\cap M}$ как замкнутого класса тогда и только тогда, когда она содержит по одной функции из вышеприведённых трёх видов и больше ничего. Система функций является базисом ${\displaystyle U\cap M}$ как клона тогда и только тогда, когда она содержит одну функцию, тождественно равную 0, одну функцию, тождественно равную 1, и больше ничего. Функций в базисе как замкнутого класса всегда ровно 3; функций в базисе как клона всегда ровно 2. Порядок класса селекторов с константами как замкнутого класса равен ${\displaystyle 1}$, а как клона равен ${\displaystyle 0}$. Класс ${\displaystyle U\cap M}$ самодвойственен. Селекторы с 0 Селекторы с 0 образуют замкнутый класс ${\displaystyle M\cap L\cap T_{0}=U\cap T_{0}}$. Обозначение Поста — ${\displaystyle R_{8}}$[14]; Яблонский, Гаврилов и Кудрявцев используют обозначение ${\displaystyle O_{6}}$[16]. Все функции этого класса имеют один из двух видов: ${\displaystyle f(x_{1},\ldots ,x_{n})=x_{i}}$; ${\displaystyle f(x_{1},\ldots ,x_{n})=0}$. Класс ${\displaystyle U\cap T_{0}}$ является предполным в ${\displaystyle K\cap T_{0}}$, ${\displaystyle D\cap T_{0}}$, ${\displaystyle L\cap T_{0}}$ и в ${\displaystyle U\cap M}$. Предполных класса 2: ${\displaystyle U\cap T_{0}\cap T_{1}}$ и класс нулей ${\displaystyle C\cap T_{0}}$[2]. Минимальных клонов 1: ${\displaystyle U\cap T_{0}\cap T_{1}}$. Базис ${\displaystyle U\cap T_{0}}$ как замкнутого класса: ${\displaystyle \{x,0\}}$[12]; базис ${\displaystyle U\cap T_{0}}$ как как клона: ${\displaystyle \{0\}}$. В ${\displaystyle U\cap T_{0}}$ нет шефферовых функций как для замкнутого класса, но есть шефферовы функции как для клона. Система функций является базисом в ${\displaystyle U\cap T_{0}}$ как замкнутого класса тогда и только тогда, когда она содержит по одной функции из вышеприведённых двух видов и больше ничего. Система функций является базисом ${\displaystyle U\cap T_{0}}$ как клона тогда и только тогда, когда она содержит одну функцию, тождественно равную 0, и больше ничего. Функций в базисе как замкнутого класса всегда ровно 2; функций в базисе как клона всегда ровно 1. Порядок класса селекторов с 0 как замкнутого класса равен ${\displaystyle 1}$, а как клона равен ${\displaystyle 0}$. Класс ${\displaystyle U\cap T_{0}}$ двойственен классу ${\displaystyle U\cap T_{1}}$. Селекторы с 1 Селекторы с 1 образуют замкнутый класс ${\displaystyle M\cap L\cap T_{1}=U\cap T_{1}}$. Обозначение Поста — ${\displaystyle R_{6}}$[14]; Яблонский, Гаврилов и Кудрявцев используют обозначение ${\displaystyle O_{5}}$[16]. Все функции этого класса имеют один из двух видов: ${\displaystyle f(x_{1},\ldots ,x_{n})=x_{i}}$; ${\displaystyle f(x_{1},\ldots ,x_{n})=1}$. Класс ${\displaystyle U\cap T_{1}}$ является предполным в ${\displaystyle K\cap T_{1}}$, ${\displaystyle D\cap T_{1}}$, ${\displaystyle L\cap T_{1}}$ и в ${\displaystyle U\cap M}$. Предполных класса 2: ${\displaystyle U\cap T_{0}\cap T_{1}}$ и класс единиц ${\displaystyle C\cap T_{1}}$[2]. Минимальных клонов 1: ${\displaystyle U\cap T_{0}\cap T_{1}}$. Базис ${\displaystyle U\cap T_{1}}$ как замкнутого класса: ${\displaystyle \{x,1\}}$[12]; базис ${\displaystyle U\cap T_{1}}$ как как клона: ${\displaystyle \{1\}}$. В ${\displaystyle U\cap T_{1}}$ нет шефферовых функций как для замкнутого класса, но есть шефферовы функции как для клона. Система функций является базисом в ${\displaystyle U\cap T_{1}}$ как замкнутого класса тогда и только тогда, когда она содержит по одной функции из вышеприведённых двух видов и больше ничего. Система функций является базисом ${\displaystyle U\cap T_{1}}$ как клона тогда и только тогда, когда она содержит одну функцию, тождественно равную 1, и больше ничего. Функций в базисе как замкнутого класса всегда ровно 2; функций в базисе как клона всегда ровно 1. Порядок класса селекторов с 1 как замкнутого класса равен ${\displaystyle 1}$, а как клона равен ${\displaystyle 0}$. Класс ${\displaystyle U\cap T_{1}}$ двойственен классу ${\displaystyle U\cap T_{0}}$. Селекторы Селекторы образуют замкнутый класс ${\displaystyle M\cap L\cap T_{0}\cap T_{1}=M\cap L\cap S=M\cap L\cap S\cap T_{0}=M\cap L\cap S\cap T_{1}=M\cap L\cap S\cap T_{0}\cap T_{1}=U\cap T_{0}\cap T_{1}}$. Обозначение Поста — ${\displaystyle R_{1}}$[14]; Яблонский, Гаврилов и Кудрявцев используют обозначение ${\displaystyle O_{1}}$[16]. Все функции этого класса являются селекторами, то есть имеют следующий вид: ${\displaystyle f(x_{1},\ldots ,x_{n})=x_{i}}$. Класс ${\displaystyle M\cap L\cap T_{1}}$ является предполным в ${\displaystyle K\cap T_{0}\cap T_{1}}$, ${\displaystyle D\cap T_{0}\cap T_{1}}$, ${\displaystyle U\cap T_{0}}$, ${\displaystyle U\cap T_{1}}$ и в ${\displaystyle U\cap S}$. Предполный класс 1: ${\displaystyle \varnothing }$[2]. Минимальных клонов нет вообще. Базис ${\displaystyle U\cap T_{0}\cap T_{1}}$ как замкнутого класса: ${\displaystyle \{x\}}$[12]; базис ${\displaystyle U\cap T_{0}\cap T_{1}}$ как как клона: ${\displaystyle \varnothing }$. В ${\displaystyle U\cap T_{0}\cap T_{1}}$ все функции являются шефферовыми. Система функций является базисом в ${\displaystyle U\cap T_{0}\cap T_{1}}$ как замкнутого класса тогда и только тогда, когда она состоит из одной функции класса ${\displaystyle U\cap T_{0}\cap T_{1}}$. Система функций является базисом ${\displaystyle U\cap T_{0}\cap T_{1}}$ как клона тогда и только тогда, когда она является пустым множеством. Функций в базисе как замкнутого класса всегда ровно 1; функций в базисе как клона всегда ровно 0. Порядок класса селекторов как замкнутого класса равен ${\displaystyle 1}$, а как клона равен ${\displaystyle 0}$. Класс ${\displaystyle U\cap T_{0}\cap T_{1}}$ самодвойственен. Примечания 1 2 3 Пост, 1941, с. 65. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Яблонский, Гаврилов, Кудрявцев, 1966, с. 101. 1 2 3 Шестопал, 1966, с. 1024. Яблонский, Гаврилов, Кудрявцев, 1966, с. 91. Яблонский, Гаврилов, Кудрявцев, 1966, с. 45. Пост, 1941, с. 70. Шестопал, 1966, с. 1026. Пост, 1941, с. 69. 1 2 Пост, 1941, с. 59. Пост, 1941, с. 60. 1 2 Пост, 1941, с. 72. 1 2 3 4 5 Яблонский, Гаврилов, Кудрявцев, 1966, с. 77. Пост, 1941, с. 76. 1 2 3 4 Пост, 1941, с. 49. У Поста ошибка в определении ${\displaystyle R_{10}}$ из-за чего оно такое же, как у ${\displaystyle R_{11}}$, однако на диаграмме на с. 101 видно, что нужный нам класс именно ${\displaystyle R_{11}}$ 1 2 3 Яблонский, Гаврилов, Кудрявцев, 1966, с. 71. Литература Post E. L. The Two-Valued Iterative Systems Of Mathematical Logic. — 1941. Шестопал Г. А. Простые базисы в замкнутых классах функций алгебры логики (рус.) // Докл. АН СССР : доклад. — 1966. — Т. 168, вып. 5. — С. 1023—1026.