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 - тупикова ДНФ . ▲