Презентации лекций / Презентация лекции 5 ДМ 20
.pdf
Тема 5 «Минимизация дизъюнктивных нормальных форм»
«Дискретная математика» Олейник Татьяна Анатольевна
кафедра ВМ-1
План лекции
1. Постановка задачи минимизации ДНФ
2. Сокращенная и тупиковые ДНФ
3. Построение минимальных ДНФ
2
План лекции
1. Постановка задачи минимизации ДНФ
2. Сокращенная и тупиковые ДНФ
3. Построение минимальных ДНФ
3
Есть алфавит переменных = { , ,…} |
1 |
|
2 |
||
|
||
Элементарная конъюнкцияранга над |
3 |
|
Обозначения: |
|
|
- |
|
|
|
|
|
|
|
|
|
|
|
= |
|
формула вида |
|
|
|
|
|
|
|
|
|
|
|
|
= |
|
|
|
|
|
|
|
|
= |
|
все буквы разные |
|
|
|
|
|
||
|
|
|
|
|
|||
Константа1 |
|
|
|
|
|
|
–элементарная |
|
|
|
|
|
|
Примеры: |
|
|
||||
конъюнкцияранга0. |
|
|
||||
|
|
|
– элементарная конъюнкция ранга 3 |
|||
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
– элементарная конъюнкция ранга 4 |
|
|
|
|
|
||
|
|
|
|
|
|
|
Сколько? |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
(всевозможныхэлементарных |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
конъюнкцийнад алфавитомиз |
|
|
|
|
|
|
|
|
|
3 |
3 |
… |
3 |
|
|||
переменных) |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Порядокмножителей не важен
4
1
2
Дизъюнктивнаянормальная форманад
- 3
дизъюнкцияразличных элементарных конъюнкцийнад
Сумма рангов |
|
|
|
|
|
Порядокследования |
конъюнкций– |
|
|
|
|
|
конъюнкций |
Примеры: |
|
|
|
|
||
сложностьДНФ. |
|
|
|
|
не важен |
|
|
|
|
|
– ДНФ сложности 3 |
||
|
|
|
||||
|
|
|
|
– ДНФ сложности 4 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Сколько? |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
(всевозможныхДНФ над |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
алфавитомиз |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
2 |
2 |
… |
2 |
|
|
|
|||
переменных) |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
5
1
2
3
Пример:
( , )
0 0 1
0 1 0
1 0 1
1 1 1
= ̅̅ ̅
ДНФ сложности6 |
|
|
= ̅ |
|
|
ДНФ сложности3 |
Могутбытьварианты! |
|
|
||
= ̅ |
6 |
|
ДНФ сложности2 |
||
|
1
2
3
Дизъюнктивные нормальныеформы, сложностькоторых наименьшая,
… минимальные- ДНФ функции
7
|
1 |
|
2 |
Задачаминимизации ДНФ: |
3 |
|
8
Можно решитьзадачу минимизацииДНФ
методом полного перебора
1шаг.СтроимвсеДНФ надмножеством = { , ,…, }. |
Их |
|
− |
|
2шаг.ОтбираемизпостроенныхДНФте,которыезадаютфункцию
3шаг.ВычисляемсложностькаждойотобраннойДНФ.
ДНФнаименьшейсложностииестьминимальныеДНФ функции .
1
2
3
9
Элементарнуюконъюнкцию называют
импликантой ,
если навсех векторах ,накоторыхравна1, такжеравна1,
т.е. = верно,что = .
Импликантуназывают простой,
еслиприудаленииизнее любой«буквы» получается
неимпликанта.
Пример: |
|
|
( , ) |
|
|||
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
0 |
0 |
|
1 |
1 |
0 |
|
|
|
|
Выпишем всеэлементарныеконъюнкции надалфавитом { }:
1, ̅, ̅, , , ̅̅, ̅, ̅ , ,
|
: |
равна 1на 0,0 , 0,1 |
, 1,0 ,(1,1),а |
|
|
|
|
1,0 = 0.Значит, 1 |
неимпликанта |
|
: |
равна 1на 0,0 и (0,1), |
||
|
|
|
0,0 = 1и 0,1 = 1. |
|
|
|
|
Значит, ̅импликанта. |
|
|
|
|
Простая,т.к.после удалениебуквы ( ̅) |
|
|
|
|
получаем 1, аона неимпликанта. |
|
|
|
|
:равна1 толькона 0,0 , |
|
|
|
|
|
|
0,0 = 1. Значит, ̅̅импликанта.
Непростая, т.к.послеудалениебуквы ̅
получаем импликанту ̅.
…
1
2
3
10