Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методичні вказівки щодо використання функцій алгебри логіки та мінімізації цих функцій у базисі Буля.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Методичні вказівки
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Частина 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
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора