Частина 2. Методичні вказівки щодо використання функцій алгебри логіки та мінімізації цих функцій у базисі Буля 2.1 Функціональна повнота системи функцій алгебри логіки і наборів логічних елементів Основна вимога, яка ставиться до набору логічних елементів, полягає в тому, щоб за допомогою цього набору можна було побудувати будь-яку логічну схему. З огляду на те, що функціонування елементів однозначно описується функціями алгебри логіки (ФАЛ), застосовуючи операцію суперпозиції, можна з деякої системи ФАЛ отримати будь-яку, скільки завгодно складну ФАЛ. Тоді ця деяка система ФАЛ буде називатися функціонально повною (ФПС ФАЛ). Функціонально повним є такий набір ФАЛ, який містить хоча б одну функцію, яка: не зберігає константу "0"; не зберігає константу "1"; не є монотонною; не є самодвоїстою; не є лінійною. Якщо функція F на нульовому наборі змінних дорівнює 0, тобто F(0,0,...,0)=0, то ця функція зберігає константу "0". Таблиця 2.1.1 ┌──┬────┬────────────────┬──────────────┬─────────┐ │х0 │0011│Назва ФАЛ │ Вираз ФАЛ │ Клас │ │х1 │0101│ │ ├─┬─┬─┬─┬─┤ │ │ │ │ │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 │ │Х│Х│Х│ │ └──┴────┴────────────────┴──────────────┴─┴─┴─┴─┴─┘ Якщо функція 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 ┌───┬─┐ │abc│f│ ├───┼─┤ │000│1│ │001│0│ │010│1│ │011│1│ │100│0│ │101│0│ │110│1│ │111│0│ └───┴─┘ # - позначення операції "додавання за модулем 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 ┌───┬─┐┌───┬─┐┌───┬─┐┌───┬─┐┌───┬─┐┌───┬─┐ │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│ └───┴─┘└───┴─┘└───┴─┘└───┴─┘└───┴─┘└───┴─┘ а б в г д е # 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 ┌─────┬───┬─────┬───┐ │ abc │ f │ abc │ f │ ├─────┼───┼─────┼───┤ │ 000 │ 1 │ 111 │ 0 │ │ 001 │ 0 │ 110 │ 1 │ │ 010 │ 1 │ 101 │ 0 │ │ 011 │ 1 │ 100 │ 0 │ └─────┴───┴─────┴───┘ Оскільки поліном містить добутки змінних, то функція не є лінійною. Отже, із п'яти необхідних для створення ФПС властивостей відсутня одна - несамодвоїстість, тому дана функція не утворює ФПС. 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 ┌─────────┬──────────────┬──────────┐ ┌────┬─┐│ I │ II │ III │ │abcd│f│├────┬──┬─┼────┬────┬──┬─┼────┬─────┤ ├────┼─┤│ К │П │У│ С │ К │П │У│ С │ К │ │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 │+│ │ │ └────┴─┘└────┴──┴─┴────┴────┴──┴─┴────┴─────┘ Імпліканта називається простою, якщо вона є кон'юнкцією змінних, і будь-яка кон'юнкція, отримана з неї шляхом викреслювання будь-яких змінних, не є імплікантою. Побудова простих імплікант ілюструється прикладом 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 ┌────┬──────┬────┬─────┬────┬────┐ │ │ 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│ │ │ │ │ * │ └────┴──────┴────┴─────┴────┴────┘ Позначимо через 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 ┌────────────────┬───────────────────────┬────────────────┐ ┌────┬─┐│ I │ II │ III │ │abcd│f│├─────────┬────┬─┼──────┬─────────┬────┬─┼──────┬─────────┤ ├────┼─┤│ К │ П │У│ С │ К │ П │У│ С │ К │ │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│Х│└─────────┴────┴─┴──────┴─────────┴────┴─┴──────┴─────────┘ │1011│Х│ Таблиця 2.2.6 │1100│0│ ┌───────┬───────────┬──────────┐ 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- │ └────┴─┘ ├───────┼───────────┼──────────┤ │ 0101 │ * │ │ │ 1111 │ * │ * │ └───────┴───────────┴──────────┘ Номери наборів проставлені у верхніх лівих кутках клітинок карти (у шістнадцятковому коді). ┌───c ──┐ ┌────c ───┐ ╔═══╦════╦═══╦═══╗ ─┐ ╔════╦═══╦════╦════╗ ║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│║ │ │ ║ └─╫───┘║ ║ ║ ││ │ ╫┼┴─┴╫──┘║ │ │║ └─┼╫─ │ │ ║ ║ ║ ║ ║ ││ a ║└───╫───╫─┼─┼╫───┘║ │ a ╠═══╬════╬═══╬═══╣ ┘│ │ ╠════╬═══╬═╪═╪╬════╣ ─┘ │ ║18 ║19 ║1B ║1A ║ │ │ ║8 ║9 ║B│ │║A ║ │ ║ X║ 0 ║ X║ 0║ │ │ ║ 0 ║ X ║ │1│║ 0 ║ │ ║ ║ ║ ║ ║ │ │ ║ ║ ║ └─┘║ ║ └─╚═══╩════╩═══╩═══╝ ─┘ └─╚════╩═══╩════╩════╝ └────d ──┘ └───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. ┌───┬───┐┌───┬───┐ │0Y │1Y ││0Y │1Y │ └───┴───┘├───┼───┤─┐ └ е ┘│2Y │3Y │ g └───┴───┘─┘ └ е ┘ Примітка: 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 ───┐ ╔══╪══╪╦═════╦════╦══╪══╪═╗ ─┐ ╔═══╪╦════╦══╦═╪══╗ ║10│ │║11┌─┐║13┌─╫──┼──┼┐║ │ ║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 ║ │ a ╠══════╬═════╬══╪═╬══════╪╣ ┘│ a ╠════╬════╬══╬════╣ ─┘ │ ║18 ║19 ║1B│ ║1A │║ │ │ ║8 ║9 ║B ║A ║ │ ─╫─────┐║ ║ │ ║ ┌───┼╫─ │ │ ─╫───┐║ ║ ║ ┌──╫─ │ ║ ┌──┼╫─────╫──┼─╫──┼──┐│║ │ │ ║ 0│║ X ║ 1║ │0 ║ │ ║ │ X│║ 0 ║ │X║ │0 ││║ │ │ ║ │║ ║ ║ │ ║ │ ║ │ │║ ║ └─╫──┼──┼┘║ │ │ ║ │║ ║ ║ │ ║ └─ ╚══╪══╪╩═════╩════╩══╪══╪═╝ ─┘ └─ ╚═══╪╩════╩══╩═╪══╝ └──── d ───┘ └────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 ──┐ ╔══╦═══╦════╦═══╗ ║0 ║1 ║3 ║2 ║ c (=1) ┌──┐ ┌──┐ ║ ║ ║ ┌──╫──┐║ ───────────────┤& │ ac │1 │ ║ ║ ║ │1 ║ 1│║ a (1->0) │ ├──────┤ │ ║ ║ ║ └──╫──┘║ ──┬────────────┤ │(1->0)│ │ ┌─╠══╬═══╬════╬═══╣ │ ┌──┐ │ │ │ │f │ ║4 ║5 ║7 ║6 ║ │ │& │ /a ├──┤ │ ├───────── │ ║ ║ ┌─╫───┐║ ║ └─┤ o───────┤& │/ab │ │(1->0->1) a ║ ║ │1║ 1│║ ║ │ │ (0->1)│ ├──────┤ │ │ ║ ║ └─╫───┘║ ║ └──┘b (=1) │ │(0->1)│ │ └─╚══╩═══╩════╩═══╝ ───────────────┤ │ │ │ └─── c───┘ └──┘ └──┘ Рис. 2.4.1 Рис. 2.4.2 a (1->0) ┌──┐ ─────┐ ┌────────── ──┬──────────┤1 │ a "1"│ "0" │ "1" │┌──┐ │ │f └────────────┘ ││& │ -a │ ├───────── . . └┤ o──────┤ │(1->0->1) . ┌─────────┐ │ │(0->1)│ │ ─a "0". │ "1" . │ "0" └──┘ └──┘ ────────────┘ . └─────── Рис. 2.4.3 . . ──────┐ ┌───────────────── f "1"│ "0" │ "1" └─────┘ Рис. 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 ─┐ ╔══╦═══╦════════╦═══╗ ╔════╦═══╦═╦═══╗ ╔══════╦═══╦═╦═══╗ ║0 ║1 ║3┌────┐ ║2 ║ ║0 ║1 ║3║2 ║ ║0┌───┐║1 ║3║2 ║ ║ ║ ║ │┌───┼─║──┐║ ║ ┌──╫──┐║ ║ ║ ║ │┌──┼╫──┐║ ║ ║ ║ ║ ║ ││ 1 │ ║ 1│║ ║ │0 ║ 0│║ ║ ║ ║ ││0 │║ 0│║ ║ ║ ║ ║ ║ │└───┼─║──┘║ ║ └──╫──┘║ ║ ║ ║ │└──┼╫──┘║ ║ ║ ┌╠══╬═══╬═╪════╪═╬═══╣┌╠════╬═══╬═╬═══╣ ┌╠═╪═══╪╬═══╬═╬═══╣ │║4 ║5 ║7│ │ ║6 ║│║4 ║5 ║7║6 ║ │║4│ │║5 ║7║6 ║ │║ ║ ┌─╫─┼───┐│ ║ ║│╫───┐║ ║ ║ ┌─╫ │╫─┼──┐│║ ║ ║ ┌─╫ a║ ║ │1║ │ 1││ ║ ║a║ 0│║ ║ ║ │0║ a║ │ 0││║ ║ ║ │0║ │║ ║ └─╫─┼───┘│ ║ ║│╫───┘║ ║ ║ └─╫ │╫─┼──┘│║ ║ ║ └─╫ │║ ║ ║ └────┘ ║ ║│║ ║ ║ ║ ║ │║ └───┘║ ║ ║ ║ └╚══╩═══╩════════╩═══╝└╚════╩═══╩═╩═══╝ └╚══════╩═══╩═╩═══╝ └─── c ──────┘ └─ c ─┘ └─ 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 Можливі комбінації розрядів пар простих імплікант ┌───────────────────┬───────────────────┬─────────┐ │Перший елемент пари│Другий елемент пари│Результат│ ├───────────────────┼───────────────────┼─────────┤ │ - │ - │ - │ │ - │ 0 │ 0 │ │ - │ 1 │ 1 │ │ 0 │ - │ 0 │ │ 0 │ 0 │ 0 │ │ 0 │ 1 │ x(-)│ │ 1 │ - │ 1 │ │ 1 │ 0 │ x(-)│ │ 1 │ 1 │ 1 │ └───────────────────┴───────────────────┴─────────┘ результаті мінімізації спільним склеюванням (спільним термом), за допомогою так званого сполучного терма. Для наведеного прикладу це показано на рис. 2.4.5. Остаточний результат мінімізації із врахуванням сполучного терма: f = ac v /ab v bc. Тут bc - сполучний терм. Таблиця 2.4.2 ┌──────────┬────┐ │ Номер │ │ │імпліканти│abcd│ ├──────────┼────┤ │ і0 │-00-│ │ і1 │01--│ │ і2 │1-11│ └──────────┴────┘ Аналогічна ситуація може виникати при склеюванні за "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 ┌────────────┬────┐┌────────────┬────┐┌────────────┬────┐ │Порівнюються│ ││Порівнюються│ ││Порівнюються│ │ ├────────────┼────┤├────────────┼────┤├────────────┼────┤ │ і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 │ └────────────┴────┘└────────────┴────┘└────────────┴────┘ f = /b·/c v /a·b v a·c·d. Таблиця 2.4.4 ┌──────────┬────┐ │ Номер │ │ │імпліканти│abcd│ ├──────────┼────┤ │ і0 │0-0-│ │ і1 │01--│ │ і2 │1010│ └──────────┴────┘ При записі методом Мак-Класкі функція буде мати вигляд табл. 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 ┌────────────┬─────┐┌────────────┬─────┐┌────────────┬─────┐ │Порівнюються│ ││Порівнюються│ ││Порівнюються│ │ ├────────────┼─────┤├────────────┼─────┤├────────────┼─────┤ │ і0 │0-0- ││ і0 │0-0- ││ і1 │01-- │ │ і1 │01-- ││ і2 │1010 ││ і2 │1010 │ ├────────────┼─────┤├────────────┼─────┤├────────────┼─────┤ │ │010 -││ │x0x0 ││ │xx10 │ │ Результат ├─────┤│ Результат ├─────┤│ Результат ├─────┤ │ │немає││ │немає││ │немає│ ├────────────┼─────┤├────────────┼─────┤├────────────┼─────┤ │ Терм │немає││ Терм │немає││ Терм │немає│ └────────────┴─────┘└────────────┴─────┘└────────────┴─────┘ При записі методом Мак-Класкі функція буде мати вигляд табл. 2.4.4. Результати попарного порівняння наведені в табл. 2.4.5. Оскільки при попарному порівнянні або не формувалося жодного символу "x", або їх формувалося більше ніж один, то в даному прикладі сполучних термів не буде. Наведений приклад ілюструється картою Карно (рис. 2.4.9). │ │┌───c──┐ ┌───c──┐ ┌──c───┐ ╔╪══╦═╪╦═══╦══╗ ╔═══╦═══╦═══╦══╗ ╔═══╦══╦══╦═══╗ ║│ ║ │║ ║ ║ ║┌──╫──┐║ ║ ║ ║┌──╫─┐║ ║ ║ ║│1 ║1│║ ║ ║ ║│1 ║ 1│║ ║ ║ ║│1 ║1│║ ║ ║ ║└─0╫─1║ 3║ 2║ ║│ 0║ 1║ 3║ 2║ ║│ 0║ 1║ 3║ 2║ ╠═══╬══╬═══╬══╣─┐ ╠╪══╬══╪╬═══╬══╣─┐ ╠╪══╬═╪╬══╬═══╣─┐ ║┌──╫──╫───╫─┐║ │ ║│ ║ │║┌─┐║ ║ │ ║╟──╫─┼╫──╫──┐║ │ ║│1 ║1 ║ 1 ║1│║ │ ║│1 ║ 1│║│1│║1 ║ │ ║║1 ║1│║1 ║ 1│║ │ ║└─4╫─5╫──7╫─6║ │ ║└─4║──5║│ 7║ 6║ │ ║╚═4╬═5╫─7╫──6║ │ ┌─╠═══╬══╬═══╬══╣ b ┌─╠═══╬═══╬╪═╪╬══╣ b ┌─╠═══╬══╬══╬═══╣ b │ ║ ║ ║┌─┐║ ║ │ │ ║ ║ ║│ │║ ║ │ │ ║ ║ ║ ║ ║ │ │ ║ ║ ║│1│║ ║ │ │ ║ ║ ║│1│║ ║ │ │ ║ ║ ║ ║ ║ │ │ ║ C║ D║│ F║ E║ │ │ ║ C║ D║└─F║ E║ │ │ ║ C║ D║ F║ E║ │ a ╠═══╬══╬╪═╪╬══╣─┘ a ╠═══╬═══╬═══╬══╣─┘ a ╠═══╬══╬══╬═══╣─┘ │ ║┌──╫─┐║│ │║ ║ │ ║ ║┌──╫──┐║ ║ │ ║ ║ ║ ║┌─┐║ │ ║│1 ║1│║│1│║ ║ │ ║ 1 ║│1 ║ 1│║ ║ │ ║ ║ ║ ║│1│║ │ ║│ 8║ 9║└─B║ A║ │ ║ 8║└─9╫──B║ A║ │ ║ 8║ 9║ B║└─A║ └─╚╪══╩═╪╩═══╩══╝ └─╚═══╩═══╩═══╩══╝ └─╚═══╩══╩══╩═══╝ └──d───┘ └───d───┘ └──d──┘ Задана функція Сполучні терми Задана функція Рис. 2.4.8 Рис. 2.4.9