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

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

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

Классы конъюнкций и дизъюнкций как с константами, так и без, являются замкнутыми классами. Более того, классы конъюнкций и дизъюнкций только с одной из констант, тоже являются замкнутыми классами. Класс конъюнкций обозначают , класс дизъюнкций — ; в зависимости от автора это обозначение может быть как для классов с константами, так и для классов без. Здесь они будут использованы как обозначения для классов с константами.

Классы конъюнкций и дизъюнкций с константами образуют замкнутый класс . Обозначение Поста — , обозначение Угольникова — , обозначение Лау — . Класс является предполным в классе монотонных функций . Предполных класса 3: класс конъюнкций с нулями , класс конъюнкций с единицами и класс селекторов с константами . Пример базиса: . В базисе всегда ровно 3 функции; шефферовых функций нет. Каждый базис состоит из трёх функций следующего вида: Функция, тождественно равная ; Функция, тождественно равная ; Конъюнкция с хотя бы двумя существенными переменными. Порядок класса конъюнкций с константами равен 2. Класс двойственен классу .

образуют замкнутый класс . Обозначение Поста — , обозначение Угольникова — , обозначение Лау — . Класс является предполным в классе монотонных функций . Предполных класса 3: класс дизъюнкций с единицами , класс дизъюнкций с нулями и класс селекторов с константами . Пример базиса: . В базисе всегда ровно 3 функции; шефферовых функций нет. Каждый базис состоит из трёх функций следующего вида: Функция, тождественно равная ; Функция, тождественно равная ; Дизъюнкция с хотя бы двумя существенными переменными. Порядок класса дизъюнкций с константами равен 2. Класс двойственен классу .

Классы конъюнкций с единицами и дизъюнкций с нулями образуют замкнутый класс . Обозначение Поста — , обозначение Угольникова — , обозначение Лау — . Класс является предполным в классе конъюнкций и в классе монотонных функций, сохраняющих 1 . Предполных класса 2: класс конъюнкций без констант , и класс селекторов с единицами . Пример базиса: . В базисе всегда ровно 2 функции; шефферовых функций нет. Каждый базис состоит из двух функций следующего вида: Функция, тождественно равная ; Конъюнкция с хотя бы двумя существенными переменными. Порядок класса конъюнкций с единицами равен 2. Класс двойственен классу .

образуют замкнутый класс . Обозначение Поста — , обозначение Угольникова — , обозначение Лау — . Класс является предполным в классе конъюнкций и в классе монотонных функций, сохраняющих 0 . Предполных класса 2: класс конъюнкций без констант , и класс селекторов с единицами . Пример базиса: . В базисе всегда ровно 2 функции; шефферовых функций нет. Каждый базис состоит из двух функций следующего вида: Функция, тождественно равная ; Дизъюнкция с хотя бы двумя существенными переменными. Порядок класса дизъюнкций с нулями равен 2. Класс двойственен классу .

Классы конъюнкций с нулями и дизъюнкций с единицами образуют замкнутый класс . Обозначение Поста — , обозначение Яблонского, Гаврилова и Кудрявцева — , обозначение Угольникова — , обозначение Лау — . Класс является предполным в классе конъюнкций и в классе монотонных функций, удовлетворяющих условию ⟨1∞⟩ . Предполных класса 2: класс конъюнкций без констант , и класс селекторов с нулями . Пример базиса: . В базисе всегда ровно 2 функции; шефферовых функций нет. Каждый базис состоит из двух функций следующего вида: Функция, тождественно равная ; Конъюнкция с хотя бы двумя существенными переменными. Порядок класса конъюнкций с нулями равен 2. Класс двойственен классу .

образуют замкнутый класс . Обозначение Поста — , обозначение Яблонского, Гаврилова и Кудрявцева — , обозначение Угольникова — , обозначение Лау — . Класс является предполным в классе дизъюнкций и в классе монотонных функций, удовлетворяющих условию ⟨0∞⟩ . Предполных класса 2: класс дизъюнкций без констант , и класс селекторов с единицами . Пример базиса: . В базисе всегда ровно 2 функции; шефферовых функций нет. Каждый базис состоит из двух функций следующего вида: Функция, тождественно равная ; Дизъюнкция с хотя бы двумя существенными переменными. Порядок класса дизъюнкций с единицами равен 2. Класс двойственен классу .

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

