Тема. Мінімізація булевих функцій.
Лекція 6. Проблема мінімізації. Породження простих импликантами. Алгоритм Куайна і Мак-Клоскі Проблема мінімізації
Визначення. ДНФ # 106; функції f називається
а) мінімальної (мінімальної по ЛІТЕРАЛЬ), якщо вона має найменше число символів змінних серед інших ДНФ функції f;
в) найкоротшою (мінімальної по сполучення), якщо вона має мінімальне число елементарних кон'юнкція.
Число різних елементарних кон'юнкція від n змінних дорівнює 3 n. тому будь-яка змінна може або входити в кон'юнкцію, або не входити, або входити з запереченням. Тоді ДНФ від n змінних однозначно визначається вектором довжини 3 n. що складається з нулів і одиниць, де 1 означає, що відповідна елементарна кон'юнкція входить в ДНФ, а 0 - не входить. Тому число всіх ДНФ від "n" змінних одно.
Для довільної функції алгебри логіки можна написати багато ДНФ. Проблема мінімізації полягає в тому, щоб для функції f побудувати мінімальну ДНФ в певному вище сенсі. Ця проблема допускає тривіальне рішення, що полягає в переборі всіх ДНФ, але очевидно, що таке рішення є надзвичайно трудомістким навіть при невеликих значеннях n.
Визначення. Формула # 89; тягне формулу # 70; (позначення
# 89; # 70; ). якщо ( # 89; # 70; ) º 1. тобто не існує такого набору значень змінних, при якому # 121; приймає значення 1. а # 70; - значення 0.
Визначення. Елементарна кон'юнкція K називається импликантами функції f. якщо K f.
Приклад 6.1.
Нехай і нехай K = x = x 1 y 0. К = 1 # 219; x = 1, y = 0. Оскільки f (1,0, z) = 1 × 1 × z # 218; 1 × 1 × = z # 218; º 1. то К = x є импликантами функції f.
Нехай f (x, y, z, t) = x z # 218; x t і нехай K = x = x 1 y 0. К = 1 # 219; x = 1, y = 0. Оскільки f (1,0, z, t) = z # 218; t 1. тому що якщо z = 0 і t = 0. то z # 218; t = 0, тобто К = x не є импликантами f.
Теорема 6.1. якщо формула # 70 ;. реалізує функцію f. має вигляд, - ДНФ, то.
Доведення. Нехай в ДНФ функції ki = 1. Тоді і, отже, f = 1.
Визначення. Импликант P функції f називається простим. якщо при видаленні будь-якої змінної з P отримана елементарна кон'юнкція не є импликантами.
У прикладі 6.1. - простий импликант, тому що ні x ні импликантами не є.
Теорема 6.2. Кожна функція подана в вигляді, де Pi - прості імпліканти.
Доведення. Потрібно показати, що f = 1 тоді і тільки тоді, коли. Очевидно, що якщо, то f = 1.
Нехай тепер для деякого набору значень змінних. В цьому випадку, а з теореми 6.1. випливає, що ki - импликант. Скорочуємо цей импликант до простого. Дану процедуру повторюємо для всіх наборів значень змінних, для яких f = 1.
Визначення. ДНФ функції f називають неізбиточной якщо:
Очевидно, що мінімальна ДНФ є неізбиточной. Тому мінімальні ДНФ слід шукати серед ненадлишкових. Таким чином завдання мінімізації може бути розділена на наступні етапи:
1) знаходження всіх простих импликант функції f;
2) знаходження ненадлишкових ДНФ функції f;
3) вибір мінімальних ДНФ функції f.
Породження простих импликантами
Визначення. елементарна кон'юнкція # 97; покривається елементарної кон'юнкція # 98 ;. якщо кожна змінна, що входить в # 98 ;. входить в # 97; (З урахуванням заперечення).
Приклад 6.2.
кон'юнкція # 97; = Xyz покривається кон'юнкція # 98; = Xy.
кон'юнкція # 97; = X z не покривається кон'юнкція # 98; = X.
Визначення. елементарна кон'юнкція # 97; називається доповненням елементарної кон'юнкції # 98; по відношенню до ДНФ # 70; . якщо:
Приклад 6.3.
нехай # 70; = xy # 218; # 218; zt # 218; . тоді кон'юнкції # 97; 1 = xyzt. # 97; 2 = xyz, # 97; 3 = xy t, # 97; 4 = xy є доповненнями кон'юнкції # 98; = Xy по відношенню до # 70; .
Теорема 6.3. нехай # 70; - СДНФ функції f. якщо # 98; - импликант f. то всі додатки елементарної кон'юнкції # 98; по відношенню до # 70; входять в # 70; .
Доведення. Нехай - импликант функції f і нехай є доповненням # 98; по відношенню до # 70 ;. Припустимо, що # 97; не входить в # 70 ;. Розглянемо такий набір значень змінних, що # 97; = 1. тобто покладемо xi = # 100; i. i = 1, ..., n. тоді і # 98; = 1. а # 70; = 0 оскільки # 97; за припущенням не входить в # 70 ;. Але це суперечить тому, що # 98; импликантой f.
З теореми випливає, що об'єднуючи в СДНФ # 70; функції f відповідним чином пари елементарних кон'юнкція і застосовуючи послідовно рівність, можна в результаті отримати всі прості імпліканти функції f.
Приклад 6.4.
Нехай f = xyzt # 218; x # 218; x zt.
Перша і третя кон'юнкції дають xyzt # 218; x zt = xzt. Друга і третя кон'юнкції даютx z # 218; x zt = x z. Отримані вирази є простими імплікантаім і, отже, f = xzt # 218; x z.
Алгоритм Куайна і Мак-Клоскі (перерахування простих импликантами)
Систематизуємо викладену вище ідею.
1) випишемо для функції f СДНФ # 70; .
2) У кожній елементарної кон'юнкції всі змінні будемо записувати в однаковому порядку.
3) Кожну елементарну кон'юнкцію представимо у вигляді послідовності з 1. 0 і -. ставлячи на i-му місці 1. якщо i -я змінна входить в кон'юнкцію без заперечення, 0 - якщо з запереченням і -. якщо не входить.
Наприклад, xyz # 218; x # 218; x запишемо у вигляді 111- # 218; 1-0- # 218; 1 -0.
4) Утворити з елементарних кон'юнкція групи, включаючи в одну групу набори з однаковим числом одиниць (групи, в яких число одиниць відрізняється на 1. називається сусідніми); розташуємо групи в порядку зростання числа одиниць.
Наприклад, для функції
елементарні кон'юнкції представляються як 1101, 1001, 1100, 1000, 0010, 0001 у 0000 а список груп буде наступним:
5) Рівність не можна вживати тільки до відповідних парам наборів із сусідніх груп. Відповідна пара утворюється двома наборами, що відрізняються в одній позиції, і в цій позиції не варто риска. Відповідні пари будемо відзначати зірочками (*).
6) Ставимо в различающейся позиції підходящої пари риску і поміщаємо вийшов набір в наступний список груп.
7) Повторюємо описаний процес, поки це можливо. Непомічені набори утворюють прості імпліканти.
У розглянутому прикладі кроки 6 і 7 виглядають наступним чином.