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

 

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

Определение 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: Функция называется самодвойственной, если , т. е. .

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

Теорема 3: Суперпозицией из произвольной несамодвойственной функции и отрицания можно получить константы и .

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

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

Ясно, что . Поэтому , а значит – несамодвойственная функция.

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

Пусть , тогда рассмотрим функцию . Эта функция является суперпозицией и . Поскольку , то отождествим для функции переменные : . Имеем , т.е. – константа. Подставляя эту константу в , получим другую константу. Итак, мы представили в виде суперпозиции и обе константы и . Что и требовалось доказать.

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