Методи побудови скороченої ДНФ

Одним із методів знаходження скороченої ДНФ функції є метод, запропонований 1952 р. Куайном (W. Quine). У цьому методі до досконалої ДНФ булевої функції послідовно застосовують такі рівносильності:

неповне склеювання ;

поглинання (члена ки)

де k -- елементарна кон'юнкція, и - змінна. Кажуть, що члениku та склеюються поuі в результаті даютьk. Склеювання назива­ють неповним, оскільки члениku та залишаються у правій частині.

Алгоритм Куайна.

Крок 1.Булеву функцію f (x ₁,..., х_n), яку потрібно мінімізувати, записати у досконалій ДНФ, позначити її f ₀. Виконати i: =0.

Крок 2.Якщо до ДНФ f не можна застосувати жодного неповного склеювання, то зупинитись: f_i - скорочена ДНФ. Інакше на основі ДНФ f_i побудувати ДНФ f_{i+ 1} за таким правилом: у формі f_i. виконати всі неповні склеювання, які можна застосувати до елеме­нтарних кон'юнкцій рангуп-і, після цього вилучити всі елемен­тарні кон'юнкції рангуп-і, до яких можна застосувати поглинання.

Крок 3.Виконати і: =і+1 і перейти до кроку 2. ▲

Отже, в алгоритмі Куайна, починаючи з досконалоїДНФ f₀ будують послідовність ДНФ f ₀, f ₁, f ₂,... доти, доки не отримають скоро­чену ДНФ.

Алгоритм Куайна обґрунтовує така теорема.

Теорема 8.26.Для будь-якої булевої функції f результатом застосування алгоритму Куайна до досконалої ДНФ цієї функції є скорочена ДНФ функції f. ▲

Приклад 8.25.Побудуємо скорочену ДНФ для булевої функції, яку задано досконалою ДНФ f ₀:

Виконаємо i: =0. Застосовуючи неповне склеювання до членів 1 та 2, 2 та 5, 3 та 4, 4 та 5, одержимо

Після п'ятикратного застосування поглинання, одержимо

Виконаємо i: =1. Оскільки жодне неповне склеювання не може бути застосоване, то дістали кінцевий результат і f ₁ - скорочена ДНФ.▲

Мак-Класкі (МсСluskеу) удосконалив алгоритм Куайна.

Алгоритм Мак-Класкі.

Крок 1.Булеву функцію, яку потрібно мінімізувати, записати у досконалій ДНФ.

Крок 2.Упорядкувати змінні й записати їх у кожній елементар­ній кон'юнкції у вибраному порядку. Після цього зобразити кожну елементарну кон'юнкцію послідовністю з 1, 0 та - (риска). На i -й позиції записати 1, якщо i -а змінна входить до елементарної кон'юнкції без заперечення, 0, якщо входить із запереченням, і риску, якщо зовсім не входить. Наприклад, елементарні кон'юнкціїхуz, , записують, відповідно, у вигляді 111-, 1-0-, 1- - 0.

Крок 4.Виконати всі можливі склеювання . Склею­вання можна застосувати лише до елементів списку, які містяться у сусідніх класах. Елементи, які склеюють, знаходять у сусідніх класах простим порівнянням: ці елементи повинні відрізнятись точно в одній позиції і в цій позиції не повинна бути риска (-).

Якщо помістити до одного класу всі k, які були отримані із двох сусідніх класів, то на наступному кроці знову доведеться порів­нювати лише елементи із сусідніх класів. Елементи, які беруть участь у склеюванні, позначити *; надалі вони не залишаться у списку простих імплікант. Попередній список після опрацювання матиме такий вигляд:

Непозначеними * залишилися 4 елементи: 01-; 10-; -11; 1-1. Отже, множина всіх простих імплікант функції

така:

а її скорочена ДНФ- . ▲

Метод Блейка. В алгоритмах Куайна і Мак-Класкі знаходження скороченої ДНФ починають з досконалої ДНФ. У багатьох випад­ках доводиться знаходити скорочену ДНФ функції, що задана довільною ДНФ (не досконалою ДНФ). У таких випадках доцільно користуватись методом Блейка (A. Blake).

