1. 6. 3. Метод мінімізації Квайна – Мак-Класкі.

Даний метод представляє собою формалізований на етапі пошуку простих імплікант метод Квайна. Суть формалізації полягає у наступному:

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

2. Всі номери розбиваються на групи, що не перетинаються. Ознакою утворення -ї групи являється наявність одиниць в кожному двійковому номері конституенти одиниці.

3. Склеювання виконують тільки між номерами сусідніх груп. Склеювані номери позначаються яким-небудь знаком (наприклад, закреслюванням).

4. Склеювання виконують всі можливі, як і в методі Квайна. Непозначені після склеювання номери являються простими імплікантами.

Пошук мінімальних ДНФ далі здійснюється по імплікантній матриці, як і в методі Квайна.

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

.

1. В ДДНФ функції замінимо всі конституенти одиниці їх двійковими номерами:

.

2. Утворюємо групи двійкових номерів, Ознакою утворення -ї являється наявність одиниць в двійковому номері конституенти одиниці.

В даному випадку всі номери функції упорядковуються у чотири групи:

- перша група містить номери з однією одиницею - - ;

- друга група містить номери з двома одиницями

- -, - - ;

- третя група містить номери з трьома одиницями

- -, - - ;

- четверта група містить номери з чотирма одиницями - -.

3. Виконуємо всі можливі склеювання між номерами цих груп. Номери, що склеюються, позначимо значком „ - -„.

Запишемо результати склеювання. При цьому в двійкових номерах простих імплікант поставимо зірочки на позиціях, по яких відбувалося склеювання: 00*1, 0*01, 0*11, 01*1, *111, 111*.

Перша проста імпліканта одержана в результаті склеювання номерів 0001 і 0011, друга – номерів 0001 і 0101, третя – номерів 0011 і 0111, четверта – номерів 0101 і 0111, п’ята – номерів 0111 і 1111, шоста – номерів 1110 і 1111.

Утворюємо групи із результатів склеювання, тобто із двійкових номерів імплікант. Одержимо три групи:

- перша група містить номери імплікант з однією одиницею

- 00*1- , - 0*01- ;

- друга група містить номери імплікант з двома одиницями

- 0*11- , - 01*1- ;

- третя група містить номери імплікант з трьома одиницями

*111, 111*.

Склеюємо номери імплікант із сусідніх груп. При цьому склеюватися можуть тільки номери, що мають зірочки в однакових позиціях. Склеювані номери позначимо значком „- -„. Результатом склеювання являється імпліканта 0**1.

4. Маємо три прості імпліканти: *111, 111*, 0**1.

5. Будуємо імплікантну матрицю (табл. 1. 14. По таблиці визначаємо сукупність простих імплікант – 0**1 і 111*, що відповідає мінімальній ДНФ.

Таблиця 1. 14

Двійкові номери простих імплікант	Двійкові номери конституент одиниці
	0001	0011	0101	0111	1110	1111
0 * * 1	+	+	+	+
* 1 1 1				+		+
1 1 1 *					+	+

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

0 ** 1 ; 1 1 1 * .

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