![](/user_photo/_userpic.png)
Презентации лекций / Презентация лекции 4 ДМ 20
.pdf![](/html/88911/114/html_SZPtLNuv1w._jEF/htmlconvd-rpw_j61x1.jpg)
Тема 4 «Представление булевых функций формулами специального вида»
«Дискретная математика» Олейник Татьяна Анатольевна
кафедра ВМ-1
![](/html/88911/114/html_SZPtLNuv1w._jEF/htmlconvd-rpw_j62x1.jpg)
План лекции
1.Принцип двойственности
2.Задание функции совершенной дизъюнктивной нормальной формой
3.Задание функции совершенной конъюнктивной нормальной формой
4.Задание функции полиномом Жегалкина
2
![](/html/88911/114/html_SZPtLNuv1w._jEF/htmlconvd-rpw_j63x1.jpg)
План лекции
1.Принцип двойственности
2.Задание функции совершенной дизъюнктивной нормальной формой
3.Задание функции совершенной конъюнктивной нормальной формой
4.Задание функции полиномом Жегалкина
3
![](/html/88911/114/html_SZPtLNuv1w._jEF/htmlconvd-rpw_j64x1.jpg)
|
|
1 |
|
|
|
2 |
|
|
|
3 |
|
|
4 |
||
|
|
||
|
-функция, двойственная
|
|
|
|
|
|
4
![](/html/88911/114/html_SZPtLNuv1w._jEF/htmlconvd-rpw_j65x1.jpg)
Функциязадана векторомзначений.
Как найтивектор значений двойственной ейфункции?
|
|
( , ) |
( , ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
0 |
1 |
|
|
= ( |
, |
, |
, |
) → = ( |
|
, |
|
, |
|
, |
|
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1
2
3
4
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5
![](/html/88911/114/html_SZPtLNuv1w._jEF/htmlconvd-rpw_j66x1.jpg)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1
2
3
4
6
![](/html/88911/114/html_SZPtLNuv1w._jEF/htmlconvd-rpw_j67x1.jpg)
Функциязадана формулой.
Как построитьформулу длядвойственной ейфункции?
Действуемпо определению –заменяем вформуле, которойзадана, каждуюпеременную ее отрицанием и надвсейформулой пишем отрицание
Пример: |
|
|
??? |
||
|
|
|
, |
= ( | ) |
|
|
|
, |
|
̅ |
|
|
= (̅,̅) = ̅( ̅|̅) |
|
1
2
3
4
7
![](/html/88911/114/html_SZPtLNuv1w._jEF/htmlconvd-rpw_j68x1.jpg)
Принцип двойственности:
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Если функция заданаформулойФ , , , то формула,полученнаяизнеезаменойсимволовфункций
, ,…насимволы двойственныхимфункций, задаетфункцию , двойственную.
Пример: |
|
|
|
, |
= |
( |
| ) |
, |
= |
( |
↓ ) |
1
2
3
4
Ф = Ф[ , ,…]
Ф называют формулой, двойственной кФ
8
![](/html/88911/114/html_SZPtLNuv1w._jEF/htmlconvd-rpw_j69x1.jpg)
Следствие принципа двойственности:
Важно! Структураформулыдолжнасохраниться.
Доизмененияформулывосстанавливаемскобкиисвязки!
Пример:
= ( |
̅) (1 ) |
= (( |
) ̅) (1 ) |
= (( |
)̅) (0 ) |
1
2
3
4
9
![](/html/88911/114/html_SZPtLNuv1w._jEF/htmlconvd-rpw_j610x1.jpg)
План лекции
1.Принцип двойственности
2.Задание функции совершенной дизъюнктивной нормальной формой
3.Задание функции совершенной конъюнктивной нормальной формой
4.Задание функции полиномом Жегалкина
10