Классы конъюнкций и дизъюнкций

Класс конъюнкций — класс булевых функций вида

${\displaystyle f(x_{1},\ldots ,x_{n})=a_{0}(a_{1}\lor x_{1})\ldots (a_{n}\lor x_{n})}$, ${\displaystyle n\geq 0}$.

Класс дизъюнкций — класс булевых функций вида

${\displaystyle f(x_{1},\ldots ,x_{n})=a_{0}\lor a_{1}x_{1}\lor \ldots \lor a_{n}x_{n}}$, ${\displaystyle n\geq 0}$.

Термины «конъюнкция» и «дизъюнкция» здесь понимаются не в смысле бинарных операций конъюнкции и дизъюнкции, и не в смысле элементарной конъюнкции и элементарной дизъюнкции. В контексте классов конъюнкций и дизъюнкций термины «конъюнкция» и «дизъюнкция» обозначают функции указанных выше видов соответственно. Так, конъюнкция в данном контексте — это функция, представляемая в виде конъюнкции переменных (необязательно всех), а дизъюнкция — функция, представляемая в виде дизъюнкции переменных (необязательно всех). Таким образом, конъюнкции и дизъюнкции могут иметь фиктивные переменные^[1].

В указанном выше определении конъюнкциями и дизъюнкциями считают также константы ${\displaystyle 0}$ и ${\displaystyle 1}$. Некоторые авторы не включают константы в классы конъюнкций и дизъюнкций, и поэтому в определении конъюнкции имеют вид

${\displaystyle f(x_{1},\ldots ,x_{n})=(a_{1}\lor x_{1})\ldots (a_{n},\lor x_{n})}$, ${\displaystyle n\geq 1}$,

а дизъюнкции имеют вид

${\displaystyle f(x_{1},\ldots ,x_{n})=a_{1}x_{1}\lor \ldots \lor a_{n}x_{n}}$, ${\displaystyle n\geq 1}$^[2].

Чтобы не путаться в определениях здесь те классы, которые имеют константы, будут всегда называться «класс конъюнкций с константами» и «класс дизъюнкций с константами», а те, которые не имеют, — «класс конъюнкций без констант» и «класс дизъюнкци без констант».

Классы конъюнкций и дизъюнкций как с константами, так и без, являются замкнутыми классами. Более того, классы конъюнкций и дизъюнкций только с одной из констант, тоже являются замкнутыми классами. Класс конъюнкций обозначают ${\displaystyle K}$, класс дизъюнкций — ${\displaystyle D}$; в зависимости от автора это обозначение может быть как для классов с константами, так и для классов без^[1][2]. Здесь они будут использованы как обозначения для классов с константами.

Конъюнкции с константами образуют замкнутый класс ${\displaystyle K}$. Обозначение Поста — ${\displaystyle P_{6}}$^[3], обозначение Угольникова — ${\displaystyle K}$^[4], обозначение Лау — ${\displaystyle K\cup C}$^[5]. Класс ${\displaystyle K}$ является предполным в классе монотонных функций ${\displaystyle M}$. Предполных класса 3: класс конъюнкций с нулями ${\displaystyle K\cap T_{0}}$, класс конъюнкций с единицами ${\displaystyle K\cap T_{1}}$ и класс селекторов с константами ${\displaystyle U\cap M}$. Пример базиса: ${\displaystyle \{\land ,0,1\}}$. В базисе всегда ровно 3 функции; шефферовых функций нет. Каждый базис состоит из трёх функций следующего вида:

• Функция, тождественно равная ${\displaystyle 0}$;
• Функция, тождественно равная ${\displaystyle 1}$;
• Конъюнкция с хотя бы двумя существенными переменными.

Порядок класса конъюнкций с константами равен 2. Класс ${\displaystyle K}$ двойственен классу ${\displaystyle D}$.

Дизъюнкции с константами образуют замкнутый класс ${\displaystyle D}$. Обозначение Поста — ${\displaystyle S_{6}}$^[6], обозначение Угольникова — ${\displaystyle D}$^[4], обозначение Лау — ${\displaystyle D\cup C}$^[5]. Класс ${\displaystyle D}$ является предполным в классе монотонных функций ${\displaystyle M}$. Предполных класса 3: класс дизъюнкций с единицами ${\displaystyle D\cap T_{1}}$, класс дизъюнкций с нулями ${\displaystyle D\cap T_{0}}$ и класс селекторов с константами ${\displaystyle U\cap M}$. Пример базиса: ${\displaystyle \{\lor ,1,0\}}$. В базисе всегда ровно 3 функции; шефферовых функций нет. Каждый базис состоит из трёх функций следующего вида:

