lec04
.pdfПокрытие NL максимальными интервалами называется приводимым, если из этого покрытия можно выбрать хотя бы один максимальный интервал так, что оставшиеся максимальные интервалы покрывают БФ. В противном случае он называется неприводимым.
ДНФ, отвечающая неприводимому покрытию, называется
неизбыточной или тупиковой.
21
Теорема 4.3. Для любой булевой функции Dmin является неизбыточной.
Доказательство: от противного.
1)
Dmin = K1 … Ki … KS.
Покажем, что все Ki в Dmin отвечают Nmax.
Пусть Ki, которое не отвечает требованиям для максимальных интервалов неприводимого покрытия
Kʹ : |
|
N |
Kʹ |
N , где | |
|
| < |N |
Kʹ |
| rang K |
i |
> rang Kʹ, |
|
|
|
f |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
т.е. исходная ДНФ не была минимальной.
(Обратное не верно – не всякая тупиковая ДНФ является min).
2) Покрытие NS, отвечающее D1 = K1 … Ki … KS, не приводимо. Действительно, если бы оно было приводимо, то Ki отбросив которое покрытие не нарушается и получаем некоторое D2: D2 Ki = D1, т.е. rang D2 < rang D1.
22
Пример 4.6.
= (0000 1111); n = 3
n = 3, |NK|=4(=2n-r).n – r = 2. r = 1 т.е.
rang k = 1 DC = x1
(т.к. лишь оно равно 1)
23
Maксимальный интервал NK называется ядровым для булевой функции , если при его отбрасывании нарушается покрытие носителя.
(т.е. если есть вершина, которая не покрывается другими max интервалами функции ).
Логическая сумма всех ядровых интервалов называется
ядром (ядровый ДНФ) и обозначается
Dφ
24
Теорема 4.4. Все конъюнкции, входящие в состав min ДНФ для функции , содержатся в сокращенной ДНФ, т.е. отвечают max интервалам.
Доказательство. От противного.
Пусть Dmin – некоторая min ДНФ для (возможны несколько min ДНФ), которая содержит Ki конъюнкцию: Ki DC. Тогда:
Dmin = K1 K1 … Ki … Kn
Т.к. NKi – не является max интервалом, найдется интервал Kʹ такой, что:
NKi NKʹ Nf
Заменив в покрытии интервал NK на NKʹ, покрытие не нарушится и поэтому сохраняется равенство
f = K1 K1 … K … Kn = D
Сравним Dmin и D . NKi имеет rang Ki > rang K rang Dmin > rang D , ч.т.д.
25
Теорема 4.5. Все ядровые конъюнкции входят в состав любой min ДНФ для функции .
Доказательство. Вытекает из теоремы 4.4 и определения Dφ.
Согласно теореме 4.4 все конъюнкции из Dmin отвечают max интервалу функции . Если какой-нибудь из ядровых интервалов для ядровых конъюнкций Dmin, то оставшиеся интервалы не могут покрыть Nf не выполняется равенство: Dmin = , что противоречит def Dmin.
Эти теоремы можно мнемонически объединить:
Dφ Dmin DC
Замечание 4.3. ! Всегда выполняется Dmin = , DC = , но Dφ = - не всегда. Т.о. необходимо иметь в виду:
Dφ = Dmin = Dφ и других Dmin не существуют.
Общий случай Dφ ; для отыскания Dmin надо дополнить Dφ конъюнкциями из DC, пока не получится покрытие .
26
Пример 4.6б.
= (0000 1111)
Найти Dφ
Dφ = x?1
Dφ = ?
Dmin = x1
27
Пример 4.5б.
Найти Dφ для = (1011 1101)
Отбрасывая любой из max интервалов мы не получим грань не покрытую другим интервалом, т.е.
Dφ = ?0
Согласно замечанию 4.2. дополняем Dφ конъюнкциями из DC, пока не получится покрытие
D1 |
= 1 2 2 3 |
1 3 |
(для Nf = I1 I3 |
I5) |
|
D2 |
= 1 3 1 2 |
2 3 |
(для Nf = I2 I4 |
I6) |
|
Для булевой некоторые ДНФ D называются неизбыточными, если
1) все конъюнкции из DC отвечают Nmax; 2) эти интервалы покрывают NB ; = D;
3) отбрасывание какого-либо из этих интервалов нарушает покрытие (равенство) = D. Очевидно, Dmin является неизбыточный.
NB = I1 I2 I4 I6 ?
избыточное покрытие, т.к. можно отбросить I1
NB = I1 I2 I4 I5 ?
неизбыточное покрытие, никакой интервал нельзя убрать без нарушения покрытия.
Алгоритм получения минимальной ДНФ.
1.Выделяем носитель функции.
2.Выделяем все возможные max интервалы. Для B3 – интервалы:
Ранга 1 - могут быть 4 вершины, лежащие в одной грани. Ранга 2 – любые 2 вершины, соединенные ребром. Ранга 3 – любая отдельная вершина.
3.Выписываем конъюнкции из DC для max интервалов (простые импликанты).
4.Выделяем ядро функции.
5.Используя ядро функции и комбинацию неядровых интервалов, получаем все неприводимые покрытия, для каждого из которых выписываем тупиковую ДНФ.
6.Среди тупиковых ДНФ выбираем минимальную.
30