§ 2.2. Нормальные формы

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

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

Функцию, двойственную к , обозначают , т.е. .

Упражнение 2.16. Используя определение, найти двойственные функции для дизъюнкции, конъюнкции и функций одной переменной.

◄ Пусть . Тогда .

Пусть . Тогда .

Пусть . Тогда .

Пусть . Тогда .

Пусть . Тогда .

Пусть . Тогда .►

Утверждение. Для любой функции выполняется равенство .

◄ .►

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

0	0
0	1
1	0
1	1

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

1. столбец значений функции переписать в обратном порядке (т.е. число, стоящее в первой строке, записать в последнюю строку; число, стоящее во второй строке - в предпоследнюю строку и т.д.);

2. в получившемся в результате выполнения пункта 1 столбце значений каждое число заменить его отрицанием (0 заменить 1 и 1 заменить 0).

Аналогичного алгоритма для получения двойственной функции можно придерживаться и в случае любого числа аргументов.

Упражнение 2.17. Найти функции, двойственные данным:

а) ; б) ;

в) ; г) .

◄ а) .

б) .

в) и г) решите самостоятельно.►

Упражнение 2.18. Найти функции, двойственные данным:

а) ; б) .

◄ а) Вначале зададим функцию таблицей:

0	0	0	1	0	1	1
0	0	1	0	0	1	1
0	1	0	1	0	0	0
0	1	1	0	0	0	0
1	0	0	1	1	0	1
1	0	1	0	0	0	0
1	1	0	1	1	0	1
1	1	1	0	0	0	0

Далее: .

б) решите самостоятельно.►

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

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

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

Поскольку , , , , , , то для получения формулы, двойственной к формуле , нужно в формуле заменить 0 на 1, 1 на 0, связку на связку , связку на связку .

Упражнение 2.19. Реализовать формулами функции, двойственные данным:

а) ; б) ; в) ; г) .

◄ а) .

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

б) .

в) и г) решите самостоятельно.►