• Функция, тождественно равная ${\displaystyle 1}$;
• Функция, тождественно равная ${\displaystyle 0}$;
• Дизъюнкция с хотя бы двумя существенными переменными.

Порядок класса дизъюнкций с константами равен 2. Класс ${\displaystyle D}$ двойственен классу ${\displaystyle K}$.

Конъюнкции с единицами образуют замкнутый класс ${\displaystyle K\cap T_{1}}$. Обозначение Поста — ${\displaystyle P_{5}}$^[3], обозначение Угольникова — ${\displaystyle K_{1}}$^[7], обозначение Лау — ${\displaystyle K\cup C_{1}}$^[5]. Класс ${\displaystyle K\cap T_{1}}$ является предполным в классе конъюнкций ${\displaystyle K}$ и в классе монотонных функций, сохраняющих 1 ${\displaystyle M\cap T_{1}}$. Предполных класса 2: класс конъюнкций без констант ${\displaystyle K\cap T_{0}\cap T_{1}}$, и класс селекторов с единицами ${\displaystyle U\cap T_{1}}$. Пример базиса: ${\displaystyle \{\land ,1\}}$. В базисе всегда ровно 2 функции; шефферовых функций нет. Каждый базис состоит из двух функций следующего вида:

• Функция, тождественно равная ${\displaystyle 1}$;
• Конъюнкция с хотя бы двумя существенными переменными.

Порядок класса конъюнкций с единицами равен 2. Класс ${\displaystyle K\cap T_{1}}$ двойственен классу ${\displaystyle D\cap T_{0}}$.

Дизъюнкции с нулями образуют замкнутый класс ${\displaystyle D\cap T_{0}}$. Обозначение Поста — ${\displaystyle S_{5}}$^[6], обозначение Угольникова — ${\displaystyle S_{1}}$^[7], обозначение Лау — ${\displaystyle D\cup C_{0}}$^[5]. Класс ${\displaystyle D\cap T_{0}}$ является предполным в классе конъюнкций ${\displaystyle D}$ и в классе монотонных функций, сохраняющих 0 ${\displaystyle M\cap T_{0}}$. Предполных класса 2: класс конъюнкций без констант ${\displaystyle D\cap T_{0}\cap T_{1}}$, и класс селекторов с единицами ${\displaystyle U\cap T_{0}}$. Пример базиса: ${\displaystyle \{\lor ,0\}}$. В базисе всегда ровно 2 функции; шефферовых функций нет. Каждый базис состоит из двух функций следующего вида:

• Функция, тождественно равная ${\displaystyle 0}$;
• Дизъюнкция с хотя бы двумя существенными переменными.

Порядок класса дизъюнкций с нулями равен 2. Класс ${\displaystyle D\cap T_{0}}$ двойственен классу ${\displaystyle K\cap T_{1}}$.

Конъюнкции с нулями образуют замкнутый класс ${\displaystyle K\cap T_{0}}$. Обозначение Поста — ${\displaystyle P_{4}}$^[3], обозначение Яблонского, Гаврилова и Кудрявцева — ${\displaystyle P_{3}}$^[8], обозначение Угольникова — ${\displaystyle K_{0}}$^[7], обозначение Лау — ${\displaystyle K\cup C_{0}}$^[5]. Класс ${\displaystyle K\cap T_{0}}$ является предполным в классе конъюнкций ${\displaystyle K}$ и в классе монотонных функций, удовлетворяющих условию ⟨1^∞⟩ ${\displaystyle T_{0,\infty }\cap M}$. Предполных класса 2: класс конъюнкций без констант ${\displaystyle K\cap T_{0}\cap T_{1}}$, и класс селекторов с нулями ${\displaystyle U\cap T_{0}}$. Пример базиса: ${\displaystyle \{\land ,0\}}$. В базисе всегда ровно 2 функции; шефферовых функций нет. Каждый базис состоит из двух функций следующего вида:

• Функция, тождественно равная ${\displaystyle 0}$;
• Конъюнкция с хотя бы двумя существенными переменными.

Порядок класса конъюнкций с нулями равен 2. Класс ${\displaystyle K\cap T_{0}}$ двойственен классу ${\displaystyle D\cap T_{1}}$.

Дизъюнкции с единицами образуют замкнутый класс ${\displaystyle D\cap T_{1}}$. Обозначение Поста — ${\displaystyle S_{4}}$^[6], обозначение Яблонского, Гаврилова и Кудрявцева — ${\displaystyle S_{3}}$^[9], обозначение Угольникова — ${\displaystyle D_{0}}$^[7], обозначение Лау — ${\displaystyle D\cup C_{1}}$^[5]. Класс ${\displaystyle D\cap T_{1}}$ является предполным в классе дизъюнкций ${\displaystyle D}$ и в классе монотонных функций, удовлетворяющих условию ⟨0^∞⟩ ${\displaystyle T_{1,\infty }\cap M}$. Предполных класса 2: класс дизъюнкций без констант ${\displaystyle D\cap T_{0}\cap T_{1}}$, и класс селекторов с единицами ${\displaystyle U\cap T_{1}}$. Пример базиса: ${\displaystyle \{\lor ,1\}}$. В базисе всегда ровно 2 функции; шефферовых функций нет. Каждый базис состоит из двух функций следующего вида:

• Функция, тождественно равная ${\displaystyle 1}$;
• Дизъюнкция с хотя бы двумя существенными переменными.

Порядок класса дизъюнкций с единицами равен 2. Класс ${\displaystyle D\cap T_{1}}$ двойственен классу ${\displaystyle K\cap T_{0}}$.

Конъюнкции без констант образуют замкнутый класс ${\displaystyle K\cap T_{0}\cap T_{1}}$. Обозначение Поста — ${\displaystyle P_{2}}$^[3] (не путать с обозначением класса всех будевых функций ${\displaystyle P_{2}}$), обозначение Яблонского, Гаврилова и Кудрявцева — ${\displaystyle P_{1}}$^[8], обозначение Угольникова — ${\displaystyle K_{01}}$^[10], обозначение Лау — ${\displaystyle K}$^[5]. Класс ${\displaystyle K\cap T_{0}\cap T_{1}}$ является предполным в классе конъюнкций с нулями ${\displaystyle K\cap T_{0}}$, конъюнкций с единицами ${\displaystyle K\cap T_{1}}$ и в классе монотонных функций, сохраняющих константы и удовлетворяющих условию ⟨1^∞⟩ ${\displaystyle T_{0,\infty }\cap M\cap T_{1}}$. Предполный класс 1: класс селекторов ${\displaystyle U\cap T_{0}\cap T_{1}}$. Пример базиса: ${\displaystyle \{\land \}}$. В базисе всегда ровно 1 функция; она является шефферовой. Каждый базис состоит из одной функции следующего вида:

• Конъюнкция с хотя бы двумя существенными переменными.

Порядок класса конъюнкций без констант равен 2. Класс ${\displaystyle K\cap T_{0}\cap T_{1}}$ двойственен классу ${\displaystyle D\cap T_{0}\cap T_{1}}$.

Дизъюнкции без констант образуют замкнутый класс ${\displaystyle D\cap T_{0}\cap T_{1}}$. Обозначение Поста — ${\displaystyle S_{2}}$^[6], обозначение Яблонского, Гаврилова и Кудрявцева — ${\displaystyle S_{1}}$^[9], обозначение Угольникова — ${\displaystyle D_{01}}$^[10], обозначение Лау — ${\displaystyle D}$^[5]. Класс ${\displaystyle D\cap T_{0}\cap T_{1}}$ является предполным в классе дизъюнкций с единицами ${\displaystyle D\cap T_{1}}$, классе дизъюнкций с нулями ${\displaystyle D\cap T_{0}}$ и в классе монотонных функций, сохраняющих константы и удовлетворяющих условию ⟨0^∞⟩ ${\displaystyle T_{1,\infty }\cap M\cap T_{0}}$. Предполный класс 1: класс селекторов ${\displaystyle U\cap T_{0}\cap T_{1}}$. Пример базиса: ${\displaystyle \{\lor \}}$. В базисе всегда ровно 1 функция; она является шефферовой. Каждый базис состоит из одной функции следующего вида:

• Дизъюнкция с хотя бы двумя существенными переменными.

Порядок класса дизъюнкция без констант равен 2. Класс ${\displaystyle D\cap T_{0}\cap T_{1}}$ двойственен классу ${\displaystyle K\cap T_{0}\cap T_{1}}$.

Эмиль Пост рассматривал более слабое замыкание множеств булевых функций. В этом замыкании отсутствует требование замкнутости относительно удаления и добавления фиктивных переменных, а также запрещены нульарные функциию Замкнутые относительно него множества он называл итеративными системами. Для них несколько отличаются базисы, множества максимальных систем (аналог предполных классов) и появляется 4 новых системы, похожих на классы конъюнкций и дизъюнкций. Основная причина их появления в том, что не имея возможность добавлять фиктивные переменные невозможно получить из конъюнкции (дизъюнкции), не имеющих фиктивных переменных и имеющих хотя бы одну существенную переменную, конъюнкцию (дизъюнкцию), имеющую хотя бы одну фиктивную переменную.

Система конъюнкций без фиктивных переменных с нулями — состоит из всех функций вида

${\displaystyle f(x_{1},\ldots ,x_{n})=ax_{1}\ldots x_{n}}$, где ${\displaystyle n\geq 1}$.

Обозначение Поста — ${\displaystyle P_{3}}$^[3]. Эта система максимальна в системе конъюнкций с нулями, а её максимальные системы — система конъюнкций без фиктивных переменных и констант и система из тождественной функции и нулей. Пример базиса: ${\displaystyle \{\land ,0\}}$.

Система дизъюнкций без фиктивных переменных с единицами — состоит из всех функций вида

${\displaystyle f(x_{1},\ldots ,x_{n})=a\lor x_{1}\lor \ldots \lor x_{n}}$, где ${\displaystyle n\geq 1}$.

Обозначение Поста — ${\displaystyle S_{3}}$^[6]. Эта система максимальна в системе дизъюнкций с единицами, а её максимальные системы — система дизъюнкций без фиктивных переменных и констант и система из тождественной функции и единиц. Пример базиса: ${\displaystyle \{\lor ,1\}}$.

Система конъюнкций без фиктивных переменных с нулями и система дизъюнкций без фиктивных переменных с единицами двойственны друг другу.

Система конъюнкций без фиктивных переменных и констант — состоит из всех функций вида

${\displaystyle f(x_{1},\ldots ,x_{n})=x_{1}\ldots x_{n}}$, где ${\displaystyle n\geq 1}$.

Обозначение Поста — ${\displaystyle P_{1}}$^[3]. Эта система максимальна в системе конъюнкций без констант и в системе конъюнкций без фиктивных переменных с нулями, а её единственная максимальная система — система из тождественной функции. Пример базиса: ${\displaystyle \{\land \}}$.

Система дизъюнкций без фиктивных переменных и констант — состоит из всех функций вида

${\displaystyle f(x_{1},\ldots ,x_{n})=x_{1}\lor \ldots \lor x_{n}}$, где ${\displaystyle n\geq 1}$.

Обозначение Поста — ${\displaystyle S_{1}}$^[6]. Эта система максимальна в системе дизъюнкций без констант и в системе дизъюнкций без фиктивных переменных с единицами, а её единственная максимальная система — система из тождественной функции. Пример базиса: ${\displaystyle \{\lor \}}$.

Система конъюнкций без фиктивных переменных и констант и система дизъюнкций без фиктивных переменных и констант двойственны друг другу.

Множество максимальных итеративных систем для системы конъюнкций с нулями не совпадает с её множеством предполных классов. Её максимальными итеративными системами являются система конъюнкций без констант, система селекторов с нулями и система конъюнкций без фиктивных переменных с нулями. Пример базиса как итеративной системы — ${\displaystyle \{\land ,0,e_{1}^{2}\}}$, где ${\displaystyle e_{1}^{2}}$ определяется как ${\displaystyle e_{1}^{2}(x_{1},x_{2})=x_{1}}$. Двойственно, множество максимальных итеративных систем для системы дизъюнкций с единицами не совпадает с её множеством предполных классов. Её максимальными итеративными системами являются система дизъюнкций без констант, система селекторов с единицами и система дизъюнкций без фиктивных переменных с единицами. Пример базиса как итеративной системы — ${\displaystyle \{\lor ,1,e_{1}^{2}\}}$.

Аналогично происходит и с система конъюнкций и дизъюнкций без констант. Максимальными итеративными системами системы конъюнкций без констант являются система селекторов и система конъюнкций без фиктивных переменных и констант. Пример базиса как итеративной системы — ${\displaystyle \{\land ,e_{1}^{2}\}}$. Двойственно, максимальными итеративными системами системы дизъюнкций без констант являются система селекторов и система дизъюнкций без фиктивных переменных и констант. Пример базиса как итеративной системы — ${\displaystyle \{\lor ,e_{1}^{2}\}}$.

Множество всех систем, в которых каждый из рассмотренных в статье замкнутых классов является максимальной итеративной системой, совпадает с множеством всех замкнутых классов, в которых данных класс предполон. Для нерассмотренных в этом разделе, но рассмотренных в статье замкнутых классов, множество максимальных итеративных систем и примеры базисов как итеративных систем совпадают с указанными выше множеством предполных классов и примерами базисов как замкнутого класса.

• Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2000.
• Угольников, А. Б. О замкнутых классах Поста (рус.) // Изв. вузов. Матем. : журнал. — М.: Soviet Math. (Iz. VUZ), 1988. — 16 февраля (т. 32, вып. 7). — С. 79-88.
• Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста (рус.) / под ред. В. В. Донченко. — М.: Наука, 1966. — 120 с. — 10 000 экз.
• Lau, D. Function Algebras on Finite Sets: A Basic Course on Many-Valued Logic and Clone Theory (англ.). — Springer, 2006. — 668 p.
• Post E. L. The Two-Valued Iterative Systems Of Mathematical Logic. — 1941.