Замкнутый класс в теории булевых функций — такое множество функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: . Другими словами, любая функция, которую можно выразить формулой с использованием функций множества , снова входит в это же множество.
В 1941 году Эмиль Пост представил полное описание всех замкнутых классов булевых функций. Множество всех замкнутых классов, упорядоченное отношением включения, образует решётку, называемую решёткой Поста.
Определение Через элементарные операции Говорят, что функция получена при помощи операции суперпозиции функций из множества , если функция может быть получена из функций множества за конечное число шагов при помощью следующих операций: Перестановка и отождествление переменных; Подстановка функций и переменных в качестве аргументов другой функции; Добавление и удаление фиктивных переменных. Если множество функций замкнуто относительно указанных операций, то оно называется замкнутым классом. В данном определении разрешается функциям иметь ноль аргументов, то есть быть нульарными.
В англоязычной литературе и некоторой русскоязычной зачастую используют другое определение, неэквивалентное данному. Замкнутому классу запрещают иметь нульарные функции и убирается требование замкнутости относительно операции удаления переменных. Замкнутые классы в этом определении идентичны замкнутым классам в первом, с точностью до нульарных функций. Через формулы Пусть дано множество функций положительной арности и множество , , называемое множеством переменных. Булевой формулой глубины 0 над множеством функций и множеством переменных называется однобуквенное слово из одного символа . Булевой формулой глубины , где , называется слово вида , где ― функция, имеющая арность , а ― булевы формулы, глубины меньше . Говорят, что функция задаётся булевой формулой относительно набора переменных (все в этом наборе отличаются и каждая переменная формулы входит в этот набор), если равняется значению этой формулы, после подстановки вместо каждого значения . Тогда говорят, что функция получена при помощи операции суперпозиции функций из множества , если функция может быть задана булевой формулой положительной глубины над множеством функций .
Данное определение эквивалентно второму определению выше (то есть тому, где запрещаются функции нулевой арности). Определение через формулы можно видоизменить для того, чтобы оно соответствовала первому определению (тому, где разрешается удаление фиктивных переменных). Для этого множеству разрешается иметь нульарные функции и вводится понятие фиктивной переменной формулы. Переменная называется фиктивной переменной булевой формулы , если любое изменение значения данной переменной при сохранении значений остальных переменных не меняет значения формулы; в противном случае переменная называется существенной. Тогда при определении того, что функция задаётся формулой относительно набора переменных на этот набор накладывается менее строгое ограничение: требуется не чтобы любая переменная формула обязательно входила в этот набор, а достаточно чтобы любая существенная переменная входила в него, а фиктивные могут и не входить. Формулировка определения того, что функция получена при помощи операции суперпозиции, остаётся без изменений. Такое определение будет эквивалентно определению через элементарные операции с удалением фиктивных переменных.
Примеры замкнутых классов Простейшими замкнутыми классами являются класс всех булевых функций и пустое множество . Некоторые авторы не считают пустое множество замкнутым классом; в таком случае множество всех замкнутых классов булевых функций с отношением включения не образует решётку.
Особо известными замкнутыми классами булевых функций являются следующие 5 классов, известные как классы Поста: Класс функций, сохраняющих константу 0:. Класс функций, сохраняющих константу 1:. Класс самодвойственных функций:. Класс монотонных булевых функций:. Класс линейных булевых функций:. Эти классы так известны, поскольку участвуют в формулировке критерия Поста. Любой замкнутый класс булевых функций, отличный от класса всех функций, вкладывается в хотя бы один из этих пяти классов.
Другими важными замкнутыми классами являются: Класс конъюнкций с константами , представляющий собой множество функций вида . Класс дизъюнкций с константами , представляющий собой множество функций вида . Класс несущественных функций , содержащий только константы, отрицания одного из своих аргументов и селекторы (функции, равные одному из своих аргументов на всех наборах их значений). Класс констант , содержащий только константы. Класс функций (m — любое натуральное, большее единицы число), удовлетворяющих условию : для любых m наборов, на которых функция принимает нулевое значение, найдется переменная, также принимающая нулевое значение на всех этих наборах. Класс функций, для которых выполнено условие : , где — одна из переменных функции. Класс функций (m — любое натуральное, большее единицы число), удовлетворяющих условию : для любых m наборов, на которых функция принимает единичное значение, найдется переменная, также принимающая единичное значение на всех этих наборах. Класс функций, для которых выполнено условие : , где — одна из переменных функции.
Любой замкнутый класс булевых функций является пересечением конечного числа классов , где .
Свойства Пересечение любого числа замкнутых классов снова является замкнутым классом (если пустое множество считать замкнутым классом). Объединение замкнутых классов может замкнутым классом не являться (например объединение класса нулей и класса селекторов с отрицаниями не является замкнутым классом, поскольку отрицание нуля даст единицу). Замкнутый класс булевых функций, содержащий не только константы, обязательно содержит все селекторы. Дополнение замкнутого класса булевых функций до множества всех булевых функций может замкнутым классом не являться (если пустое множество не считать замкнутым классом, то дополнение не является замкнутым классом никогда).
Замыкание Замыканием (относительно суперпозиции) системы функций называется множество всех функций, которые могут быть получены из функций множества при помощи суперпозиции. Замыкание системы функций обозначается .. Замыкание любой системы функций является замкнутым классом. Система функций является замкнутым классом тогда и только тогда, когда . Класс является наименьшим по включению замкнутым классом, включающим . Класс можно получить как пересечение всех замкнутых классов, содержащих .
Замыкание относительно суперпозиции является частым случаем теоретико-множественного замыкания, то есть для него выполнены следующие свойства: Любое множество является подмножеством своего замыкания: . Замыкание подмножества является подмножеством замыкания: .Следует заметить, что из строгого вложения множеств следует лишь нестрогое вложение их замыканий: Многократное применение операции замыкания эквивалентно однократному: . Замыкание относительно суперпозиции также удовлетворяет свойству финитарности, то есть является алгебраическим: , где — множество всех конечных подможеств .
Полные системы функций Система функций называется полной системой в замкнутом классе , если любую функцию класса можно получить при помощи суперпозиции функций множества . Эквивалентное определение: система полна в , если . Полную систему также называют порождающей системой и говорят, что она порождает класс . Примеры полных систем: В любом замкнутом классе сам класс является полной системой. Система является полной системой в классе всех булевых функций, так как любую функцию можно задать при помощи СДНФ, а . Система является полной системой в классе линейных функций, так как любую линейную функцию можно задать при помощи полинома Жегалкина без конъюнкций, а . Система является полной системой в классе монотонных функций, так как любую монотонную функцию можно задать при помощи сокДНФ без отрицаний. Функция, которая сама по себе образует полную систему в замкнутом классе , называется шефферовой функцией в классе . Штрих Шеффера и Стрелка Пирса являются шефферовыми функциями в классе всех булевых функций. Отрицание функции голосования является шефферовой функцией в классе самодвойственных функций. В классах монотонных функций и линейных функций шефферовых функций нет. Базис Полная система функций в замкнутом классе называется базисом в замкнутом классе , если никакая собственная подсистема не является полной в . Таким образом базис — это минимальная по включению полная система класса.
Приведённая выше система , полная в классе всех булевых функций, не является базисом, поскольку можно выразить через при помощи законов де-Моргана. Базисами в классе всех булевых функций являются системы и .
Система является базисом в классе линейных функций. Система является базисом в классе монотонных функций.
У любого замкнутого класса булевых функций есть конечный базис. Все базисы всех замкнутых классов имеют не более четырёх функций.
Порядок Идейно, порядок замкнутого класса есть минимальная арность функций базиса. Существует несколько определений порядка.
В одном из определений сначала определяется порядок функции как количество её существенных переменных. Порядок базиса определяется как максимальный из порядков входящих в него функций. Порядок замкнутого класса определяется как минимальный из порядков его базисов.
В другом определении порядок замкнутого класса определяется как минимальное число такое, что множество всех функций арности этого класса порождает весь этот класс.
Если рассматривается суперпозиция с удалениями фиктивных переменных, то оба определения эквивалентны. Если же замкнутому классу разрешается иметь только функции положительной арности, то все классы, имеющие порядок 0 в первом определении, имеют порядок 1 во втором; других отличий нет.
Первое определение используется в терминологии, в которой отождествляются функции, отличающиеся лишь фиктивными переменными. В такой терминологии не имеет смысла рассматривать общее количество аргументов, поэтому в качестве порядка функций рассматривается количество существенных переменных.
Критериальные системы Система замкнутых подклассов класса называется критериальной в замкнутом классе , если каждый собственный подкласс вкладывается в некоторый класс из . Простейший пример критериальной системы для произвольного класса — множество всех собственных подклассов . Критерий Поста устанавливает, что система классов является критериальной для класса всех булевых функций. Критериальная система класса называется минимальной, если никакая её собственная подсистема не является критериальной в .
Замкнутый класс называется предполным в замкнутом классе , если для любой функции система является полной в . У каждого замкнутого класса булевых функций конечное количество предполных классов, причём оно не больше 5. Для каждого замкнутого класса его собственный замкнутый подкласс можно дополнить до некоторого предполного в .
Минимальная критериальная система замкнутого класса булевых функций есть множество всех его предполных классов. Это позволяет сформулировать для каждого из замкнутых классов простой критерий полноты, состоящий в том, что система функций полна в этом классе тогда и только тогда, когда она полностью не лежит ни в одном из его предполных классов. Частный случай этого критерия для класса всех булевых функций называется критерием Поста или малой теорема Поста. Примеры минимальных критериальных систем: Для класса всех булевых функций минимальная критериальная система есть . Для класса всех линейных функций минимальная критериальная система есть . Для класса всех самодвойственных функций минимальная критериальная система есть .
Список замкнутых классов В 1941 году Эмиль Пост привёл полное описание структуры замкнутых классов двузначной логики. Также Пост установил, что любой замкнутый класс может быть порожден конечным базисом.