Частина 2. Методичні вказівки щодо використання функцій алгебри логіки та мінімізації цих функцій у базисі Буля
2.1 Функціональна повнота системи функцій алгебри логіки і наборів логічних елементів
Основна вимога, яка ставиться до набору логічних елементів, полягає в тому, щоб за допомогою цього набору можна було побудувати будь-яку логічну схему. З огляду на те, що функціонування елементів однозначно описується функціями алгебри логіки (ФАЛ), застосовуючи операцію суперпозиції, можна з деякої системи ФАЛ отримати будь-яку, скільки завгодно складну ФАЛ. Тоді ця деяка система ФАЛ буде називатися функціонально повною (ФПС ФАЛ).
Функціонально повним є такий набір ФАЛ, який містить хоча б одну функцію, яка:
не зберігає константу "0";
не зберігає константу "1";
не є монотонною;
не є самодвоїстою;
не є лінійною.
Якщо функція F на нульовому наборі змінних дорівнює 0, тобто F(0,0,...,0)=0, то ця функція зберігає константу "0".
Таблиця 2.1.1 ---T----T----------------T--------------T---------¬ ¦х0 ¦0011¦Назва ФАЛ ¦ Вираз ФАЛ ¦ Клас ¦ ¦х1 ¦0101¦ ¦ +-T-T-T-T-+ ¦ ¦ ¦ ¦ ¦0¦1¦Л¦М¦С¦ +--+----+----------------+--------------+-+-+-+-+-+ ¦F0 ¦0000¦константа "0" ¦0 ¦X¦ ¦X¦X¦ ¦ ¦F1 ¦0001¦кон'юнкція, І ¦х0·х1 ¦X¦Х¦ ¦X¦ ¦ ¦F2 ¦0010¦заборона по х1 ¦х0·/х1 ¦X¦ ¦ ¦ ¦ ¦ ¦F3 ¦0011¦х0 ¦х0 ¦X¦Х¦Х¦Х¦Х¦ ¦F4 ¦0100¦заборона по х0 ¦/х0·х1 ¦X¦ ¦ ¦ ¦ ¦ ¦F5 ¦0101¦х1 ¦х1 ¦X¦Х¦Х¦Х¦Х¦ ¦F6 ¦0110¦сума за mod 2 ¦х0·/х1 v /х0·х1¦X¦ ¦Х¦ ¦ ¦ ¦F7 ¦0111¦диз'юнкція, АБО ¦х0 v х1 ¦X¦Х¦ ¦Х¦ ¦ ¦F8 ¦1000¦АБО-НЕ (Пірса) ¦/(х0 v х1) ¦ ¦ ¦ ¦ ¦ ¦ ¦F9 ¦1001¦рівнозначність ¦х0·х1 v /х0·/х1¦ ¦Х¦Х¦ ¦ ¦ ¦F10¦1010¦інверсія х1 ¦/х1 ¦ ¦ ¦Х¦ ¦Х¦ ¦F11¦1011¦імплікація звор.¦х0 v /х1 ¦ ¦Х¦ ¦ ¦ ¦ ¦F12¦1100¦інверсія х0 ¦/х0 ¦ ¦ ¦Х¦ ¦Х¦ ¦F13¦1101¦імплікація пряма¦/х0 v х1 ¦ ¦Х¦ ¦ ¦ ¦ ¦F14¦1110¦І-НЕ (Шефера) ¦/(х0·х1) ¦ ¦ ¦ ¦ ¦ ¦ ¦F15¦1111¦константа "1" ¦1 ¦ ¦Х¦Х¦Х¦ ¦ L--+----+----------------+--------------+-+-+-+-+-- Якщо функція F на одиничному наборі змінних дорівнює 1, тобто F(1,1,...,1)=1, то ця функція зберігає константу "1".
ФАЛ називається монотонною, якщо при будь-якому зростанні кількості "1" у послідовності сусідніх (тобто таких, які відрізняються тільки в одному розряді) наборів змінних (х0,х1,...,xn) значення функції не зменшується.
ФАЛ називається самодвоїстою, якщо на кожній парі протилежних наборів (x0,x1,...,xn) та (/x0,/x1,...,/xn) вона приймає протилежні значення, тобто, якщо виконується умова F(x0,x1,...,xn) = /F(/x0,/x1,...,/xn), де знаком "/" позначена операція інверсії.
ФАЛ називається лінійною, якщо її можна зобразити поліномом Жегалкіна без добутків змінних
F(x0,x1,...,xn) = a0·x0 # a1·x1 # ... # an·xn,
де ai = (0, 1);
· - позначення операції І;
Таблиця 2.1.2 ----T-¬ ¦abc¦f¦ +---+-+ ¦000¦1¦ ¦001¦0¦ ¦010¦1¦ ¦011¦1¦ ¦100¦0¦ ¦101¦0¦ ¦110¦1¦ ¦111¦0¦ L---+-- # - позначення операції "додавання за модулем 2".
Для того щоб записати функцію, яка задана таблично, у вигляді полінома Жегалкіна, досить записати цю функцію у вигляді суми за модулем 2 тих наборів аргументів, на яких функція дорівнює 1. Після цього потрібно всі змінні, які входять до отриманого виразу з інверсіями, замінити за допомогою співвідношення /х = х # 1, розкрити дужки і звести подібні члени за допомогою тотожності
х # х # ... # х = х, якщо кількість х непарна;
х # х # ... # х = 0, якщо кількість х парна.
У табл. 2.1.1 наведені функції двох змінних і вказаний клас кожної ФАЛ. У графі "Клас" позначено:
0 - зберігає константу "0";
1 - зберігає константу "1";
Л - лінійна;
М - монотонна;
С - самодвоїста.
Приклад 2.1.1. Перевірити, чи створює функція трьох змінних, яка задана табл. 2.1.2, функціонально повну систему.
1) Оскільки на нульовому наборі f(0,0,0) = 1, то ця функція не зберігає константу "0".
2) Оскільки на одиничному наборі f(1,1,1) = 0, то ця функція не зберігає константу "1".
3) Послідовності сусідніх наборів подані в табл. 2.1.3 а, б, в, г, д, е.
Оскільки на всіх шести послідовностях сусідніх наборів функція не є монотонною (а досить було б і на одному), то функція не є монотонною взагалі.
4) Пари протилежних наборів наведені в табл. 2.1.4.
Оскільки на кожній парі протилежних наборів функція приймає протилежні значення, то функція є самодвоїстою.
5) Для визначення лінійності функції подамо її у вигляді полінома Жегалкіна
F = /a·/b·/c # /a·b·/c # /a·bc # ab·/c =
=(1#a)(1#b)(1#c) # (1#a)b(1#c) # (1#a)bc # ab(1#c) =
=(1#a)(1#b#c#bc) # b(1#a#c#ac) # (bc # abc) # (ab # abc) =
=(1 # b # c # bc # a # ab # ac # abc) # (b # ab # bc # abc) # (bc #
Таблиця 2.1.3 ----T-¬----T-¬----T-¬----T-¬----T-¬----T-¬ ¦abc¦f¦¦abc¦f¦¦abc¦f¦¦abc¦f¦¦abc¦f¦¦abc¦f¦ +---+-++---+-++---+-++---+-++---+-++---+-+ ¦000¦1¦¦000¦1¦¦000¦1¦¦000¦1¦¦000¦1¦¦000¦1¦ ¦001¦0¦¦001¦0¦¦010¦1¦¦010¦1¦¦100¦0¦¦100¦0¦ ¦011¦1¦¦101¦0¦¦011¦1¦¦110¦1¦¦101¦0¦¦110¦1¦ ¦111¦0¦¦111¦0¦¦111¦0¦¦111¦0¦¦111¦0¦¦111¦0¦ L---+--L---+--L---+--L---+--L---+--L---+-- а б в г д е
# abc) # (ab # abc) =
= 1 # ( = 1)
# a # ( = a)
# b # b # ( = 0)
# c # ( = c)
# ab # ab # ab # ( = ab)
# ac # ( = ac)
# bc # bc # bc # ( = bc)
# abc # abc # abc # abc = ( = 0)
= 1 # a # c # ab # ac # bc.
Таблиця 2.1.4 ------T---T-----T---¬ ¦ abc ¦ f ¦ abc ¦ f ¦ +-----+---+-----+---+ ¦ 000 ¦ 1 ¦ 111 ¦ 0 ¦ ¦ 001 ¦ 0 ¦ 110 ¦ 1 ¦ ¦ 010 ¦ 1 ¦ 101 ¦ 0 ¦ ¦ 011 ¦ 1 ¦ 100 ¦ 0 ¦ L-----+---+-----+----
Оскільки поліном містить добутки змінних, то функція не є лінійною. Отже, із п'яти необхідних для створення ФПС властивостей відсутня одна - несамодвоїстість, тому дана функція не утворює ФПС.
2.2. Мінімізація функцій методом Квайна-МакКласкі-Петрика
Метод складається з двох частин.
1. Побудова простих імплікант.
Логічна функція g(a,b,...,x) називається імплікантою логічної функції f(a,b,...,x), якщо
f(a,b,...,x) & g(a,b,...,x) = g(a,b,...,x).
Таблиця Таблиця 2.2.2 2.2.1 ----------T--------------T----------¬ -----T-¬¦ I ¦ II ¦ III ¦ ¦abcd¦f¦+----T--T-+----T----T--T-+----T-----+ +----+-+¦ К ¦П ¦У¦ С ¦ К ¦П ¦У¦ С ¦ К ¦ ¦0000¦1¦+----+--+-+----+----+--+-+----+-----+ ¦0001¦1¦¦0000¦a0 ¦+¦a0b0 ¦000-¦e0 ¦+¦e0f3 ¦-00-¦ ¦0010¦0¦+----+--+-+a0b1 ¦0-00¦e1 ¦+¦e1f5 ¦--00¦ ¦0011¦1¦¦0001¦b0 ¦+¦a0b2 ¦-000¦e2 ¦+¦e2f4 ¦--00¦ ¦0100¦1¦¦0100¦b1 ¦++----+----+--+-+e2f2 ¦-00-¦ ¦0101¦0¦¦1000¦b2 ¦+¦b0c0 ¦00-1¦f0 ¦+¦ ¦ ¦ ¦0110¦1¦+----+--+-+b1c1 ¦01-0¦f1 ¦ ¦ ¦ ¦ ¦0111¦0¦¦0011¦c0 ¦+¦b0c2 ¦-001¦f2 ¦++----+----+ ¦1000¦1¦¦0110¦c1 ¦+¦b2c2 ¦100-¦f3 ¦+¦ ¦ ¦ ¦1001¦1¦¦1001¦c2 ¦+¦b1c3 ¦-100¦f4 ¦+¦ ¦ ¦ ¦1010¦0¦¦1100¦c3 ¦+¦b2c3 ¦1-00¦f5 ¦+¦ ¦ ¦ ¦1011¦1¦+----+--+-+----+----+--+-+f2g0 ¦-0-1¦ ¦1100¦1¦¦1011¦d0 ¦+¦c0d0 ¦-011¦g0 ¦+¦f0g1 ¦-0-1¦ ¦1101¦1¦¦1101¦d1 ¦+¦c2d0 ¦10-1¦g1 ¦+¦f3g3 ¦1-0-¦ ¦1110¦0¦¦ ¦ ¦ ¦c2d1 ¦1-01¦g2 ¦+¦f5g2 ¦1-0-¦ ¦1111¦0¦¦ ¦ ¦ ¦c3d1 ¦110-¦g3 ¦+¦ ¦ ¦ L----+--L----+--+-+----+----+--+-+----+------
Імпліканта називається простою, якщо вона є кон'юнкцією змінних, і будь-яка кон'юнкція, отримана з неї шляхом викреслювання будь-яких змінних, не є імплікантою. Побудова простих імплікант ілюструється прикладом 2.2.1.
Приклад 2.2.1. Нехай функція f(a,b,c,d) задана в табл. 2.2.1. Випишемо до графи І табл. 2.2.2 усі набори, на яких функція f обертається в 1. Для виконання алгоритму їх зручно виписати розбитими на групи у відповідності з кількістю одиничних компонент у наборах (колонка К у графі І табл. 2.2.2). Оскільки мінімізуються (склеюються) лише набори, які відрізняються в одній компоненті, то для того, щоб провести всі склеювання по одній змінній, досить продивитися всі можливі пари наборів, які входять до двох сусідніх груп. Результати склеювання наборів із графи I розмістимо у графі II. Набори із графи I, які приймали участь у склеюваннях, позначимо знаком +. У графі II набори вже автоматично розбиваються на групи за кількістю одиниць (при склеюванні наборів графи I з груп із j-1 одиницями і з j одиницями отримуються набори графи II із j-1 одиницями).
До створених наборів знову застосовуємо операцію склеювання (клеяться пари наборів, які мають риску на однакових місцях і відрізняються однією компонентою). При цьому треба знову переглянути всі пари наборів із сусідніх груп. Набори, до яких застосована операція, позначені знаком +. Результати склеювання заносимо до графи III таблиці. У графі III знову намагаємося виконати склеювання, але цього зробити не вдається. На цьому процедура завершується.
У табл. 2.2.2 позначено графи:
К - код набору;
С - склеюванням яких наборів цей код утворився;
П - умовне позначення набору;
У - позначка про участь набору в склеюванні.
В отриманій таблиці знаходяться всі імпліканти функції f, які мають вигляд кон'юнкцій. Простими будуть лише ті з них, які не мають позначки + (із яких не можна викреслити жодної змінної, інакше може бути застосована операція склеювання). В розглянутому прикладі простими імплікантами є кон'юнкції
/ab/d, /b/c, /c/d, /bd, a/c,
які відповідають наборам
01-0, -00-, --00, -0-1, 1-0-.
2. Формування мінімальної диз'юнктивної нормальної форми.
Таблиця 2.2.3 -----T------T----T-----T----T----¬ ¦ ¦ I1 ¦ I2 ¦ I3 ¦ I4 ¦ I5 ¦ ¦abcd¦/аb/d ¦/b/c¦/c/d)¦/bd ¦a/c ¦ ¦ ¦ 01-0 ¦-00-¦--00 ¦-0-1¦1-0-¦ +----+------+----+-----+----+----+ ¦0000¦ ¦ * ¦ * ¦ ¦ ¦ ¦0001¦ ¦ * ¦ ¦ * ¦ ¦ ¦0011¦ ¦ ¦ ¦ * ¦ ¦ ¦0100¦ * ¦ ¦ * ¦ ¦ ¦ ¦0110¦ * ¦ ¦ ¦ ¦ ¦ ¦1000¦ ¦ * ¦ * ¦ ¦ * ¦ ¦1001¦ ¦ * ¦ ¦ * ¦ * ¦ ¦1011¦ ¦ ¦ ¦ * ¦ ¦ ¦1100¦ ¦ ¦ * ¦ ¦ * ¦ ¦1101¦ ¦ ¦ ¦ ¦ * ¦ L----+------+----+-----+----+-----
Позначимо через I1, I2, ..., Is всі прості імпліканти функції f. Будемо говорити, що кон'юнкція К покриває набір n, якщо на наборі n вона дорівнює 1. Побудуємо імплікантну таблицю (таблицю покриття) по функції f. Її рядки відповідають одиничним наборам функції f, а графи - простим імплікантам. На схрещенні рядка n і графи Ij проставляється *, якщо імпліканта Ij покриває набір n (у протилежному випадку не ставиться нічого).
Імплікантна табл. 2.2.3 відповідає функції, заданій у табл. 2.2.1, і імплікантам, знайденим за допомогою табл. 2.2.2.
З імплікантою Ij будемо пов'язувати логічну змінну іj. Кожній множині імплікант приписується набір значень змінних іj: якщо Ij входить у множину, то іj=1, якщо ні, то іj=0. Розглянемо рядок таблиці покриття, який відповідає якомусь набору n. Нехай у цьому рядку символи * знаходяться у графах I1, I2, ..., Iw. Рядок n буде покритий тоді і лише тоді, коли до множини буде введена хоча б одна з імплікант I1, I2, ..., Iw, тобто коли диз'юнкція і1 v і2 v ... v іw дорівнює 1. Складемо таку диз'юнкцію для кожного рядка імплікантної таблиці і візьмемо їхній добуток по всіх рядках. Отримаємо функцію F, яка для табл. 2.2.3 має вигляд
F=(і2 v і3)(і2 v і4)і4(і1 v і3)і1(і2 v і3 v і5)(і2 v і4 v і5)і4(і3 v і5)і5.
Після спрощення F = і1і2і4i5 v і1і3і4і5. Тепер функція F вказує на 2 ненадмірних покриття: {I1, I2, I4, I5} та {I1, I3, I4, I5}. Їм відповідають дві ДНФ, кожна з яких складаються з 9 літер, тому кожна з них є мінімальною. Таким чином, дана функція f має дві мінімальні ДНФ:
f = I1 v I2 v I4 v I5 = /ab/d v /b/c v /bd v a/c,
f = I1 v I3 v I4 v I5 = /ab/d v /c/d v /bd v a/c.
Мінімізація не повністю визначених функцій методом Квайна-МакКласкі-Петрика.
Всі дії відбуваються, як описано вище. Лише на першому етапі до табл. 2.2.2 як початкові набори вводяться додатково і всі набори, на яких функція не визначена, а на другому – до табл. 2.2.3, як і раніше, тільки набори, на яких функція приймає значення 1.
Приклад 2.2.2. Функція задана табл.2.2.4, Х – невизначене значення.
Знаходження простих імплікант - табл. 2.2.5.
Знаходження мінімального покриття - табл. 2.2.6.
2.3. Мінімізація функцій за допомогою карт Карно
Карти Карно є одним з найефективніших засобів знаходження мінімальних диз'юнктивних нормальних форм (МДНФ) для функцій невеликої кількості змінних (4...6).
На картах Карно кожному з 2n наборів відповідає одна клітинка. Якщо на даному наборі аргументів функція дорівнює 1, то в клітинці, яка відповідає даному набору, записується 1. Клітинки, які відповідають наборам, де функція дорівнює 0, або заповнюють 0, або залишають незаповненими. Клітинки, які відповідають наборам, де функція недовизначена, заповнюють Х (рис. 2.3.1).
Кожна із змінних x розбиває карту Карно на дві половини - половину x і половину (-x). Половини карт, які відповідають неінверсним аргументам, позначені на рис 2.3.1, де зображена карта Карно на 5 змінних - e, a, b, c, d, які утворюють набори {eabcd}.
Таблиця Таблиця 2.2.5 2.2.4 -----------------T-----------------------T----------------¬ -----T-¬¦ I ¦ II ¦ III ¦ ¦abcd¦f¦+---------T----T-+------T---------T----T-+------T---------+ +----+-+¦ К ¦ П ¦У¦ С ¦ К ¦ П ¦У¦ С ¦ К ¦ ¦0000¦0¦+---------+----+-+------+---------+----+-+------+---------+ ¦0001¦0¦¦ 0 1 0 1 ¦ a0 ¦+¦ a0b0 ¦ 0 1 - 1 ¦ d0 ¦+¦ d0e2 ¦ - 1 - 1 ¦ ¦0010¦0¦¦ 1 0 1 0 ¦ a1 ¦+¦ a0b2 ¦ - 1 0 1 ¦ d1 ¦+¦ d1e0 ¦ - 1 - 1 ¦ ¦0011¦0¦+---------+----+-+ a1b1 ¦ 1 0 1 - ¦ d2 ¦+¦ d2e3 ¦ 1 - 1 - ¦ ¦0100¦0¦¦ 0 1 1 1 ¦ b0 ¦+¦ a1b3 ¦ 1 - 1 0 ¦ d3 ¦+¦ d3e1 ¦ 1 - 1 - ¦ ¦0101¦1¦¦ 1 0 1 1 ¦ b1 ¦++------+---------+----+-+ ¦ ¦ ¦0110¦0¦¦ 1 1 0 1 ¦ b2 ¦+¦ b0c0 ¦ - 1 1 1 ¦ e0 ¦+¦ ¦ ¦ ¦0111¦Х¦¦ 1 1 1 0 ¦ b3 ¦+¦ b1c0 ¦ 1 - 1 1 ¦ e1 ¦+¦ ¦ ¦ ¦1000¦0¦+---------+----+-+ b2c0 ¦ 1 1 - 1 ¦ e2 ¦+¦ ¦ ¦ ¦1001¦0¦¦ 1 1 1 1 ¦ c0 ¦+¦ b3c0 ¦ 1 1 1 - ¦ e3 ¦+¦ ¦ ¦ ¦1010¦Х¦L---------+----+-+------+---------+----+-+------+---------- ¦1011¦Х¦ Таблиця 2.2.6 ¦1100¦0¦ --------T-----------T----------¬ F = і1(і1 v і2) = ¦1101¦Х¦ ¦ ¦ I1 ¦ I1 ¦ = і1 v і1і2 = і1. ¦1110¦Х¦ ¦ abcd ¦ bd ¦ ac ¦ f = I1 = bd. ¦1111¦1¦ ¦ ¦ -1-1 ¦ 1-1- ¦ L----+-- +-------+-----------+----------+ ¦ 0101 ¦ * ¦ ¦ ¦ 1111 ¦ * ¦ * ¦ L-------+-----------+-----------
Номери наборів проставлені у верхніх лівих кутках клітинок карти (у шістнадцятковому коді).
----c --¬ -----c ---¬ г===T====T===T===¬ -¬ г====T===T====T====¬ ¦10 ¦11 ¦13 ¦12 ¦ ¦ ¦0 ¦1 ¦3--¬¦2 ¦ ¦ 0¦ 0 ¦ 0¦ X¦ ¦ ¦ 0 ¦ 0 ¦ ¦X¦¦ 0 ¦ ¦===+====+===+===¦ ¬¦ ¦====+===+=+=++====¦ -¬ ¦14 ¦15 ¦17 ¦16 ¦ ¦¦ ¦4 ¦5 ¦7¦ ¦¦6 ¦ ¦ ¦ 0¦ X ¦ 0¦ 0¦ ¦¦ +---¬¦ ¦ ¦ ¦¦ ---+- ¦ ¦ ¦ ¦ ¦ ¦ ¦¦ ¦ 1¦¦ 0 ¦ ¦1¦¦ ¦X ¦ ¦ --¦===+====+===+===¦ be --¦===++===+=+=++=+==¦ b ¦ ¦1C ¦1D ¦1F ¦1E ¦ ¦¦ ¦ ¦C ¦¦D ¦F¦ ¦¦E¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦¦ ¦ ¦---++---+-+-++-+-¬¦ ¦ ¦ ¦ --+---¬¦ ¦ ¦ ¦¦ ¦ ¦¦--++--¬¦ ¦ ¦¦ ¦ ¦¦ ¦ ¦ ¦ ¦1¦ 1¦¦ 0¦ X¦ ¦¦ ¦ ¦¦¦X¦¦ 1¦¦ ¦1¦¦ ¦X¦¦ ¦ ¦ ¦ L-+----¦ ¦ ¦ ¦¦ ¦ +++-++---¦ ¦ ¦¦ L-++- ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦¦ a ¦L---+---+-+-++----¦ ¦ a ¦===+====+===+===¦ -¦ ¦ ¦====+===+=+=++====¦ -- ¦ ¦18 ¦19 ¦1B ¦1A ¦ ¦ ¦ ¦8 ¦9 ¦B¦ ¦¦A ¦ ¦ ¦ X¦ 0 ¦ X¦ 0¦ ¦ ¦ ¦ 0 ¦ X ¦ ¦1¦¦ 0 ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ L--¦ ¦ L-L===¦====¦===¦===- -- L-L====¦===¦====¦====- L----d --- L---d ---- Рис 2.3.1.
Правила мінімізації такі:
1) сусідніми вважаються клітинки, які відрізняються значенням лише однієї змінної, тобто:
а) дві клітинки, які мають спільну грань;
б) клітинки, які знаходяться в крайньому правому і крайньому лівому стовпцях однієї карти в одному рядку;
в) клітинки, які знаходяться в крайньому верхньому і крайньому нижньому рядках однієї карти в одному стовпчику;
г) клітинки, які займають однакове положення в сусідніх картах.
Для випадку 5 змінних (e, a, b, c, d) мінімізація проводиться на двох картах, для 6 (g, e, a, b, c, d) змінних - на 4-х картах (рис. 2.3.2). Кожна карта розбивається змінними a, b, c, d на 16 клітинок однаково, як це показано на рис. 2.3.1.
----T---¬----T---¬ ¦0Y ¦1Y ¦¦0Y ¦1Y ¦ L---+----+---+---+-¬ L е -¦2Y ¦3Y ¦ g L---+------ L е - Примітка: Y = 0,...,F. Рис. 2.3.2.
2) Дві сусідні клітинки об'єднуються (склеюються), при цьому зникає змінна, якою ці клітинки відрізняються.
3) 4 сусідні клітинки, які утворюють прямокутник (або у просторі прямокутний паралелепіпед, якщо накласти карти одна на одну), об'єднуються (склеюються), при цьому зникають 2 змінні, якими ці клітинки відрізняються.
4) 8 сусідніх клітинок, які утворюють прямокутник (прямокутний паралелепіпед), об'єднуються (склеюються), при цьому зникають 3 змінні, якими ці клітинки відрізняються.
5) 16 сусідніх клітинок, які утворюють прямокутник (прямокутний паралелепіпед), об'єднуються (склеюються), при цьому зникають 4 змінні, якими ці клітинки відрізняються.
6) Загалом: 2n сусідніх клітинок, які утворюють прямокутник (прямокутний паралелепіпед), об'єднуються (склеюються), при цьому зникають n змінних, якими ці клітинки відрізняються.
7) Кожну клітинку можна склеювати безліч разів.
8) Невизначене значення функції (позначається на карті Х) можна вважати як 0, так і 1 в залежності від зручності мінімізації.
9) Так само, як і по 1, можна робити склеювання і по 0. В результаті буде отриманий вираз для інверсної функції /f.
10) Одночасно можна клеїти або тільки за 1, або тільки за 0.
Приклад 2.3.1. Мінімізувати функцію, задану на рис. 2.3.1, за "1".
Результати склеювання позначені на рис. 2.3.1. Всі склеювання - по 4 клітинки:
клітинки 4, C, 6, E - результат /eb/d, зникли 2 змінні a і c. Це склеювання потрібне, щоб мінімізувати набір 4, на якому функція визначена і дорівнює "1";
клітинки C, D, F, E - результат /eab, зникли 2 змінні c і d. Це склеювання потрібне, щоб мінімізувати набори D і E, на яких функція визначена і дорівнює "1";
клітинки 3, 7, F, B - результат /ecd, зникли 2 змінні a і b. Це склеювання потрібне, щоб мінімізувати набори 7, F і B, на яких функція визначена і дорівнює "1";
клітинки C, D, 1C, 1D - результат ab/c, зникли 2 змінні e і d. Це склеювання потрібне, щоб мінімізувати набір 1C і 1D, на яких функція визначена і дорівнює "1".
Невизначені значення функції в клітинках (наборах) 9, 12, 15, 1Е, 18, 1B довизначаємо як "0", оскільки вони не допомагають при склеюванні за "1".
Невизначені значення функції в клітинках (наборах) 3, 6, C, Е довизначаємо як "1", оскільки вони допомагають при склеюванні за "1".
Набори 3, 4, 6, 7, D, B, 1C, 1D - кожен бере участь в одному склеюванні.
Набори D, F, E - беруть участь у двох склеюваннях кожний.
Набір C - бере участь у трьох склеюваннях.
Остаточний результат:
f = /eb/d v /eab v /ecd v ab/c.
Приклад 2.3.2. Мінімізувати функцію, задану на рис. 2.3.1, за "0".
Результати склеювання позначені на рис. 2.3.3.
---- c ------¬ -- c ---¬ г==+==+T=====T====T==+==+=¬ -¬ г===+T====T==T=+==¬ ¦10¦ ¦¦11--¬¦13--+--+--+¬¦ ¦ ¦0 ¦¦1--¬¦3 ¦2¦ ¦ ¦ ¦--++--+-++--+-+--+-¬¦¦¦ ¦ ¦ --++-+-++--+-+-¬¦ ¦ ¦¦0¦¦ ¦0¦¦ ¦0¦ ¦X¦¦¦¦ ¦ ¦ ¦0¦¦ ¦0¦¦ X¦ ¦0¦¦ -+--++--¦ ¦ ¦¦ ¦ ¦ L-++++- ¦ -+-+--¦ ¦ ¦¦ ¦ L-++- ¦ L+--+--+-++--+-+----+-¦¦ ¦ ¦ L--+-+-++--+----¦ ¦===+==+==+=++==+=+====+=+¦ ¬¦ ¦====+=+=++==+====¦ -¬ ¦14 ¦ ¦15¦ ¦¦17¦ ¦16 ¦ ¦¦ ¦¦ ¦4 ¦5¦ ¦¦7 ¦6 ¦ ¦ ¦ ¦0 ¦ ¦X¦¦ ¦0¦ 0¦ ¦¦ ¦¦ ¦ 1 ¦ ¦0¦¦ 1¦ X ¦ ¦ ¦ L--+--+-++--+-+----- ¦¦ ¦¦ ¦ ¦ L--¦ ¦ ¦ ¦ ¦ ¦ L--¦ ¦ ¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦ -- ¦======+=====+==+=+======+¦ be -- ¦====+====+==+====¦ b ¦ ¦1C ¦1D ¦1F¦ ¦1E ¦¦ ¦¦ ¦ ¦C ¦D ¦F ¦E ¦ ¦ ¦ ¦ 1 ¦ 1 ¦ ¦0¦ X ¦¦ ¦¦ ¦ ¦ X ¦ 1 ¦ 1¦ X ¦ ¦ a ¦======+=====+==+=+======+¦ -¦ a ¦====+====+==+====¦ -- ¦ ¦18 ¦19 ¦1B¦ ¦1A ¦¦ ¦ ¦ ¦8 ¦9 ¦B ¦A ¦ ¦ -+-----¬¦ ¦ ¦ ¦ ----++- ¦ ¦ -+---¬¦ ¦ ¦ ---+- ¦ ¦ ---++-----+--+-+--+--¬¦¦ ¦ ¦ ¦ 0¦¦ X ¦ 1¦ ¦0 ¦ ¦ ¦ ¦ X¦¦ 0 ¦ ¦X¦ ¦0 ¦¦¦ ¦ ¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦¦ ¦ L-+--+--+-¦ ¦ ¦ ¦ ¦¦ ¦ ¦ ¦ ¦ L- L==+==+¦=====¦====¦==+==+=- -- L- L===+¦====¦==¦=+==- L---- d ---- L----d -- Рис.2.3.3.
Склеювання по 8 клітинки:
клітинки 0, 1, 2, 3, 10, 11, 12, 13 - результат /a/b, зникли 3 змінні - c, d і e. Це склеювання потрібне, щоб мінімізувати набори 0, 1, 2, 10, 11, 12, на яких функція визначена і дорівнює "0";
клітинки 0, 2, 8, A, 10, 12, 18, 1A - результат /b/d, зникли 3 змінні - a, c і e. Це склеювання потрібне, щоб мінімізувати набори 8, A, 1A, на яких функція визначена і дорівнює "0" (набори 0, 2, 10, 12 вже були мінімізовані на попередньому етапі);
клітинки 10, 11, 12, 13, 14, 15, 16, 17 - результат /ae, зникли 3 змінні - b, c і d. Це склеювання потрібне, щоб мінімізувати набори 14, 16, 17, на яких функція визначена і дорівнює "0" (набори 10, 11, 12 вже були мінімізовані на попередніх етапах);
клітинки 10, 11, 12, 13, 18, 19, 1A, 1B - результат /be, зникли 3 змінні - a, c і d. Це склеювання потрібне, щоб мінімізувати набори 19, 1A, на яких функція визначена і дорівнює "0" (набори 10, 11, 12 вже були мінімізовані на попередніх етапах);
клітинки 12, 13, 16, 17, 1A, 1B, 1E, 1F - результат ce, зникли 3 змінні - a, b і d. Це склеювання потрібне, щоб мінімізувати набір 1F, на якому функція визначена і дорівнює "0" (набори 12, 16, 17, 1А вже були мінімізовані на попередніх етапах).
Склеювання по 4 клітинки:
клітинки 1, 5, 11, 15 - результат /a/cd, зникли 2 змінні - b і e. Це склеювання потрібне, щоб мінімізувати набір 5, на якому функція визначена і дорівнює "0" (набори 1 і 11 вже були мінімізовані на попередніх етапах).
Невизначені значення функції в клітинках (наборах) 6, 9, C, F довизначаємо як "1", оскільки вони не допомагають при склеюванні за "0".
Невизначені значення функції в клітинках (наборах) 3, 13, 15, 18, 1B довизначаємо як "0", оскільки вони допомагають при склеюванні за "0".
Набори 3, 5, 8, A, 14, 19, 1E, 1F - беруть участь в одному склеюванні кожний.
Набори 0, 1, 2, 16, 17, 18, 1B- беруть участь у двох склеюваннях кожний.
Набори 10, 11, 1A - беруть участь у трьох склеюваннях кожний.
Набір 12 - бере участь у чотирьох склеюваннях.
Оскільки склеювання проводиться за “0”, то в результаті мінімізації отримаємо диз’юнктивну нормальну форму для інверсного значення функції /f:
/f = /a/b v /b/d v /ae v /be v ce v /a/cd.
Пряме значення функції f отримується згідно з правилами Моргана у вигляді кон'юнктивної нормальної форми:
f = (a v b)(b v d)(a v /e)(b v /e)(/c v /e)(a v c v /d).
2.4. Визначення сполучного терма
-----b --¬ г==T===T====T===¬ ¦0 ¦1 ¦3 ¦2 ¦ c (=1) ---¬ ---¬ ¦ ¦ ¦ ---+--¬¦ ---------------+& ¦ ac ¦1 ¦ ¦ ¦ ¦ ¦1 ¦ 1¦¦ a (1->0) ¦ +------+ ¦ ¦ ¦ ¦ L--+---¦ --T------------+ ¦(1->0)¦ ¦ --¦==+===+====+===¦ ¦ ---¬ ¦ ¦ ¦ ¦f ¦ ¦4 ¦5 ¦7 ¦6 ¦ ¦ ¦& ¦ /a +--+ ¦ +--------- ¦ ¦ ¦ --+---¬¦ ¦ L-+ o-------+& ¦/ab ¦ ¦(1->0->1) a ¦ ¦ ¦1¦ 1¦¦ ¦ ¦ ¦ (0->1)¦ +------+ ¦ ¦ ¦ ¦ L-+----¦ ¦ L---b (=1) ¦ ¦(0->1)¦ ¦ L-L==¦===¦====¦===- ---------------+ ¦ ¦ ¦ L--- c---- L--- L--- Рис. 2.4.1 Рис. 2.4.2 a (1->0) ---¬ -----¬ ----------- --T----------+1 ¦ a "1"¦ "0" ¦ "1" ¦---¬ ¦ ¦f L------------- ¦¦& ¦ -a ¦ +--------- . . L+ o------+ ¦(1->0->1) . ----------¬ ¦ ¦(0->1)¦ ¦ -a "0". ¦ "1" . ¦ "0" L--- L--- ------------- . L------- Рис. 2.4.3 . . ------¬ ------------------ f "1"¦ "0" ¦ "1" L------ Рис. 2.4.4 Розглянемо функцію f(a, b, c), яка задана картою Карно (рис. 2.4.1).
Результати мінімізації також зображені на рис. 2.4.1. Результат мінімізації f(a,b,c) = ac v /ab. Схема, яка реалізує цю функцію, наведена на рис. 2.4.2.
-------- b --¬ -- b -¬ -- b -¬ г==T===T========T===¬ г====T===T=T===¬ г======T===T=T===¬ ¦0 ¦1 ¦3-----¬ ¦2 ¦ ¦0 ¦1 ¦3¦2 ¦ ¦0----¬¦1 ¦3¦2 ¦ ¦ ¦ ¦ ¦----+-¦--¬¦ ¦ ---+--¬¦ ¦ ¦ ¦ ¦---++--¬¦ ¦ ¦ ¦ ¦ ¦ ¦¦ 1 ¦ ¦ 1¦¦ ¦ ¦0 ¦ 0¦¦ ¦ ¦ ¦ ¦¦0 ¦¦ 0¦¦ ¦ ¦ ¦ ¦ ¦ ¦L---+-¦---¦ ¦ L--+---¦ ¦ ¦ ¦ ¦L--++---¦ ¦ ¦ -¦==+===+=+====+=+===¦-¦====+===+=+===¦ -¦=+===++===+=+===¦ ¦¦4 ¦5 ¦7¦ ¦ ¦6 ¦¦¦4 ¦5 ¦7¦6 ¦ ¦¦4¦ ¦¦5 ¦7¦6 ¦ ¦¦ ¦ --+-+---¬¦ ¦ ¦¦+---¬¦ ¦ ¦ --+ ¦+-+--¬¦¦ ¦ ¦ --+ a¦ ¦ ¦1¦ ¦ 1¦¦ ¦ ¦a¦ 0¦¦ ¦ ¦ ¦0¦ a¦ ¦ 0¦¦¦ ¦ ¦ ¦0¦ ¦¦ ¦ L-+-+----¦ ¦ ¦¦+----¦ ¦ ¦ L-+ ¦+-+---¦¦ ¦ ¦ L-+ ¦¦ ¦ ¦ L----- ¦ ¦¦¦ ¦ ¦ ¦ ¦ ¦¦ L----¦ ¦ ¦ ¦ LL==¦===¦========¦===-LL====¦===¦=¦===- LL======¦===¦=¦===- L--- c ------- L- c -- L- c -- Рис. 2.4.5 Рис. 2.4.6 Рис. 2.4.7
Розглянемо, що відбувається на виході схеми, коли інформація на входах міняється, а власне комбінація abc (7-ий набір) міняється на комбінацію /abc (3-ій набір). При такому переході змінні b і c залишаються сталими (=1), а змінна a міняє свій стан від 1 до 0, що зображено на рис. 2.4.2. Згідно з рис. 2.4.1, значення f не повинно при цьому змінюватися. Еквівалентна схема для цього переходу зображена на рис. 2.4.3, а часова діаграма - на рис. 2.4.4 (сигнал f на рис. 2.4.4. показано без врахування внутрішньої затримки елемента АБО).
Через затримку на елементі НЕ сигнал /a змінюється з запізненням відносно сигналу a. Це призводить до одночасної появи на входах елемента АБО 2-х сигналів низького рівня, наслідком чого буде поява короткочасного сигналу 0 (просічки) на виході елемента АБО. Виникає так званий ефект гонок. Щоб позбутися цього негативного ефекту, необхідно об'єднати всі сусідні набори, на яких функція приймає значення "1" і які не об'єднані в Таблиця 2.4.1 Можливі комбінації розрядів пар простих імплікант --------------------T-------------------T---------¬ ¦Перший елемент пари¦Другий елемент пари¦Результат¦ +-------------------+-------------------+---------+ ¦ - ¦ - ¦ - ¦ ¦ - ¦ 0 ¦ 0 ¦ ¦ - ¦ 1 ¦ 1 ¦ ¦ 0 ¦ - ¦ 0 ¦ ¦ 0 ¦ 0 ¦ 0 ¦ ¦ 0 ¦ 1 ¦ x(-)¦ ¦ 1 ¦ - ¦ 1 ¦ ¦ 1 ¦ 0 ¦ x(-)¦ ¦ 1 ¦ 1 ¦ 1 ¦ L-------------------+-------------------+---------- результаті мінімізації спільним склеюванням (спільним термом), за допомогою так званого сполучного терма. Для наведеного прикладу це показано на рис. 2.4.5. Остаточний результат мінімізації із врахуванням сполучного терма:
f = ac v /ab v bc. Тут bc - сполучний терм.
Таблиця 2.4.2 -----------T----¬ ¦ Номер ¦ ¦ ¦імпліканти¦abcd¦ +----------+----+ ¦ і0 ¦-00-¦ ¦ і1 ¦01--¦ ¦ і2 ¦1-11¦ L----------+-----
Аналогічна ситуація може виникати при склеюванні за "0". Наприклад, рис. 2.4.6, де /f = a/c v /a/b. Гонки можуть виникати при здійсненні переходів між 0 і 4 наборами. Для їх усунення вводиться сполучний терм, як показано на рис. 2.4.7. Внаслідок цього остаточний результат буде
/f = a/c v /a/b v v /b/c, де /b/c - сполучний терм.
Визначення сполучного терма при записі методом Мак-Класкі.
Попарне порозрядне порівняння (табл. 2.4.1) простих імплікант здійснюється після виконання мінімізації методом Квайна-Мак-Класкі для визначення сполучного терма. Якщо при порівнянні будь-якої пари імплікант символ "x" зустрічається тільки один раз, то це говорить про необхідність введення сполучного терму. Розряди такого терма визначаються згідно з графою "Результат" табл. 2.4.1 і при цьому символ "x" заміняється міткою "-".
Приклад 2.4.1. Визначити сполучні терми для функції
Таблиця 2.4.3 -------------T----¬-------------T----¬-------------T----¬ ¦Порівнюються¦ ¦¦Порівнюються¦ ¦¦Порівнюються¦ ¦ +------------+----++------------+----++------------+----+ ¦ і0 ¦-00-¦¦ і0 ¦-00-¦¦ і1 ¦01--¦ ¦ і1 ¦01--¦¦ і2 ¦1-11¦¦ і2 ¦1-11¦ +------------+----++------------+----++------------+----+ ¦ ¦0x0-¦¦ ¦10x1¦¦ ¦x111¦ ¦ Результат +----+¦ Результат +----+¦ Результат +----+ ¦ ¦0-0-¦¦ ¦10-1¦¦ ¦-111¦ +------------+----++------------+----++------------+----+ ¦ Терм ¦/a/c¦¦ Терм ¦a/bd¦¦ Терм ¦bcd ¦ L------------+-----L------------+-----L------------+-----
f = /b·/c v /a·b v a·c·d.
Таблиця 2.4.4 -----------T----¬ ¦ Номер ¦ ¦ ¦імпліканти¦abcd¦ +----------+----+ ¦ і0 ¦0-0-¦ ¦ і1 ¦01--¦ ¦ і2 ¦1010¦ L----------+----- При записі методом Мак-Класкі функція буде мати вигляд табл. 2.4.2. Результати попарного порівняння наведені в табл. 2.4.3. Оскільки при кожному порівнянні сформувався один символ "x", то кожний терм є сполучним і тому необхідним. Після введення сполучних термів, функція буде мати вигляд
f = /b·/c v /a·b v v a·c·d v /a·/c v a·/b·d v v b·c·d.
Наведений приклад ілюструється картою Карно (рис. 2.4.8).
Приклад 2.4.2. Визначити сполучні терми, для функції
f = /a·/c +/a·b + a·/b·c·/d.
Таблиця 2.4.5 -------------T-----¬-------------T-----¬-------------T-----¬ ¦Порівнюються¦ ¦¦Порівнюються¦ ¦¦Порівнюються¦ ¦ +------------+-----++------------+-----++------------+-----+ ¦ і0 ¦0-0- ¦¦ і0 ¦0-0- ¦¦ і1 ¦01-- ¦ ¦ і1 ¦01-- ¦¦ і2 ¦1010 ¦¦ і2 ¦1010 ¦ +------------+-----++------------+-----++------------+-----+ ¦ ¦010 -¦¦ ¦x0x0 ¦¦ ¦xx10 ¦ ¦ Результат +-----+¦ Результат +-----+¦ Результат +-----+ ¦ ¦немає¦¦ ¦немає¦¦ ¦немає¦ +------------+-----++------------+-----++------------+-----+ ¦ Терм ¦немає¦¦ Терм ¦немає¦¦ Терм ¦немає¦ L------------+------L------------+------L------------+------
При записі методом Мак-Класкі функція буде мати вигляд табл. 2.4.4. Результати попарного порівняння наведені в табл. 2.4.5. Оскільки при попарному порівнянні або не формувалося жодного символу "x", або їх формувалося більше ніж один, то в даному прикладі сполучних термів не буде. Наведений приклад ілюструється картою Карно (рис. 2.4.9).
