Мінімізація логічних функцій

Мінімізація логічних функцій за Квайном.

Кроки алгоритму мінімізації логічних функцій за Квайном:

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

2. У ДДНФ здійснити всі операції неповного склеювання конституент одиниці.

3. Зробити поглинання імплікантами всіх конституент одиниці, які беруть участь у неповному склеюванні.

4. Здійснити операції неповного склеювання і поглинання імплікант з п-1 змінною, одержаних на першому кроці склеюванні за аналогією з пунктом 2 і 3.

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

Приклад. Знайти скорочену ДНФ логічної функції

Розв’язання

1. Застосовуючи операцію розгортання, отримаємо ДДНФ функції .

2. Здійснимо в ДДНФ функції усі можливі операції неповного склеювання конституент одиниці.

Для цього пронумеруємо всі конституенти одиниці функції

і виконаємо щодо цих конституент усі можливі операції неповного склеювання.

Результати такого склеювання занесемо до таблиці, в якій перший стовпчик показує номери конституент одиниці, другий – результат склеювання, третій змінні, за якими відбулося склеювання.

№	Номери конституент, які склеюються	Імпліканти	Змінна, яка склеюється
1	1-2		z
2	1-3		x
3	2-5		y
4	3-4		y
5	4-6		z
6	5-6		x

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

Очевидно, що подальше склеювання отриманих у таблиці імплікант неможливе, і тому вони будуть простими. Тобто одержана ДНФ буде скороченою.

Цей вираз містить шість простих імплікант. Серед них знаходяться й добутки, що належать початковій функції . Тому інші імпліканти можна вважати зайвими.

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

Таким чином, скорочена ДНФ – це далеко не завжди мінімальна ДНФ, оскільки вона хоч і містить прості імпліканти, проте серед них можуть бути й надлишкові.

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

З метою визначення мінімальної ДНФ використовуються імплікантні матриці.

Проста імпліканта	Конституента
	1	2	3	4	5	6
	х	х
	х		х
		х			х
			х	х
				х		х
					х	х

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

Якщо імпліканта є власною частиною деякої конституенти одиниці, то клітинка імплікантної матриці, що відповідає цій імпліканті та конституенті одиниці, помічається позначкою.

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

Мінімальна кількість імплікант, що накривають хрестиками всі стовпчики, дорівнює 3: ху – накриває перший і другий; - третій і четвертий;- п’ятий і шостий. Можна накрити й інакше:- перший і третій;- другий і п’ятий;- четвертий і шостий.

Отже, дана логічна функція має дві мінімальні ДНФ з однаковою кількістю літер (6):

1.

2.