1. Мінімізація методом Квайна

Вихідною формою подання функції для мінімізації за методом Квайна є досконала диз'юнктивна нормальна форма (ДДНФ). Метод забезпечує одержання скороченої ДНФ (СДНФ), тобто сукупності всіх простих імплікант. Метод базується на використанні співвідношення неповного склеювання і співвідношення поглинання , де A і B - довільні кон'юнктивні терми, x - змінна.

Для мінімізації необхідно виконати такі етапи:

1. запис функції у початковій формі - ДДНФ;

2. застосування співвідношення склеювання послідовно до конституент одиниці, потім до імплікант n-1 рангу, n-2 рангу і так далі, поки можливе формування нових імплікант;

3. виконання всіх можливих поглинань, в результаті чого визначаються всі прості імпліканти;

4. побудова таблиці покриттів (імплікантної матриці) і знаходження тупикових ДНФ (ТДНФ);

5. вибір мінімальної ДНФ (МДНФ) з числа ТДНФ.

Виконаємо мінімізацію функції, заданої табл. 5.

Таблиця 5 – Параметри функції

x3	x2	x1	y
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

Функція у досконалій диз'юнктивній нормальній формі (ДДНФ) має вигляд

Виконавши попарне склеювання конституент одиниці, одержуємо множину імплікант 2-го рангу: . Подальше склеювання імплікант неможливе. Тоді функцію можна записати у вигляді:

Виконавши поглинання, одержуємо скорочену ДНФ:

Будуємо таблицю покриттів (табл. 6).

Таблиця 6 – Таблиця покриттів

	Конституенти
Імпліканти
	+		+
	+			+
		+	+
		+			+

Знаходимо ядро функції - сукупність імплікант відповідних однократно покритим конституентам.

В даному випадку ядро складають імпліканти і . Як правило, ядро варто доповнити ще декількома імплікантами, для одержання повного покриття всіх конституент вихідної функції. Різні варіанти покриття є тупиковими ДНФ. Серед ТДНФ форма з мінімальною ціною буде мінімальною ДНФ (МДНФ). Для розглянутої функції, існують дві рівноцінні ТДНФ:

та

Як МДНФ вибираємо, наприклад,

2. Мінімізація методом Квайна – Мак-Класкі

Приклад 1. Мінімізувати перемикальну функцію, задану у вигляді досконалої диз'юнктивної нормальної форми, методом Квайна – Мак-Класкі:

Етап 1: виписати двійкове представлення наборів, що утворюють ДДНФ даної функції:

(0011, 0111, 1000, 1010, 1011, 1100, 1111)

Етап 2: розбити отримані двійкові коди на групи, що містять однакову кількість одиниць у коді. Для ФАЛ, що залежать від n змінних, таких груп може бути n+1 (ні однієї одиниці в коді, одна одиниця, дві одиниці, ... , n одиниць у коді). Розташувати групи за зростанням кількості одиниць (табл.7). Якщо кількість груп, що вийшли, менше n+1, то відсутні групи позначити як порожні.

Таблиця 7 – Розташування груп за зростанням кількості одиниць

- - - -

1000

0011 1010 1100

0111 1011

1111