Метод Блейка заснований на застосуванні рівносильності уза­гальненого склеювання.

де А, В, С- довільні формули.

Якщо, у цій рівносильності АВ≠ 0, то кажуть, що до членівАСта ВСможна застосувати нетривіальне узагальнене склеювання.

Доведемо рівносильність узагальненого склеювання, викори­стовуючи закони алгебри Буля:

Теорема 8.27. Якщо в будь-якій ДНФ булевої функції f виконати всі можливі узагальнені склеювання і після цього всі поглинання, то в результаті одержимо скорочену ДНФ функції f.

Доведення. ґрунтується на тому, що в результаті багатократного застосування рівносильності узагальненого склеювання до довіль­ної ДНФ булевої функції можна отримати будь-яку просту імпліканту цієї функції. ▲

Метод Блейка полягає в тому, що у довільній ДНФ заданої булевої функції спочатку здійснюють усі допустимі узагальнені склеювання(причому отримані в результаті узагальнених склеювань члени беруть участь у нових узагальнених склеюваннях). Після цього здійснюють поглинання, тобто вилучають диз'юнктивні члени вигляду АВ у разі наявності диз'юнктивних членів А або В. У результаті отримують скорочену ДНФ.

Приклад 8.26. Знайдемо за методом Блейка скорочену ДНФ булевої функції . Легко побачити, що перший і другий члени формули f допускають узагальнені склеювання як по jc, так і по> >. Але члени, які виникають у результаті цих склеювань, дорівнюють нулю. Нетривіальне узагальнене склеювання тут мож­ливе лише для першого і третього членів формули f. Застосуємо це склеювання й одержимо ДНФ .

У цій формі нетривіальне узагальнене склеювання можна застосувати до першого і третього, а також до другого і четвертого членів. Проте, обидва ці склеювання дають члени, які вже є у формі f ₁. Отже, можна вважати, що у формі f ₁виконані всі можливі в ній узагальнені склеювання. Виконаємо поглинання (член поглинається членомyz)і одержимо скорочену ДНФ ▲

Розглянемо, ще один метод побудови скороченої ДНФ - метод Нельсона (R. Nelson).Цим методом зручно користуватись, якщо функція задана довільною кон'юнктивною нормальною формою.

Метод Нельсона обґрунтовує така теорема.

Теорема 8.28. Якщо в будь-якій кон'юнкгивній нормальній формі булевої функції розкрити всі дужки відповідно до дистрибутивного закону і виконати всі поглинання, то в результаті отримаємо скорочену ДНФ цієї функції.

Для доведення достатньо переконатись, що у разі розкриття дужок удовільній кон'юнктивній нормальній формі d _l∧ d ₂∧...∧ d_m булевої функції f можна отримати будь-яку наперед задану просту імплікантуkцієї функції.▲

Приклад 8.27. Розглянемо булеву функцію f, задану кон'юн­ктивною нормальною формою .

Розкриваючи дужки: .

Виконаємо поглинання й одержимо скорочену ДНФ булевої функції f:

.▲

Методи Куайна, Мак-Класкі, Блейка, Нельсона використовують для знаходження скороченої ДНФ, що складає перший етап міні­мізації.

8.5.3. Побудова тупикових ДНФ

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

Імплікантною таблицею будь-якої булевої функції є прямокутна таблиця, рядки якої позначено різними простими імплікантами функції f, а стовпці - наборами значень змінних (або відповідними їм консттуентами одиниці), на яких функція приймає значення 1.

Якщо деяка проста імпліканта k _pперетворюється в 1 на наборі , який позначає деякий стовпчик імплікантної таблиці, то на перетині рядка, позначеного k_p, і стовпчика, позначеного набором (або відповідною йому конституентою одиниці К), ставлять зірочку. У такому випадку кажуть, що проста імпліканта накриває одиницю булевої функції. Якщо стовпці імплікантної таблиці поз­начено конституентами одиниці, то, очевидно, таблицю слід запов­нювати за таким правилом.

На перетині рядкаk_р та стовпцяКімплікантної таблиці тоді й лише тоді ставлять зірочку, коли імплікантаk_р становить деяку частину конституенти К (можливо, збігається з усією консти­туентою).

