Презентации лекций / Презентация лекции 5 ДМ 20
.pdf
ПустьфункциязаданаДНФ. Любаяэлементарнаяконъюнкция, входящаяв этуДНФ,
– импликантафункции (необязательнопростая)
Пусть = ….
Возьмемлюбойвектор такой,что
= 1.Тогда () = ()…= 1…= 1.
Пример:
( , )
|
|
0 |
0 |
|
1 |
|
|
|
0 |
1 |
|
0 |
|
|
|
1 |
0 |
|
1 |
|
|
|
1 |
1 |
|
1 |
|
= ̅̅ |
̅ |
̅̅ |
||||
|
̅ |
|||||
= ̅ |
|
|
||||
|
|
|
- импликанты |
|||
|
|
|
||||
= ̅ |
|
|
̅ |
|
||
|
|
|
|
|
|
|
Из них ̅, - простыеимпликанты (после ихудаления остается1,
а онанеимпликанта), остальныеимпликантынеявляются простыми.
1
2
3
11
План лекции
1. Постановка задачи минимизации ДНФ
2. Сокращенная и тупиковые ДНФ
3. Построение минимальных ДНФ
12
Задание функциив виде сокращенной ДНФ
Пусть , ,…, -все простыеимпликантыфункции. Тогдаверноравенство:
= .
Утверждение докажем в конце лекции
Пример:
Формула
называется
сокращенной
дизъюнктивной
нормальной
формойфункции
( , )
0 0 1
0 1 0
1 0 1
1 1 1
Ужеустановили:
̅̅-импликанта , не простая̅-импликанта , не простая-импликанта , не простая ̅- простаяимпликантапростаяимпликанта
Остальныеэ.к.:
1 - не импликанта ̅ -неимпликанта ̅- неимпликантане импликанта
Задаемфункцию ввидесокращеннойДНФ:
= ̅
1
2
3
13
|
1 |
Для заданиянекоторых функций всепростыеимпликантыне нужны – |
2 |
можновключить в дизъюнкциюлишь некоторыеиз простыхимпликант |
3 |
и получить формулу для этой функции.
ДНФназываюттупиковойДНФфункции,если:
(1)Она задаетфункцию
(2)Ее элементарныеконъюнкциипростыеимпликантыфункции
(3)Если удалитьизнеелюбуюизееэ.к.(простуюимпликанту),то получившаяся«укороченная»формуланебудетзадаватьфункцию
ЛюбаяминимальнаяДНФ функции является тупиковойДНФ,
т.е. э.к.,которыеееобразуют,– простыеимпликанты,и ее нельзя«укоротить».
Утверждение докажем в конце лекции 14
План лекции
1. Постановка задачи минимизации ДНФ
2. Сокращенная и тупиковые ДНФ
3. Построение минимальных ДНФ
15
Алгоритмрешения задачи минимизацииДНФ
(один из многих)
СДНФ
1этап.ПреобразуемСДНФ функцииопределеннымобразомиполучаемее сокращеннуюДНФ.
2этап.ПосокращеннойДНФ выписываемнаборпростыхимпликант. Понаборупростыхимпликантфункциинаходимвсеее тупиковые ДНФ.
3этап.Вычисляемсложностькаждойтупиковой ДНФ функции. Отбираем тупиковые ДНФ наименьшейсложности. Они и естьминимальные ДНФфункции.
1
Сокращенная
ДНФ
2
Тупиковые
ДНФ
3
Минимальные
ДНФ
1
2
3
16
1 этап. От СДНФ к сокращенной ДНФ
Используются:
1. Операциянеполного склеивания:
=
2. Операция поглощения:
=
3. Операция идемпотентности:
=
0 шаг |
ВыписываемСДНФ.К каждойпареконъюнкцийприменяем |
|||
|
операциюнеполногосклеивания(если это возможно).Спомощью |
|||
|
операциипоглощенияудаляемконъюнкцииранга. Удаляем |
|||
|
получившиесядублируемые конъюнкции.Приходимк . |
|||
шаг |
Кначалушагапостроена . К каждойпаре конъюнкцийранга − |
|||
|
применяемоперациинеполногосклеиванияипоглощения. |
|||
|
Удаляемполучившиесядублируемые конъюнкции. |
|||
|
Приходимк |
. Сравниваем |
с . |
|
|
Если |
и |
совпадают,то |
- сокращеннаяДНФ функции. |
|
Если |
и |
несовпадают,тоувеличиваем наединицу и |
|
повторяем -й шаг.
Примеры: 1. = (1101 0101)
2. = (01000110 01000111)
1
2
3
17
2 этап. От сокращенной ДНФ ктупиковым ДНФ
1. |
Выписываемимпликантнуютаблицу. |
|
|
Элементы носителя: |
|
= 1 |
|
||||||||||
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
… |
|
|
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
… |
|
|
|
… |
|
|
|
|
|
|
Простые |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
… |
|
… |
|
… |
|
… |
|
… |
|
|
… |
|||
|
импликанты |
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
… |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= ( ) |
|
|
… |
|
… |
|
… |
|
… |
|
… |
|
|
… |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
… |
|
|
|
… |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2. |
Составляемформулу: |
: |
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3. |
Преобразуемеев ДНФ надалфавитомпеременных |
, ,…, . |
|
|
|
|
|
|
|||||||||
|
Получаемдизъюнкциюразличныхконъюнкцийвида . |
|
|
|
|
||||||||||||
4. |
Формальнопреобразуемкаждуюконъюнкциювдизъюнкцию |
|
. |
|
|
|
|||||||||||
5. |
Сделавобратныезамены,из каждойтакойдизъюнкцииполучаемтупиковую ДНФ. |
|
|||||||||||||||
Примеры: 1. = (11010101) |
|
|
2. = (010001100100 0111) |
|
|
|
|
||||||||||
1
2
3
18
1
2
3 этап. От тупиковыхДНФ к минимальнымДНФ |
3 |
|
Вычисляемсложностькаждойтупиковой ДНФ.
Отбираем ДНФнаименьшейсложности.
Они есть минимальные ДНФ.
Примеры: 1. = (1101 0101)
2. = (01000110 01000111)
19
Каждуюбулевуфункцию , ,…, , заисключениемтождественноравнойнулю, можнозадатьвформесокращеннойДНФ
(т.е.какдизъюнкциювсехпростыхимпликантфункции)
Какдоказать?
Показать: |
|
|
|
|
1.Если |
, |
,…, |
= 1, то и сокращеннаяДНФнанаборе , ,…, равна1. |
|
2.Если сокращеннаяДНФна наборе , ,…, |
равна1, то и , ,…, = 1. |
|||
О
б
о
с
н
о
в
а
н
и
я
20