Похожие презентации:
Дискретная математика
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)
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