Метод Квайна-Маккласкі

У 1956 р. Маккласкі запропонував модернізацію першого етапу методу Квайна. Якщо записати мінтерми у вигляді їхніх двійкових номерів, то всі номери можна розбити за числом одиниць у цих номерах на групи, що не будуть перетинатися. При цьому в і-ту групу ввійдуть всі номери, що мають у своєму двійковому запису і одиниць. Попарно порівнювати можна тільки сусідні за номером групи, оскільки саме вони різні для тих мінтермів, що входять у них, у одному розряді. При створенні мінтермів з рангом, вищим від нульового, в розряди, які відповідають вилученим змінним, записують знак „тире”. Така модифікація на практиці дуже зручна, оскільки дає змогу уникнути виписування громіздких мінтермів та імплікант, замінивши виписуванням їхніх двійкових номерів.

Приклад. Функцію в ДДНФ задано мінтермами з номерами 0, 1, 2, 3, 4, 7, 8, 9, 11, 15. Записати ці мінтерми по групах у двійковому коді.

Розв’язання.

Нульова група: 0000.

Перша група: 0001, 0010, 0100, 1000.

Друга група: 0011, 0110, 1001, 0101, 1100, 1010.

Третя група: 0111, 1011, 1101, 1110.

Четверта група: 1111.

Порівнюючи сусідні групи, визначаємо по групах мінтерми першого рангу:

Нульова група: 000–, 00–0, 0–00, –000.

Перша група: 00–1, –010, 010–, 0–10, 01–0, 100–.

Друга група: 0–11, –011, 011–, 10–1.

Третя група: –111, 1–11.

Тепер знаходимо мінтерми другого рангу:

Нульова група: 00– –, –00–, 0– –0.

Перша група: –0–1, 0–1–.

Друга група: – –11.

Складаємо таблицю міток:

	0000	0001	0010	0011	0100	0110	0111	1000	1001	1011	1111
00– –				
–00–									
0– –0						
–0–1										
0–1–							
– –11											

Подальша мінімізація за методом Маккласкі збігається з мінімізацією за методом Квайна. Для ДНФ, що розглядається, мінімальна форма має такий вигляд

f(x₁, x₂, x₃, x₄) = + + x₃x₄.

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

Алгоритм утворення мінімальної ДНФ зводиться до виконання таких трьох дій:

1. Перемикальну функцію подають у ДДНФ.

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

3. Знаходять мінімальні ДНФ за імплікантною матрицею.

Розглянемо метод імплікантних матриць на прикладах.

Приклад 1. Знайти мінімальну ДНФ, якщо ДДНФ має вигляд

f(a, b, c, d) = bcd + cd + a cd + a d + a + .

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

Для кожної імпліканти знаходимо конституенти одиниці, що пог­линаються, тобто ті конституенти, власною частиною яких є задана ім­плі­канта. Наприклад, сd поглинає дві конституенти: bcd й cd. Клі­­тинки імплікантної матриці, утворені перетином рядків з ім­плікантами і колонок із поглинанням, будемо позначати хрестиком ().

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

№ п/п	Прості імпліканти	Конституенти одиниці
		bcd	cd	a cd	a d	a
		1	2	3	4	5	6
1	cd		
2	cd			
3	a d				
4	a					
5							

cd накриває 1 і 2; a d накриває 3 та 4; накриває 5 і 6. Тому форма f = cd + a d + є тупиковою. Вона ж є і мінімальною.

Приклад 2. Знайти мінімальну ДНФ, якщо ДДНФ має вигляд

f(a, b, c) = bc + c + abc + ab + a + .

(1) (2) (3) (4) (5) (6)

Розв’язання. Виконавши всі операції склеювання та поглинання, дістанемо:

1 – 2 = c (по b); 1 – 3 = bc (по a);

2 – 6 = (по c); 3 – 4 = ab (по c);

4 – 5 = a (по b); 5 – 6 = (по a).

Отже, f(a, b, c) = c + bc + + a + + ab – скорочена ДНФ.

Складемо імплікантну матрицю.

№ п/п	Прості імпліканти	Конституенти одиниці
		bc	c	abc	ab	a
		1	2	3	4	5	6
1	c		
2	bc			
3			
4	ab				
5	a					
6							

З неї випливає, що:

– перша тупикова ДНФ f(a, b, c) = c + ab + ;

– друга тупикова ДНФ f(a, b, c) = bc + + a + .

Отже, перша тупикова ДНФ є мінімальною.