Е тап 3: порівняти кожен код з однієї групи з кожним кодом із сусідніх груп. Якщо знайдені два коди, що відрізняються тільки в одному розряді (тобто вони можуть "склеюватися" між собою згідно операції склеювання , то позначити ці коди яким-небудь особливим символом, наприклад "*", і в нову групу помістити код, що зберігає значення в співпадаючих розрядах і який-небудь особливий символ, що має, наприклад "-", на місці незбіжного розряду. При цьому утвориться n-1 нова група кодів. Якщо код попадає в декілька "склейок", то він символом * може позначатися тільки один раз.

Ця процедура повторюється для знову утворених груп доти, поки можлива процедура "склеювання" елементів сусідніх груп. Максимально можливе число кроків на цьому етапі дорівнює n. На всіх кроках, починаючи з другого, необхідно стежити за тим, щоб два "склеювані" коди являли собою терми, що залежать від одних і тих же логічних змінних, тобто знаки "-" у них повинні знаходитися в одних і тих же позиціях. З появою в одній групі декількох однакових імплікант для подальшого аналізу варто залишити лише одну з них, виходячи зі співвідношення .

Рис.1. Процес отримання первинних імплікант

Результат виконання даного етапу – одержання всіх первинних імплікант вихідної перемикальної функції, тобто скороченої диз'юнктивної нормальної форми. Первинними імплікантами будуть всі імпліканти, отримані на останньому кроці цього етапу, а також всі імпліканти, отримані на всіх попередніх кроках, які не ввійшли в жодну з "склейок", тобто, не позначені символом "*".

Етап 4: скласти імплікантну матрицю, що представляє собою таблицю, де по стовпцях розташовані конституенти одиниці вихідної функції, а по рядках - первинні імпліканти.

В клітинку таблиці ставиться який-небудь відповідний символ, наприклад "+", якщо первинна імпліканта, що розташована в заголовку рядка, є власною частиною конституенти одиниці, що розташована в заголовку стовпця (табл.8). У протилежному випадку клітинка залишається порожньою.

Таблиця 8 –Заповнення імплікантної матриці

Первинні імпліканти	Конституенти одиниці
	0011	0111	1000	1010	1011	1100	1111
--11	+	+			+		+
10-0			+	+
1-00			+			+
101-				+	+
-111		+					+

Найпростіший, але, звичайно, не повний, контроль правильності заповнення таблиці може бути проведений у такий спосіб. Якщо первинна імпліканта, що розташована в заголовку рядка, не містить символів "-", то в цьому рядку повинна бути рівно одна позначена клітинка. Рядок, що має в заголовку імпліканту з k символами "-", повинний містити рівно 2k позначених клітинок. Крім того, не повинно бути жодного стовпця, що не має хоча б однієї позначеної клітинки.

Етап 5: знайти суттєві імпліканти функції.

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

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

Для розглянутої функції суттєвими імплікантами будуть --11 і 1-00, тому що тільки первинна імпліканта --11 дозволяє покрити імпліканту 0011 вихідного набору, а первинна імпліканта 1-00 необхідна для покриття імпліканты 1100.

Імплікантна матриця після викреслювання з неї відповідних рядків і стовпців прийме наступний вигляд.

Таблиця 9 – Викреслювання рядків і стовпців з імплікантної матриці

Первинні імпліканти	Конституенти одиниці
	0011	0111	1000	1010	1011	1100	1111
--11	+	+			+		+
10-0			+	+
1 -00			+			+
101-				+	+
-111		+					+

Етап 6: знайти тупикові диз'юнктивні нормальні форми і вибрати з них мінімальні ДНФ.

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

Для аналізу після етапу 5 залишився тільки один стовпець. Його покриття може бути забезпечено включенням у тупикову форму або імпліканти 10-0, або 101-, що приводить до двох тупикових ДНФ. При наявності вибору в мінімальну форму включається імпліканта, що залежить від меншого числа змінних. Обидві отримані імпліканти залежать від трьох змінних, тому кожна з них може бути включена в мінімальну форму. При рівності рангів додатковим фактором для включення тієї чи іншої імпліканти в мінімальну форму іноді служить менше число змінних, які входять у імпліканту в інверсному вигляді, тому що це в ряді випадків дозволяє скоротити обсяг устаткування для апаратної реалізації отриманої функції. Ми у своєму розгляді даний параметр у критерій мінімальності включати не будемо.

Таким чином, розглянута функція має дві різні мінімальні диз'юнктивні форми:

з яких обирається одна.

Приклад 2. Мінімізувати ФАЛ, задану у вигляді досконалої кон’юнктивної нормальної форми, методом Квайна – Мак-Класкі:

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

Етап 1: записати двійкове представлення наборів, що утворюють ДКНФ даної функції:

(0000, 0111, 1010, 1011, 1101, 1110, 1111)

Етап 2: розбити отримані коди на групи, що містять однакову кількість нулів у коді. Для перемикальної функції, що залежать від n змінних, таких груп може бути n+1 (жодного нуля в коді, один нуль, два нулі, ... , n нулів у коді). Розташувати групи за зростанням кількості нулів (табл.10). Якщо кількість груп, що вийшли, менше n+1, то відсутні групи позначаються як порожні.

Таблиця 10 – Розташування груп за зростанням кількості нулів

1111

0111 1011 1101 1110

1010

- - - -

0000

Е тап 3: порівняти кожен код з однієї групи з кожним кодом із сусідніх груп. Якщо знайдені два коди, що відрізняються тільки в одному розряді (тобто вони можуть "склеюватися" між собою згідно , то позначити їх яким-небудь особливим символом, наприклад, "*", і в нову групу помістити код, що зберігає значення в співпадаючих розрядах і який-небудь особливий символ, що має, наприклад "-", на місці незбіжного розряду. При цьому утвориться n-1 нова група кодів.

Ця процедура повторюється для знову утворених груп доти, поки можлива процедура "склеювання " елементів сусідніх груп. Максимально можливе число кроків на цьому етапі дорівнює n. На всіх кроках, починаючи з другого, необхідно стежити за тим, щоб два "склеюваних" коди являли собою терми, що залежать одних і тих же логічних змінних, тобто знаки "-" у них повинні знаходитися в одних і тих же позиціях (рис.2). З появою в одній групі декількох однакових термів для подальшого аналізу варто залишити лише один з них, виходячи зі співвідношення .

Рис.2. Процес отримання первинних імпліцент

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

Етап 4: скласти імпліцентну матрицю, яка представляє собою таблицю, що в якості заголовків стовпців має всі конституенти нуля вихідної функції, а як заголовки рядків - первинні імпліценти.

В клітинку таблиці ставиться який-небудь відповідний символ, наприклад "+", якщо первинна імпліцента, що розташована в заголовку рядка, є власною частиною конституенти нуля, що розташована в заголовку стовпця. У протилежному випадку клітинка залишається порожньою:

Таблиця 11 – Викреслювання рядків і стовпців з імпліцентної матриці

Первинні імпліценти	Конституенти нуля
	0000	0111	1010	1011	1101	1110	1111
1-1-			+	+		+	+
-111		+					+
11-1					+		+
0000	+

Найпростіший контроль правильності заповнення таблиці може бути проведений аналогічно прикладу 1.

Етап 5: знайти суттєві імпліценти.

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

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

Для розглянутої функції всі мінтерми, що містяться в заголовках рядків, будуть суттєвими, тому що первинна імпліцента 1-1- необхідна для покриття макстермів 1010, 1011, 1110 і 111 вихідного набору, імпліцента -111 – для покриття макстерма 0111, імпліцента 11-1 – для покриття макстерма 1101, а імпліцента 0000 необхідна для покриття такого ж макстерму у вихідному наборі.

Таким чином, одержимо єдиний набір, що покриває всі макстерми, які складають досконалу кон’юнктивну нормальну форму заданої функції. У зв'язку з цим відсутній етап, аналогічний етапу 6 у прикладі 1.

Отримана єдина мінімальна кон’юнктивна нормальна форма має наступний вигляд: