Дискретная математика

1. Дискретная математика

2. Двойственная функция

• Функция
*
f ( x1 , x 2 , , x n ) f ( x1 , x 2 , , x n )
называется двойственной
функцией к функции
f ( x1 , x 2 , , x n ) .

3. Замечание:

• У двойственной функции на
противоположных наборах принимаются
противоположные значения:
если
,
то
.
f ( 0,0,1 ) 1
*
f ( 1,1,0 ) 0

4. Самодвойственная функция

• Функция называется
f ( x1 , x 2 , , x n )
самодвойственной,
если
*
f ( x1 , x 2 , , x n ) f ( x1 , x 2 , , x n ).

5. Пример 1

Пусть
f x, y - дизъюнкция.
x y
Тогда, двойственной к ней является конъюнкция:
f
x, y f x , y x
y xy

6. Пример 2

f x, y xy
Пусть
- конъюнкция
Тогда, двойственной к ней является дизъюнкция:
f
x, y f x , y x y x
y

7. Пример 3

f x x
Пусть
- тождество.
Тогда, двойственной к ней является:
f
x f x x x

8. Пример 4

f x x
Пусть
- отрицание.
Тогда, двойственной к ней является:
f
x f x x x

9. Замечание:

• Тождество и отрицание –
самодвойственные
функции.

10. Пример 5

Пусть
f x 0
- константа 0.
Ее переменная x – фиктивна, в
формуле отсутствует.
Тогда, двойственной к ней
является:
f
x f x 0 1.

11. Пример 6

Пусть
f x 1
- константа 1.
Ее переменная x – фиктивна, в
формуле отсутствует.
Тогда, двойственной к ней
является:
f
x f x 1 0.

12. Замечание:

• Отношение двойственности
симметрично.
Если f двойственна к g,
то и g двойственна к f.

13. Пример 7

Найти двойственную для функции:
f x, y, z xy xz yz.
Решение:
f
x, y,z x y
x z y z
x y x z y z
x y x z y z

14. Продолжение примера 7

x y x z y z
x yz y z xy xz yz yz
xy xz yz.
f x1 ,x2 , ,xn f
*
x1 ,x2 , ,xn
Данная функция самодвойственна.

15. Замечание:

• Вектор-столбец
самодвойственной
функции антисимметричен
относительно своей
середины.

16. Продолжение примера 7

F xy xz yz.
x
y
z
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
F(x, y, z)
01
01
01
10
0
1
1
1

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

Если в формуле F, представляющей
функцию f все знаки функций заменить
на знаки двойственных функций,
то получится формула F ,
представляющая функцию f
двойственную к f.

18. Принцип двойственности для Булевой алгебры

Если в формуле F, представляющей
функцию f все конъюнкции заменить
на дизъюнкции, дизъюнкции
на конъюнкции, 1 на 0 и 0 на 1,
то получится формула F ,
представляющая функцию
f
двойственную к f.

19. Пример 8

Воспользуемся принципом
двойственности.
f ( x , y , z ) xy x z yz
f ( x, y,z ) x y x z y z
x y x z y z
x y x z y z
x y z xyz