Similar presentations:
Двойственность. Дискретная математика
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 zx 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)
0 1
0 1
0 1
1 0
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 xz 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