3 Основи теорії мінімізації булевих функцій: побудова мднф та мкнф методом Квайна-Мак-Класки та за допомогою діаграм Вейча

Функція f, яка залежить від змінних х1, х2,…,хn, називається булевою або перемикальною, якщо функція f та кожен з її арґументів xi (i=1,…,n) набувають значення тільки із множини {0, 1}.

Визначення 1. Конституентою одиниці називають функцію , яка набуває значення 1 тільки на одному двійковому наборі. Конституента одиниці записується як логічний добуток різних змінних, деякі з яких можуть бути із запереченням. Булева функція g(x1, …, xn) називається імплікантою булевої функції f(x1,…,xn), якщо для будь-якого набору змінних, на якому g()=1, правильно f()=1.

Визначення 2. Елементарною кон’юнкцією називається кон’юнкція (логічний добуток ) кінцевого числа змінних, кожна з яких може мати або не мати заперечення. Змінна, що має значення 1, записується в прямій формі, а та, що має значення 0 – в інверсній формі. Також сюди слід віднести тотожну константу 1.

Елементарною диз’юнкцією називається диз’юнкція (логічна сума ) кінцевого числа змінних, кожна з яких може мати або не мати заперечення. Змінна, що має значення 0, записується в прямій формі, а та, що має значення 1 – в інверсній формі. Також сюди слід віднести тотожну константу 0.

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

Визначення 3. Диз’юнктивною нормальною формою (ДНФ) є диз’юнкція (логічна сума) елементарних кон’юнкцій.

Кон’юнктивною нормальною формою (КНФ) є кон’юнкція (логічний добуток) елементарних диз’юнкцій.

Визначення 4. Досконалою ДНФ є диз’юнкція конституент одиниці , які відповідають одиничним значенням функції.

Досконалою КНФ є кон’юнкція конституент нуля , які відповідають нульовим значенням функції.

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

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

Визначення 7. Тупікові ДНФ (тупікові КНФ), які містять мінімальну кількість букв є мінімальними. Мінімальних ДНФ (КНФ) функції f(x1,…,xn) може бути декілька.

Розглянемо приклад 3.1 мінімізації булевої функції , яка задана у числовому вигляді (у вигляді множини записано номери конституент одиниці із таблиці істинності даної функції), методом Квайна-Мак-Класки та за допомогою діаграм Вейча. f(, , ,)={2, 4, 6, 8, 15, 16}.

Розв`язання

Будуємо таблицю істинності змінних заданої функції.

	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
f()	0	1	0	1	0	1	0	1	0	0	0	0	0	0	1	1

.

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

1. 0001

2. 0011, 0101

3. 0111, 1110

4. 1111

Виконуємо крок склеювання, який полягає в побудові імплікант, які є результатом склеювання елементів сусідніх груп, що відрізняються тільки в значенні однієї позиції. У результуючій імпліканті на місці відмінності будемо ставити символ ‘-‘. Наприклад, 0001 і 0011 склеюються в 00-1, але 0011 та 1110 склеїти неможливо. Ті імпліканти, що не брали участь у жодному із склеювань залишаються на своєму місці без зміни.

1. 0001* 2. 0011**, 0101** 3. 0111**, 1110* 4. 1111*

1. 00-1*, 0-01* 2. 0-11*, 01-1* 3. –111, 111-

1. 0- -1 3. –111, 111-

* - імпліканта брала участь у склеюванні з однією сусідньою групою,

** - імпліканта брала участь у склеюванні з двома сусідніми групами.

Отримані після склеювання прості імпліканти складають скорочену ДНФ:

.

Для побудови МДНФ будуємо імплікантну таблицю та виконуємо крок поглинання

Двійкове зображення простих імплікант	Двійкові номери конституент
	0001	0011	0101	0111	1110	1111
0 - - 1 	*	*	*	*
- 1 1 1				*		*
1 1 1 - !					*	*
					!	!

Вибираємо мінімальну кількість простих імплікант, що поглинають усі конституенти одиниць у таблиці. Такими імплікантами є 0- -1 та 111-.

У результаті отримали .

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

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

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

Визначення 8. Правильною конфіґурацією для булевої функції від n-змінних називається прямокутна область на діаграмі Вейча, що поєднує 2^n-i однотипних клітинок.

Тоді мінімізація полягає у виборі мінімальної кількості правильних конфіґурацій за одиницями функції (для побудови МДНФ) або за нулями функції (для побудови МКНФ).

		1						0		0	0
		1	1	1				0
			1	1				0	0
								0	0	0	0

.