Метод карт Карно побудови мінімальних ДНФ

Для знаходження мінімальних ДНФ функцій невеликої кількостізмінних (не більше шести) можна використати метод карт Карно. Цейвізуальний метод був запропонований 1953 р. Карно (М. Karnaugh). Він ґрунтується на опублікованій дещо раніше роботі Вейча (Е. Veitch). Метод картКарно розглянемо для функцій трьох і чотирьох змінних.Карта Карно для функції трьох змінних складається з 2³=8 комірок.

Кожному з наборів значень аргу­ментів відповідає одна комірка. Кожна комірка зображає відповід­ну конституенту одиниці (рис. 8.1).

Якщо на певному наборі значень аргументів функція дорівнює 1, то у відповідній комірці запи­сують 1.

Приклад 8.28. Побудуємо кар­ту Карно для функції

Рис.8.2 Рис.8.3

Рівносильність склеювання можна застосувати лише до конституент (у загальному випадку до елементарних кон'юнкцій) зі змінними, у яких всі степені, за виключенням однієї, збігаються. Наприклад, можна склеїти, бо степені х таzзбігаються (х¹ та z ⁰), а степені змінної у різні. Такі конституенти називають сусідніми.

Уважають, що в карті Карно для трьох змінних ліва й права сторони тотожні (карта згорнута у циліндр). Тоді всі сусідні консти­туенти мають на карті сусідні комірки. Блоку з двох сусідніх комірок відповідає елементарна кон'юнкція, яка є спільною частиною двох конституент і містить на одну букву менше. Прямокутному блоку зчотирьох сусідніх комірок відповідає елементарна кон'юнкція, яка є спільною частиною відповідних чотирьох конституент і містить на дві букви менше. Тому на карті Карно можна об'єднувати прямо­кутні блоки, які містять сусідні дві, чотири, або (у загальному випадку) 2 ⁱ одиниць.

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

Приклад 8.28 (закінчення). На рис. 8.3 зображено покриття одиниць карти Карно блоками. Одержуємо мінімальну ДНФ . ▲

Приклад 8.29.Розглянемо функцію

Карту Карно для цієї функції зображено на рис. 8.4. Блоку з чоти­рьох одиниць відповідає елементарна кон'юнкція y рангу 1, а блоку з двох одиниць - елементарна кон'юнкція рангу2. Отже, . ▲

Рис. 8.4 Рис. 8.5

Приклад 8.30. Карту Карно для функції

зображено на рис. 8.5. Мінімальна ДНФ цієї функції

.▲

На рис. 8.6 зображено карту Карно для функції чотирьох змінних w, х, у, z. У карті Карно для чотирьох змінних ототожнюють ліву й праву, а також верхню й нижню сторони.

Приклад 8.31. Знайти мінімальну ДНФ для функції

.

Карту Карно для функціїf(w, x, y, z)зображено на рис. 8.7. Отже, . Зазначимо, що в цьому прикладі мож­ливий і інший варіант форму­вання блоків, що призведе до іншої мінімальної ДНФ. ▲

У деяких випадках дово­диться працювати з булевими функціями, визначеними не для всіх наборів значень аргументів. Тоді в карті Карно використову­ють позначкуdдля тих комірок, які відповідають наборам з невизначеним значенням буле­вої функції (на цих наборах функція Рис.8.7

може бути довизначена

довільно). У разі формування найбільших блоків можна вважати, що у деяких (або у всіх) комірках з буквоюdмістяться одиниці.

Приклад 8.32. Задамо булеву функцію чотирьох змінних, визначену на наборах, які відповідають двійковому коду десяткових цифр 0, 1, 2,..., 9, мінімальною ДНФ. Значення функції дорівнює 1, якщо набір відповідає цифрам, більшим або рівним 5, і дорівнює 0, якщо мен­шим 5. Шукану функцію f (w, x, y, z)задано табл. 8.9. Відповідну карту Карно зображено на рис. 8.8. Отже, f (w, x, y, z)=w∨ xy∨ xz. ▲

Таблиця 8.9

Рис.8.8