Вище методом Куайна для функції знайдено скорочену ДНФ . Ця функція має чотири прості імпліканти приймає значення 1 на п'яти наборах (010), (011), (100), (101), (111), яким відповідають конституенти одиниці .

За сформульованим правилом будуємо імплікантну таблицю для цієї функції (див. табл. 8.8).

Тфблиця 8.8

kp \ K
	*	*
			*	*
				*	*
		*			*

Побудову тупикових ДНФ можна здійснити безпосередньо за імплікантою таблицею. Якщо у стовпчику є лише одна зірочка, то проста імпліканта, яка позначає рядок із цією зірочкою, повинна бути вибрана обов'язково. Множину таких простих імплікант називають ядром булевої функції. У розглянутому прикладі ядро складають прості імпліканти у та х . імпліканти ядра входять у будь-яку тупикову ДНФ, але вони можуть накривати лише частину одиниць булевої функції. Стосовно імплікантної таблиці зручно казати, що прості імпліканти накривають конституенти, що відпо­відають цим одиницям. Виключимо з імплікантної таблиці стовп­чики, що мають зірочки на перетині з рядками, позначеними імплі­кантами ядра. Після цього методом перебору можна знайти міні­мальні системи простих імплікант, які накривають решту консти­туент одиниці. Таким способом ми знаходимо всі тупикові ДНФ, із яких і вибираємо мінімальні ДНФ. У цьому прикладі єдина консти­туента, що лишається не накритою імплікантами ядра, - це конституентахуz. Її можна накрити як імплікантою хz, так і імплікантою уz. Внаслідок цього отримаємо дві тупикові ДНФ: та . Обидві ці ДНФ є мінімаль­ними (мають по шість букв кожна).

Зазначимо, що метод перебору практично застосовний лише для відносно простих імплікантних таблиць; його можна також застосувати, коли потрібно знайти не всі, а лише одну тупикову ДНФ. Для знаходження всіх тупикових ДНФ у випадку складних таблиць можна застосувати метод, запропонований 1956 р. С. Петріком (S. Petrick).

Опишемо коротко цей метод.

Крок 1.Прості імпліканти позначають великими латинськими буквами. Для табл. 8.8 це виглядатиме так:

; ; C xz; D yz.

Крок 2.Для кожного стовпця імплікантної таблиці будують диз'юнкцію букв, які відповідають рядкам із зірочками у цьому стовпці.

Крок 3.Записують кон'юнкцію отриманих диз'юнкцій. Для табл. 8.8 це приведе до виразуA(A∨ D)B(B∨ C)(C∨ D).Його нази­вають кой'юнктивніш зображенням імплікантної таблиці.

Крок 4.В одержаному на кроці 3 кон'юнктивному зображенні імплікантної таблиці розкривають всі дужки за дистрибутивним законом. Знайдений вираз називають диз'юнктивним зображен­ням імплікантної таблиці.

Крок 5.До отриманого на кроці 4 диз'юнктивного зображення імплікантної таблиці застосовують всі можливі поглинання А∨ АВ=А та усувають всі повторення АА-А, A∨ A=A.Одержаний вираз називають зведеним диз'юнктивним зображенням імплікантної таблиці. Зазначимо, що в процесі знаходження зведеного диз'юнк­тивного зображення імплікантної таблиці з кон'юнктивною зобра­ження можна застосовувати різні перетворення за законами булевої алгебри, які не містять заперечень, ще до отримання звичайного (не зведеного) диз'юнктивного зображення. Тобто, кроки 4 та 5 можна об'єднати і знаходити одразу зведене диз'юнктивне зображення імплікантної таблиці.

Крок 6.Прості імпліканти, позначення яких входять у будь-який фіксований диз'юнктивний член зведеного диз'юнктивного зобра­ження імплікантної таблиці, утворюють тупикову ДНФ. Щоб отри­мати всі тупикові ДНФ потрібно розглянути всі диз'юнктивні члени цього зображення. Продовжуючи розгляд табл. 8.8, можемо записати:

Кон'юнкції ABC, очевидно, відповідає тупикова ДНФ , а кон'юнкціїABD - тупикова ДНФ . ▲