Принцип двойственности

Пусть – некоторое подмножество множества булевых функций: .

Определение 1: Множество называется замыканием множества , если оно содержит все суперпозиции функций множества и не содержит никаких других функций.

Например, если , тогда, очевидно, .

Отметим очевидные свойства замыкания:

1) ;

2) ;

3) если , то .

Определение 2: Множество называется замкнутым классом, если выполняется условие: .

Например, пусть . Как следует из предыдущего примера, и поэтому не является замкнутым классом.

Если , то класс является замыканием класса . В силу свойства 2 операции замыкания является замкнутым классом.

Очевидно, что пересечение любого числа замкнутых классов есть замкнутый класс.

Легко заметить, что если функции содержатся в то для выяснения того, является ли замкнутым классом, достаточно ограничиться проверкой выполнения следующего условия: если функции ,..., , где , принадлежат множеству , то функция также принадлежит множеству .

Определение 3: Система функций из замкнутого класса называется полной в , если .

В случае если система полна в , то всякая функция из множества является суперпозицией функции из .

Для каждого замкнутого класса с конечным базисом введем понятие порядка замкнутого класса.

Пусть – конечный базис в . Обозначим через наибольший из порядков функций, принадлежащих множеству .

Определение 4: Порядком замкнутого класса с конечным базисом называется такое натуральное число , что (здесь минимум берется по всевозможным базисам класса ).

Теорема 1: Конъюнкция, дизъюнкция и отрицание образуют полную систему функций в .

Это утверждение вытекает из следствия 2 теоремы о разложении и соотношения: .

Из того, что и , а также из рассмотренной теоремы и неполноты каждой из систем , получаем следующие следствия.

Следствие 1: Системы функций и образуют базисы множества .

Далее, т.к. , то , .

Следствие 2: Функция образуем базис .

Следствие 3: Порядок класса равен 2.

Введём в рассмотрение принцип двойственности, имеющий в дискретной математике очень важное значение.

Определение 5: Функция называется двойственной к функции .

Из определения следует, что:

1) функция двойственна к функции ,

2) функция двойственна к функции ,

3) функция двойственна к функции ,

4) функция двойственна к функции ,

5) функция двойственна к функции ,

6) функция двойственна функции .

Заметим, что двойственная функция к двойственной функции есть исходная функция, т.е. .

Теорема 2: (принцип двойственности). Если данная функция имеет вид: , то двойственная ей функция: , где – это функции, двойственные к функциям соответственно.

Доказательство: Имеем

Что и требовалось доказать.

Пусть некоторое множество функций из . Обозначим через множество всех тех функций, которые являются двойственными к функциям из множества .

Определение 6: Назовем множество двойственным к . Множество называется самодвойственным, если .

Тогда в силу принципа двойственности имеют место следующие утверждения.

Следствие 1: Если – замкнутый класс, то также образует замкнутый класс.

Следствие 2: Если – замкнутый класс и система функций полна в , то система полна в , т.е. из следует, что .

В частности, если является базисом замкнутого класса , то является базисом .

Следствие 3: Если , то .

Определение 7: Функция называется самодвойственной, если , т. е. .

Из доказанной теоремы следует, что суперпозиция самодвойственных функций самодвойственна, т. е. множество самодвойственных функций образует замкнутый класс.

Замечание: Заметим, что константы являются несамодвойственными функциями.