![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Метод є узагальненням методу Квайна-МакКласки й заснований на перетвореннях кон ’ юнкцій разом з ярликами.
При мінімізації систем булевих функцій склеюються набори, що допускають склеювання і ярлики яких мають непорожній перетин, результату склеювання приписується цей перетин ярликів.
0 1 0 f1f3 0 1 0 f2f3
1 1 0 f1f2 1 1 0 f1f4
~ 1 0 f1 Не склеюються
Кожний з наборів, що склеюються, відзначається тільки тоді, коли ярлик результату склеювання і ярлик цього набору рівні.
Формулювання методу
На першому кроці виписується множина М1 систем булевих функцій, у цю множину входять набори, на яких хоча б одна булева функція дорівнює одиниці. Кожному набору приписується ярлик - множина функцій, що порівнюють одиниці на цьому наборі.
На другому кроці множина М1 розбивається на класи М1i, де 0£i£n.
На третьому кроці виконуються всілякі склеювання наборів сусідніх класів М1i і М1i+1 з урахуванням особливостей склеювання наборів для систем булевих функцій. У результаті формується множина М1i’ результатів склеювань, де 0£i£n-1.
На четвертому кроці невідмічені набори множини М1 запам'ятовуються як максимальні набори системи булевих функцій.
Кроки 3, 4 виконуються для наборів непустої множини М1i ’.
На п'ятому кроці будується таблиця покриттів, рядки якої зіставляються знайденим максимальним наборам, стовпці – елементам множини М1, причому, кожен елемент повторюється стільки разів, скільки булевих функцій складають його ярлик, у ярлик кожного набору входить тільки одна функція з вихідного ярлика, для кожного своя.
На шостому кроці вирішується завдання про покриття й будується система ДНФ. При розподілі простих імплікант по ДНФ функцій системи враховуються ярлики.
Комплекс кубів і таблиця покриттів (табл. 31.2) виглядають:
К0: х1 х2 х3 K1: x1 x2 x3 K2: x1 x2 x3 K3:= Æ
0 0 0 f2f3Ú ~ 0 0 f2 0 ~ ~ f3
1 0 0 f1f2 0 ~ 0 f3Ú
0 1 0 f1f3Ú 0 0 ~ f2f3
0 0 1 f2f3Ú 0 1 ~ f1f3
0 1 1 f1f3Ú 0 ~ 1 f3Ú
1 1 1 f2f3 ~ 1 1 f3.
Таблиця 31.2
000 f2 | 000 f3 | 100 f1 | 100 f2 | 010 f1 | 010 f3 | 001 f2 | 001 f3 | 011 f1 | 011 f3 | 111 f2 | 111 f3 | |
100 f1f2 | ||||||||||||
111 f2f3 | ||||||||||||
~00 f2 | ||||||||||||
00~ f2f3 | ||||||||||||
01~ f1f3 | ||||||||||||
~11 f3 | ||||||||||||
0~~ f3 |
Сукупність простих імплікант, обраних у покритті, визначає другу систему ДНФ, наведену раніше.
x1`x2`x3 /f1f2, x1x2x3 /f2f3, `x1`x2 /f2f3, `x1x2 /f1f3.
Можна виконати узагальнення методу Барті-Полянського для не повністю певних булевих функцій аналогічно відповідному узагальненню методу Квайна-МакКласки.
Дата публикования: 2014-11-18; Прочитано: 259 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!