1.5. Спрощення формул

Розглянуті нами досконалі форми (ДДНФ і ДКНФ) є найбільшими (найдовшими) з усіх ДНФ і КНФ певної функції. ДДНФ і ДКНФ самі по собі не застосовні ні в мікросхемотехніці, ні в інших галузях. Їх основне призначення в тому, що всі основні алгоритми скорочення ДНФ і КНФ починаються з побудови ДДНФ і ДКНФ відповідно. А саме скорочення будь-якої логічної функції є основною метою перетворень формул булевої алгебри. Для спрощення (скорочення) формул використовують такі властивості (див. табл.1.11):

1. Поглинання

(див. 5 а. табл. 1.11);

(див. 5 б. табл. 1.11).

2. Скліювання

(див. 9 а. табл. 1.11);

(див. 9 б. табл. 1.11)

3. (див. 12 табл. 1.11).

Приклад 1.28. Наведемо приклади спрощення формул.

1)

2)

Слід зауважити, що процедура скорочення формул логічних функцій не є простою, вона потребує навичок і вмінь, яких людина набуває з досвідом. Але на допомогу в цьому випадку приходять алгоритми, які є більш ефективними процедурами. Є декілька алгоритмів скорочення ДНФ (КНФ), всі вони на початковому етапі використовують ДДНФ (ДКНФ). Тобто задля того, «щоб скоротити, спочатку треба збільшити». Ми розглянемо один алгоритм скорочення, який називається метод Квайна.

1.5.1. Утворення скороченої днф методом Квайна

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

(див. 9а. табл.. 1.11),

де два члени і склеюються за змінній .

Операція поглинання:

(див. 5б. табл.. 1.11),

член поглинається членом .

Теорема Квайна. Якщо в ДДНФ логічної функції провести всі операції склеювання, а потім усі операції поглинання, то отримаємо скорочену ДНФ.

Метод Квайна виконується в декілька етапів (підкреслимо, що перетворення треба починати, виходячи з ДДНФ).

1 Етап. Початкове скорочення формули.

Цей етап містить три кроки:

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

2. Провести можливі склеювання членів -го рангу, потім поглинання. Утворяться кон’юнкції -го рангу.

3. Виконати операції склеювання членів -го рангу, одержати кон’юнкції -го рангу і т.д.

Приклад 1.29. Скоротимо функцію, яку подано в вигляді ДДНФ:

Кон’юнкціями 4-го рангу є ( див. табл.1.23 ):

.

Проведення всіх можливих склеювань за однією змінною наведено в табл.1.23, в результаті отримаємо кон’юнкції 3-го рангу:

.

Виконання операцій поглинання приводить до вилучення всіх кон’юнкцій четвертого рангу.

Таблиця 1.23
	1
		1
			1
				1
					1
						1
							1
								1

Кон’юнкції 3-го рангу залишаються.

Проведення всіх можливих склеювань кон’юнкцій 3-го рангу наведено в табл.1.24. В результаті отримаємо кон’юнкцію 2-го рангу . Виконання операцій поглинання приводить до вилучення кон’юнкцій 3-го рангу , , , .

Залишаються кон’юнкції 3-го рангу

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

Таблиця 1.24
1	2	3	4	5	6	7	8	9	10
	1
		1
			1
Продовження таблиці 1.24
1	2	3	4	5	6	7	8	9	10
				1
					1
						1
							1
								1
									1

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

, , , , , .

Але на цьому процес скорочення формули за методом Квайна не закінчено. Ми скоротили ДДНФ до доданків рангом не більше за три. Чи можна скоротити ще? Наприклад, за рахунок кількості доданків. Продовжимо.