8.5.4. Властивості скороченої днф

Скорочена ДНФ має деякі важливі властивості.

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

Доведення. До ДНФ f, яка не має жодної букви одночасно із запереченням і без заперечення, не можна застосувати рівносильність узагальненого склеювання. Це саме стосується диз'юнкції довільної кількості членів цієї форми. Якщоf- скорочена ДНФ, то їїможна відновити за допомогою узагальненого склеювання з мінімальної ДНФ, яка складає деяку частинуf.Отже, у цьому випадку мінімальна ДНФ збігається із скороченою ДНФ. ▲

Теорема 8.30. Скорочена ДНФ монотонної функції fне має заперечень змінних.

Доведення. Нехайk_р- проста імпліканта функціїf, що має заперечення змінних. Позначимо к кон'юнкцію всіх змінних, які входять вk_р без заперечень. Побудуємо набір значеньзмінних так: усім змінним, які входять вk, припишемо значення 1, арешті змінним - значення 0. Цілком очевидно, що імпліканта k_p,а,отже, і функція fперетворюються на цьому наборі в 1. З іншого боку, кон'юнкція kперетворюється в 1 лише на наборах (зокрема, і на наборі ).Але на всіх таких наборах функціяf, за визначенням монотонності, також дорівнює 1.Отже,k-імплікантафункціїf, а імплікантаk_р-не проста. Суперечність. ▲

Наслідок. Скорочена ДНФ монотонної функції є одночасно ймінімальною ДНФ цієї функції. ▲

8.5.5.Метод карт Карно побудови мінімальних днф

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

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

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

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

. Нарис. 8.2 зображено комірки, які відповідають конституентам одиниці функції f, а на рис. 8.3 - заповнену карту.▲

Рис.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

Цифри	w x y z	F(x, y, z)
0 1 2 3 4 5 6 7 8 9	0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1	0 0 0 0 0 1 1 1 1 1

Рис.8.8