Точний метод мінімізації систем булевих функцій Барті-Полянського

Метод є узагальненням методу Квайна-МакКласки й заснований на перетвореннях кон ’ юнкцій разом з ярликами.

При мінімізації систем булевих функцій склеюються набори, що допускають склеювання і ярлики яких мають непорожній перетин, результату склеювання приписується цей перетин ярликів.

0 1 0 f₁f₃ 0 1 0 f₂f₃

1 1 0 f₁f₂ 1 1 0 f₁f₄

~ 1 0 f₁ Не склеюються

Кожний з наборів, що склеюються, відзначається тільки тоді, коли ярлик результату склеювання і ярлик цього набору рівні.

Формулювання методу

На першому кроці виписується множина М₁ систем булевих функцій, у цю множину входять набори, на яких хоча б одна булева функція дорівнює одиниці. Кожному набору приписується ярлик - множина функцій, що порівнюють одиниці на цьому наборі.

На другому кроці множина М₁ розбивається на класи М₁ⁱ, де 0£i£n.

На третьому кроці виконуються всілякі склеювання наборів сусідніх класів М₁ⁱ і М₁ⁱ⁺¹ з урахуванням особливостей склеювання наборів для систем булевих функцій. У результаті формується множина М₁^i’ результатів склеювань, де 0£i£n-1.

На четвертому кроці невідмічені набори множини М₁ запам'ятовуються як максимальні набори системи булевих функцій.

Кроки 3, 4 виконуються для наборів непустої множини М₁^{i ’}.

На п'ятому кроці будується таблиця покриттів, рядки якої зіставляються знайденим максимальним наборам, стовпці – елементам множини М₁, причому, кожен елемент повторюється стільки разів, скільки булевих функцій складають його ярлик, у ярлик кожного набору входить тільки одна функція з вихідного ярлика, для кожного своя.

На шостому кроці вирішується завдання про покриття й будується система ДНФ. При розподілі простих імплікант по ДНФ функцій системи враховуються ярлики.

Комплекс кубів і таблиця покриттів (табл. 31.2) виглядають:

К₀: х₁ х₂ х₃ K₁: x₁ x₂ x₃ K₂: x₁ x₂ x₃ K₃:= Æ

0 0 0 f₂f₃Ú ~ 0 0 f₂ 0 ~ ~ f₃

1 0 0 f₁f₂ 0 ~ 0 f₃Ú

0 1 0 f₁f₃Ú 0 0 ~ f₂f₃

0 0 1 f₂f₃Ú 0 1 ~ f₁f₃

0 1 1 f₁f₃Ú 0 ~ 1 f₃Ú

1 1 1 f₂f₃ ~ 1 1 f₃.

Таблиця 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

Сукупність простих імплікант, обраних у покритті, визначає другу систему ДНФ, наведену раніше.

x_{1`</sub>x<sub>2`}x₃ /f₁f₂, x₁x₂x₃ /f₂f₃, _{`</sub>x<sub>1`}x₂ /f₂f₃, _`x₁x₂ /f₁f₃.

Можна виконати узагальнення методу Барті-Полянського для не повністю певних булевих функцій аналогічно відповідному узагальненню методу Квайна-МакКласки.