5. Карти Карно

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

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

6. Мінімізація булевої функції картами Карно

Для знаходження мінімальної ДНФ покриємо всі одиниці карти Карно прямокутниками. В результаті отримали два прямокутника 24 та два прямокутника 14.

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

Результатом мінімізації є функція

.

Складність мінімальної ДНФ .

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

Виписуємо всі терми, в яких функція приймає значення 1. Нумерація змінних в термах – зліва-направо, тобто буде записано як 1101.

0000, 1000, 0100, 1100, 1010, 0110, 0001, 1001, 0101, 1101, 0011, 1011, 0111, 1111.

Далі класифікуємо терми за кількість одиниць.

0) 0000₁

1) 1000₂, 0100₃, 0001₄

2) 1100₅, 1010₆, 0110₇, 1001₈, 0101₉, 0011₁₀

3) 1101₁₁, 1011₁₂, 0111₁₃

4) 1111₁₄.

Проводимо попарне склеювання.

0) –000_(1-2), 0–00_(1-3), 000–_(1-4)

1) 1–00_(2-5), 10–0_(2-6), 100–_(2-8), –100_(3-5), 01–0_(3-7), 010–_(3-9), –001_(4-8), 0–01_(4-9), 00–1_(4-10)

2) 110–_(5-11), 1–01_(8-11), –101_(9-11), 101–_(6-12), 011–_(7-13), 10–1_(8-11), 01–1_(9-13), –011_(10-12),

0–11_(10-13)

3) 11–1_(11-14), 1–11_(12-14), –111_(13-14)

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

1	2	3	4	5	6	7	8	9	10	11	12	13	14
+	+	+	+	+	+	+	+	+	+	+	+	+	+

Всі терми участували в склеюваннях. В результат нічого не включається.

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

0) –000₁, 0–00₂, 000–₃

1) 1–00₄, 10–0₅, 100–₆, –100₇, 01–0₈, 010–₉, –001₁₀, 0–01₁₁, 00–1₁₂

2) 110–₁₃, 1–01₁₄, –101₁₅, 101–₁₆, 011–₁₇, 10–1₁₈, 01–1₁₉, –011₂₀, 0–11₂₁

3) 11–1₂₂, 1–11₂₃, –111₂₄

Проводимо попарне склеювання.

0) – –00_(1-7), –00–_(1-10),– –00_(2-4),0–0–_(2-11),–00–_(3-6),0–0–_(3-9)

(терми, що повторюються, тобто непотрібні, виділено кольором)

1) 1–0–_(4-14),1–0–_(6-13),10– –_(6-16),10– –_(5-19),–10–_(7-15),–10–_(9-13),01– –_(8-18),01– –_(9-17),– –01_(10-15),– –01_(11-14),0– –1_(11-19),0– –1_(12-19), –0–1_(10-20),–0–1_(12-18)

2) 1– –1_(14-21),1– –1_(18-20), – –11_(19-22),– –11_(21-23),–1–1_(19-22),–1–1_(15-24)

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

1	2	3	4	5	6	7	8	9	10	11	12	13	14
+	+	+	+	+	+	+	+	+	+	+	+	+	+

15	16	17	18	19	20	21	22	23	24
+	+	+	+	+	+	+	+	+	+

Всі терми участували в склеюваннях. В результат нічого не включається.

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

0) – –00₁, –00–₂, 0–0–₃

1) 1–0–₄, 10– –₅, –10–₆, 01– –₇, – –01₈, 0– –1₉, –0–1₁₀

2) 1– –1₁₁, –1–1₁₂, – –11₁₃

Проводимо попарне склеювання.

0) – –0–_(1-8),– –0–_(2-6),– –0–_(3-4)

(терми, що повторюються, тобто непотрібні, виділено кольором)

1) – – –1_(9-10),– – –1_(10-12),– – –1_(13-18)

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

1	2	3	4	5	6	7	8	9	10	11	12
+	+	+	+		+		+	+	+	+	+

Терми 5 і 7 у склеюваннях не приймали участь. Вони відразу записуються до результату. Подальші склеювання неможливі. Отже, тупикова ДНФ матиме такий вигляд