Пересечения предполных классов булевой логики являются замкнутыми классами в . Пересечениями предполных классов не исчерпываются все замкнутые классы в , так как пересечений конечное число, а всего замкнутых классов счётное число.
Функции, сохраняющие константы Функция, сохраняющая константы, — функция , для которой выполняются два условия: ; . Примеры: тождественная функция , конъюнкция , дизъюнкция , функция голосования , . Для количество -арных функций, сохраняющих константы, равно . Нульарных функций, сохраняющих константы, нет.
Класс функций, сохраняющих константы, является замкнутым и равен (обозначение Поста — ). Он является предполным в и . В 4 предполных класса: , , , . Примеры базисов: , , . Порядок равен . В есть шефферовы функции, например . Минимальное количество функций в базисе — , максимальное — .
Функция сохраняет константы тогда и только тогда, когда она является -функцией (то есть отождествление переменных ). Поэтому, класс можно определить как множество всех -функций. Именно так он определялся в некоторой старой литературе, включая монографию Поста. Класс самодвойственен.
Монотонные функции без 1 Монотонные функции, не равные тождественно 1, образуют замкнутый класс, равный . Класс двойственен к . Он является предполным в классах и . Обозначение Поста — . Предполных класса 3: (класс монотонных функций, не равных тождественно константе), (класс монотонных функций, удовлетворяющих условию ⟨12⟩) и (класс конъюнкций с нулями). Примеры базисов: , . Минимальное количество функций в базисе — , максимальное — . В классе монотонных функций, не равных тождественно 1, нет шефферовой функции. Порядок класса монотонных функций, не равных тождественно 1, равен . Любой базис класса монотонных функций без 1 имеет функцию, тождественно равную .
Монотонные функции без 0 Монотонные функции, не равные тождественно 0, образуют замкнутый класс, равный . Класс двойственен к . Он является предполным в классах и . Обозначение Поста — . Предполных класса 3: (класс монотонных функций, не равных тождественно константе), (класс монотонных функций, удовлетворяющих условию ⟨02⟩) и (класс дизъюнкций с единицами). Примеры базисов: , . Минимальное количество функций в базисе — , максимальное — . В классе монотонных функций, не равных тождественно 0, нет шефферовой функции. Порядок класса монотонных функций, не равных тождественно 0, равен . Любой базис класса монотонных функций без 0 имеет функцию, тождественно равную .
Монотонные функции без констант Монотонные функции, не равные тождественно константе, образуют замкнутый класс, равный . Он является предполным в классах , и . Обозначение Поста — . Предполных класса 2: (класс монотонных функций, сохраняющих константы и удовлетворяющих условию ⟨12⟩) и (класс монотонных функций, сохраняющих константы и удовлетворяющих условию ⟨02⟩). Примеры базисов: , . В есть шефферовы функции, например . Минимальное количество функций в базисе — , максимальное — . Порядок класса монотонных функций без констант равен . Класс самодвойственен.
Линейные функции, сохраняющие 0 Линейные функции, сохраняющие 0, образуют замкнутый класс . Обозначение Поста — . Булева функция является линейной, сохраняющей 0, тогда и только тогда, когда её полином Жегалкина линейный без свободного члена. То есть она имеет вид:
Булева функция является линейной, сохраняющей 0, тогда и только тогда, когда её кополином Жегалкина линейный и имеет нечётное число на равных тождественно членов. То есть она имеет один из двух видов:
Класс является предполным в и в . Предполных класса 2: и (все селекторы и функции, тождественно равные 0). Примеры базисов: , . В есть шефферовы функции, например . Минимальное количество функций в базисе — , максимальное — . Порядок класса линейных функций, сохраняющих 0, равен . Класс двойственен классу .
Линейные функции, сохраняющие 1 Линейные функции, сохраняющие 1, образуют замкнутый класс . Обозначение Поста — . Булева функция является линейной, сохраняющей 1, тогда и только тогда, когда её кополином Жегалкина линейный без свободного члена. То есть она имеет вид:
Булева функция является линейной, сохраняющей 1, тогда и только тогда, когда её полином Жегалкина линейный и имеет нечётное число ненулевых членов. То есть она имеет один из двух видов:
Класс является предполным в и в . Предполных класса 2: и (все селекторы и функции, тождественно равные 1). Примеры базисов: , . В есть шефферовы функции, например . Минимальное количество функций в базисе — , максимальное — . Порядок класса линейных функций, сохраняющих 1, равен . Класс двойственен классу .
Линейные самодвойственные функции Линейные самодвойственные функции образуют замкнутый класс . Обозначение Поста — . Булева функция является линейной самодвойственной тогда и только тогда, когда её полином Жегалкина линейный и в него входит нечётное число переменных. То есть он имеет вид:
Двойственно, функция является линейной самодвойственной тогда и только тогда, когда её кополином Жегалкина линейный и в него входит нечётное число переменных. То есть он имеет вид:
Класс является предполным в и в . Предполных класса 2: и (все селекторы и отрицания селекторов). Примеры базисов: , . В есть шефферовы функции, например . Минимальное количество функций в базисе — , максимальное — . Порядок класса линейных самодвойственных функций равен . Класс самодвойственен.
Самодвойственные функции, сохраняющие константы Самодвойственные функции, сохраняющие константы, образуют замкнутый класс . Обозначение Поста — . Самодвойственная функция сохраняет одну из констант тогда и только тогда, когда она сохраняет другую константу. Количество самодвойственных функций, сохраняющих константы, арности равно .
Класс является предполным в и в . Предполных класса 2: и . Примеры базисов: , . В есть шефферовы функции, например . Минимальное количество функций в базисе — , максимальное — . Порядок класса самодвойственных функций, сохраняющих константы, равен . Класс самодвойственен.
Линейные функции, сохраняющие константы Линейные функции, сохраняющие константы, образуют замкнутый класс . Обозначение Поста — . Булева функция является линейной, сохраняющей константы, тогда и только тогда, когда её полином Жегалкина линейный без свободного члена и содержит нечётное число ненулевых членов. То есть она имеет вид:
Двойственно, булева функция является линейной, сохраняющей константы, тогда и только тогда, когда её кополином Жегалкина линейный без свободного члена и содержит нечётное число входящих в него членов. То есть она имеет вид:
Для линейной функции равносильны следующие 3 условия: сохранение констант; сохранение и самодвойственность; сохранение и самодвойственность. Класс является предполным в , , и в . Предполный класс один — класс селекторов . Базис всегда состоит из одной функции, например: . Любая линейная функция, сохраняющая константы, не являющаяся при этом селектором, образует базис и является шефферовой. Этим исчерпываются все базисы . Порядок класса линейных функций, сохраняющих константы, равен . Класс самодвойственный.
Монотонные самодвойственные функции Монотонные самодвойственные функции образуют замкнутый класс . Обозначение Поста — . Любая монотонная самодвойственная функция сохраняет константы.
Класс является предполным в , и в . Предполный класс один — класс селекторов . Базис всегда состоит из одной функции, например: . Любая монотонная самодвойственная функция, не являющаяся при этом селектором, образует базис и является шефферовой. Этим исчерпываются все базисы . Порядок класса монотонных самодвойственных функций равен . Класс самодвойственный.
Селекторы с константами Селекторы с константами образуют замкнутый класс ( здесь класс всех несущественных функций). Обозначение Поста — У Поста ошибка в определении из-за чего оно такое же, как у , однако на диаграмме на с. 101 видно, что нужный нам класс именно ; Яблонский, Гаврилов и Кудрявцев используют обозначение . Все функции этого класса имеют один из трёх видов:
. Класс является предполным в , и в . Предполных класса 3: , и класс констант . Минимальных клона 2: и . Базис как замкнутого класса: ; базис как клона: . В нет шефферовых функций и как для замкнутого класса, и как для клона.
Система функций является базисом в как замкнутого класса тогда и только тогда, когда она содержит по одной функции из вышеприведённых трёх видов и больше ничего. Система функций является базисом как клона тогда и только тогда, когда она содержит одну функцию, тождественно равную 0, одну функцию, тождественно равную 1, и больше ничего. Функций в базисе как замкнутого класса всегда ровно 3; функций в базисе как клона всегда ровно 2. Порядок класса селекторов с константами как замкнутого класса равен , а как клона равен . Класс самодвойственен.
Селекторы с 0 Селекторы с 0 образуют замкнутый класс . Обозначение Поста — ; Яблонский, Гаврилов и Кудрявцев используют обозначение . Все функции этого класса имеют один из двух видов: ; . Класс является предполным в , , и в . Предполных класса 2: и класс нулей . Минимальных клонов 1: . Базис как замкнутого класса: ; базис как клона: . В нет шефферовых функций как для замкнутого класса, но есть шефферовы функции как для клона.
Система функций является базисом в как замкнутого класса тогда и только тогда, когда она содержит по одной функции из вышеприведённых двух видов и больше ничего. Система функций является базисом как клона тогда и только тогда, когда она содержит одну функцию, тождественно равную 0, и больше ничего. Функций в базисе как замкнутого класса всегда ровно 2; функций в базисе как клона всегда ровно 1. Порядок класса селекторов с 0 как замкнутого класса равен , а как клона равен . Класс двойственен классу .
Селекторы с 1 Селекторы с 1 образуют замкнутый класс . Обозначение Поста — ; Яблонский, Гаврилов и Кудрявцев используют обозначение . Все функции этого класса имеют один из двух видов: ; . Класс является предполным в , , и в . Предполных класса 2: и класс единиц . Минимальных клонов 1: . Базис как замкнутого класса: ; базис как клона: . В нет шефферовых функций как для замкнутого класса, но есть шефферовы функции как для клона.
Система функций является базисом в как замкнутого класса тогда и только тогда, когда она содержит по одной функции из вышеприведённых двух видов и больше ничего. Система функций является базисом как клона тогда и только тогда, когда она содержит одну функцию, тождественно равную 1, и больше ничего. Функций в базисе как замкнутого класса всегда ровно 2; функций в базисе как клона всегда ровно 1. Порядок класса селекторов с 1 как замкнутого класса равен , а как клона равен . Класс двойственен классу .
Селекторы Селекторы образуют замкнутый класс . Обозначение Поста — ; Яблонский, Гаврилов и Кудрявцев используют обозначение . Все функции этого класса являются селекторами, то есть имеют следующий вид: . Класс является предполным в , , , и в . Предполный класс 1: . Минимальных клонов нет вообще. Базис как замкнутого класса: ; базис как как клона: . В все функции являются шефферовыми.
Система функций является базисом в как замкнутого класса тогда и только тогда, когда она состоит из одной функции класса . Система функций является базисом как клона тогда и только тогда, когда она является пустым множеством. Функций в базисе как замкнутого класса всегда ровно 1; функций в базисе как клона всегда ровно 0. Порядок класса селекторов как замкнутого класса равен , а как клона равен . Класс самодвойственен.
Примечания
Литература
Категория:Теория дискретных функций