Контрольні питання
1. Сформулювати визначення ДДНФ системи перемикальних функцій.
2. Назвати етапи мінімізації системи функцій.
3. Як виконуються операції склеювання і поглинання за мінімізації систем перемикальних функцій?
4. У чому сутність проблеми мінімізації систем перемикальних функцій?
5. Як побудувати операторні форми подання перемикальних функцій?
Література
1. Жабін В. І., Жуков І. А., Клименко І. А., Ткаченко В. В. Прикладна теорія цифрових автоматів: Навч. Посібник. – К.: Книжкове вид-во НАУ, 2007. – 364 с.
2. Прикладная теория цифровых автоматов / К.Г. Самофалов, А.М. Романкевич, В.Н. Валуйский и др. – К.: Вища шк., 1987. – 375 с.
3. Савельев А.Я. Арифметические и логические основы цифровых автоматов: Учебник. – М.: Высш. шк., 1980. – 255 с.
4. Самофалов К.Г., Корнейчук В.И., Тарасенко В.П. Цифровые ЭВМ: Теория и проектирование. – К.: Вища шк., 1989. – 427 с.
Лабораторна робота 4
Мінімізація частково визначених функцій
Мета роботи: оволодіння методами мінімізації частково визначених
функцій та усунення непередбачених короткочасних
сигналів на виходах схем, дослідження параметрів
схем.
Теоретичні відомості
У реальних системах можливі випадки, коли не всі набори змінних подаються на входи комбінаційної схеми, тобто існують заборонені вхідні комбінації змінних. На таких наборах перемикальна функція вважається невизначеною, що дає додаткові можливості для спрощення комбінаційної схеми.
У таблиці істинності невизначені значення функції позначаються довільним символом, відмінним від 0 і 1, наприклад – прочерком.
Мінімізацію частково визначених функцій можна здійснювати будь-яким з наведених вище методів мінімізації. Для забезпечення найефективнішої мінімізації доцільно провести до визначення перемикальної функції на заборонених наборах таким чином, щоб спростити функцію за рахунок більших можливостей склеювання.
Мінімізація частково визначених функцій методом Вейча
Під час використання метода Вейча прочерки розглядають як одиниці в тих випадках, коли це приводить до збільшення розміру прямокутника, що відповідає імпліканті. В протилежному випадку прочерки розглядаються як нулі.
Приклад. Виконати мінімізацію перемикальної функції, заданої діаграмою Вейча (рис. 4. 1).
Для визначення мінімальної форми запису функції замінюємо певні прочерки одиницями для збільшення розміру прямокутників, тобто отримання імплікант з меншою кількістю букв. Значення функції на наборі 1101, який не увійшов в прямокутники, вважаємо рівним нулю.
Диз’юнкція визначених простих імплікант дає МДНФ до визначеної перемикальної функції
.
Мінімізація частково визначених функцій аналітичними методами
Під час використання аналітичних методів, таких як методи Квайна та Квайна – Мак-Класкі, виконуються ті самі етапи мінімізації, що й для повністю визначених функцій.
Особливістю мінімізації частково визначених функцій в диз’юнктивних формах булевої алгебри складається з того,
Рис. 4. 1. Діаграма Вейча що перед початком мінімізації у ДДНФ
перемикальної функції вводять усі конституенти заборонених наборів, тобто довизначають функцію на цих наборах одиничним значенням.
Далі виконують стандартні процедури мінімізації, але під час побудови таблиці покриття конституенти заборонених наборів не включають у заголовки стовпців таблиці покриття.
Приклад. Виконати мінімізацію частково визначеної перемикальної функції, що задана таблицею істинності (табл. 4. 1), методом Квайна.
Таблиця 4. 1
-
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1
1
0
−
−
−
1
−
Без урахування наборів, на яких функція невизначена, маємо
.
Після доповнення конституентами одиниці, що відповідають забороненим наборам (помічені зірочками), аналітичний запис функції приймає вигляд
.
Для наглядності процесу мінімізації конституенти та імпліканти записуємо стовпцями. У дужках для конституент вказуємо їх номери, а для імплікант – номери конституент, що склеювалися. Терми, що поглинаються, викреслюємо.
(закреслюються перші два стовпці)
Виконавши всі можливі склеювання та поглинання, одержуємо СДНФ заданої перемикальної функції, що довизначена на заборонених наборах:
.
Але таке довизначення перемикальної функції на заборонених наборах можливо не є оптимальним. Для перевірки цього будуємо таблицю покриття (табл. 4. 2), в яку включаємо тільки ті конституенти одиниці, котрі відповідають наперед визначеним одиничним значенням заданої перемикальної функції.
Таблиця 4. 2
-
Імпліканти
Конституенти
+
+
+
+
Виходячи з таблиці покриття знаходимо ТДНФ перемикальної функції, яка є її мінімальною МДНФ:
.
Мінімізація систем частково визначених функцій
Під час мінімізації систем частково визначених функцій використовується такий саме підхід, як і під час мінімізації окремих частково визначених функцій. На заборонених наборах значення функцій вважається одиничним, але на етапі вибору конституенти, що відповідають забороненим наборам, не включаються в таблицю покриття.
Приклад. Виконати мінімізацію системи частково визначених перемикальних функцій, заданих таблицею істинності (табл. 4. 3), методом Квайна – Мак-Класкі.
Таблиця 4. 3
-
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
−
1
0
1
1
0
0
−
1
1
0
1
−
−
0
1
−
0
0
1
1
1
0
1
Виписуємо 0-куби, що відповідають забороненим наборам і наборам, на яких функції приймають одиничне значення. При цьому позначаємо належність конституент до заданих функцій. Виконуємо всі можливі склеювання і поглинання:
000(1, 2, 3) X00(1, 2, 3)
− − − − − − − X01(2)
001(1, 2) X11(1, 2, 3) X0X(2)
100(1, 2, 3) − − − − − − − X0X(2)
= − −
− − − − −
= 0X1(1,
2)
= XX1(2)
011(1, 2, 3) 1X1(2, 3) XX1(2)
101(2, 3) − − − − − − −
− − − − − − − 00X(1, 2)
111(1, 2, 3) 10X(2, 3)
X00(1, 2, 3)
X11(1, 2, 3)
0X1(1, 2)
Z = 1X1(2, 3)
00X(1, 2)
10X(2, 3)
X0X(2)
XX1(2)
Складаємо таблицю покриття (табл. 4. 4), на підставі якої знаходимо форми функцій вихідної системи:
Таблиця 4. 4
Імпліканти |
Конституенти |
||||||||||
|
|
|
|||||||||
001 |
011 |
100 |
000 |
001 |
011 |
111 |
011 |
100 |
101 |
111 |
|
00х (1, 2) |
+ |
|
|
+ |
+ |
|
|
|
|
|
|
х00 (1, 2,3) |
|
|
+ |
+ |
|
|
|
|
+ |
|
|
0х1 (1, 2) |
+ |
+ |
|
+ |
+ |
|
|
|
|
|
|
х11 (1, 2, 3) |
|
+ |
|
|
|
+ |
+ |
+ |
|
|
|
10х (2, 3) |
|
|
|
|
|
|
|
|
+ |
+ |
|
1х1 (2, 3) |
|
|
|
|
|
|
+ |
|
|
+ |
+ |
х0х (2) |
|
|
|
+ |
+ |
|
|
|
|
|
|
хх1 (2) |
|
|
|
|
+ |
+ |
+ |
|
|
|
|
Очевидно,
що ядро функції
системи функцій складають прості
імпліканти:
(1,
2, 3) і
(1,
2, 3). Оскільки ядро функції не покриває
всіх стовпців таблиці покриття, то
складаємо тупикові функції:
;
.
Можна скласти ще кілька тупикових функцій, але всі вони за складністю рівнозначні. За МДНФ функції системи функцій приймаємо першу тупикову функцію. Тоді форми функцій вихідної системи будуть мати вигляд:
;
;
.
Аналогічно
знаходимо мінімальні значення заперечень
функцій
і
.
Виписуємо 0-куби, що відповідають забороненим наборам і наборам, на яких функції приймають нульові значення. При цьому позначаємо належність конституент до заданих функцій. Виконуємо всі можливі склеювання і поглинання:
000 (1,3) 0Х0(1,3) 0Х0 (1,3)
---------- 00Х (3) 00Х (3)
001 (3) ----------- Х10 (1,2, 3)
010 (1, 2, 3) Х10 (1, 2, 3) Z = 10Х (2)
К0 = 100 (2) К1 = 10Х (2) 1Х1 (1)
-------------- ---------- 11Х (1)
101 (1, 2) 1Х1 (1)
110 (1, 2, 3) 11Х (1)
111 (1)
Складаємо таблицю покриття (табл. 4. 5). На підставі якої знаходимо форми заперечень функцій вихідної системи:
Таблиця 4. 5
Імпліканти |
Конституенти |
||||||||
|
|
||||||||
000 |
010 |
101 |
110 |
111 |
010 |
100 |
101 |
110 |
|
00х (3) |
|
|
|
|
|
|
|
|
|
0х0 (1, 3) |
+ |
+ |
|
|
|
|
|
|
|
х10(1, 2, 3) |
|
+ |
|
+ |
|
+ |
|
|
+ |
10х (2) |
|
|
|
|
|
|
+ |
+ |
|
1х1 (1) |
|
|
+ |
|
+ |
|
|
|
|
11х (1) |
|
|
|
+ |
+ |
|
|
|
|
Таблиця 4. 5 (продовження)
Імпліканти |
Конституенти |
|||
|
||||
000 |
001 |
010 |
110 |
|
00х (3) |
+ |
+ |
|
|
0х0 (1, 3) |
+ |
|
+ |
|
х10(1, 2, 3) |
|
|
+ |
+ |
10х (2) |
|
|
|
|
1х1 (1) |
|
|
|
|
11х (1) |
|
|
|
|
Ядро
заперечення функції
системи функцій складають імпліканти:
;
;
;
та
.
Так як ядро функції покриває усі стовпці
таблиці покриття, то воно і є її МДНФ
.
Форми заперечень функцій мають вигляд:
;
;
.
Виходячи із МДНФ функцій за допомогою правила де Моргана послідовно одержимо чотири нормальні форми:
І
/ АБО
І
НЕ / І-НЕ
АБО
/ І-НЕ
;
АБО-НЕ / АБО
І
/ АБО
І-НЕ
/ І-НЕ
АБО
/ І-НЕ
;
АБО-НЕ / АБО
І
/ АБО
І-НЕ
/ І-НЕ
АБО
/ І-НЕ
.
АБО-НЕ / АБО
На основі МДНФ заперечень заданих функцій отримаємо ще чотири нормальні форми:
І
/ АБО-НЕ
І-НЕ
/ І
АБО
/ І
;
АБО-НЕ / АБО-НЕ
І
/ АБО-НЕ
І-НЕ
/ І
АБО
/ І
;
АБО НЕ / АБО-НЕ
І
/ АБО-НЕ
І-НЕ
/ І
АБО
/ І
.
АБО-НЕ / АБО-НЕ
Побудуємо комбінаційну схему заданої системи функцій, наприклад, на логічних елементах 2АБО-НЕ та 2І.
На даних логічних елементах можна реалізувати дві нормальні форми: АБО-НЕ / АБО-НЕ
;
;
;
і І
/АБО-НЕ
;
;
.
Виходячи з цього отримаємо операторні форми:
;
;
.
;
;
.
За отриманими операторними формами побудуємо комбінаційні схеми (рис. 4.2 і рис. 4. 3).
Рис. 4. 2. Комбінаційна схема системи функцій, побудована на
логічних елементах 2АБО-НЕ