образуют замкнутый класс . Обозначение Поста — (не путать с обозначением класса всех будевых функций ), обозначение Яблонского, Гаврилова и Кудрявцева — , обозначение Угольникова — , обозначение Лау — . Класс является предполным в классе конъюнкций с нулями , конъюнкций с единицами и в классе монотонных функций, сохраняющих константы и удовлетворяющих условию ⟨1∞⟩ . Предполный класс 1: класс селекторов . Пример базиса: . В базисе всегда ровно 1 функция; она является шефферовой. Каждый базис состоит из одной функции следующего вида: Конъюнкция с хотя бы двумя существенными переменными. Порядок класса конъюнкций без констант равен 2. Класс двойственен классу .

образуют замкнутый класс . Обозначение Поста — , обозначение Яблонского, Гаврилова и Кудрявцева — , обозначение Угольникова — , обозначение Лау — . Класс является предполным в классе дизъюнкций с единицами , классе дизъюнкций с нулями и в классе монотонных функций, сохраняющих константы и удовлетворяющих условию ⟨0∞⟩ . Предполный класс 1: класс селекторов . Пример базиса: . В базисе всегда ровно 1 функция; она является шефферовой. Каждый базис состоит из одной функции следующего вида: Дизъюнкция с хотя бы двумя существенными переменными. Порядок класса дизъюнкция без констант равен 2. Класс двойственен классу .

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

Система конъюнкций без фиктивных переменных с нулями — состоит из всех функций вида , где . Обозначение Поста — . Эта система максимальна в системе конъюнкций с нулями, а её максимальные системы — система конъюнкций без фиктивных переменных и констант и система из тождественной функции и нулей. Пример базиса: .

Система дизъюнкций без фиктивных переменных с единицами — состоит из всех функций вида , где . Обозначение Поста — . Эта система максимальна в системе дизъюнкций с единицами, а её максимальные системы — система дизъюнкций без фиктивных переменных и констант и система из тождественной функции и единиц. Пример базиса: .

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

Система конъюнкций без фиктивных переменных и констант — состоит из всех функций вида , где . Обозначение Поста — . Эта система максимальна в системе конъюнкций без констант и в системе конъюнкций без фиктивных переменных с нулями, а её единственная максимальная система — система из тождественной функции. Пример базиса: .

Система дизъюнкций без фиктивных переменных и констант — состоит из всех функций вида , где . Обозначение Поста — . Эта система максимальна в системе дизъюнкций без констант и в системе дизъюнкций без фиктивных переменных с единицами, а её единственная максимальная система — система из тождественной функции. Пример базиса: .

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

Множество максимальных итеративных систем для системы конъюнкций с нулями не совпадает с её множеством предполных классов. Её максимальными итеративными системами являются система конъюнкций без констант, система селекторов с нулями и система конъюнкций без фиктивных переменных с нулями. Пример базиса как итеративной системы — , где определяется как . Двойственно, множество максимальных итеративных систем для системы дизъюнкций с единицами не совпадает с её множеством предполных классов. Её максимальными итеративными системами являются система дизъюнкций без констант, система селекторов с единицами и система дизъюнкций без фиктивных переменных с единицами. Пример базиса как итеративной системы — .

Аналогично происходит и с система конъюнкций и дизъюнкций без констант. Максимальными итеративными системами системы конъюнкций без констант являются система селекторов и система конъюнкций без фиктивных переменных и констант. Пример базиса как итеративной системы — . Двойственно, максимальными итеративными системами системы дизъюнкций без констант являются система селекторов и система дизъюнкций без фиктивных переменных и констант. Пример базиса как итеративной системы — .

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

Примечания

Литература

Категория:Теория дискретных функций