Розділ 2. Використання функцій алгебри логіки та їхня мінімізація. Завдання 2.1 Визначити класи функцій алгебри логіки, до яких належить задана за допомогою таблиці 2.1.1 функція трьох змінних, і її функціональну повноту. Таблиця 2.1.1 abc f
000 0
001 1
010 0
011 1
100 0
101 1
110 0
111 0
Функція утворює ФПС (функціонально повну систему) якщо вона: 1) не зберігає константу „0”; 2) не зберігає константу „1”; 3) не є монотонною; 4) не є самодвоїстою; 5) не є лінійною.
Перевіряємо ці умови для нашої функції. 1)Константа „0”. Оскільки на нульовому наборі f (0,0,0) = 0, то функція зберігає константу „0”. Умова не виконується. 2)Константа „1”. Оскільки на одиничному наборі f (1, 1, 1) = 0 ,то ця функція не зберігає константу „1”. Умова виконується. 3)Монотонність. Таблиця 2.1.2 abc f
000 0
001 1
011 1
111 0
abc f
000 0
001 1
101 1
111 0
abc f
000 0
010 0
011 1
111 0
abc f
000 0
010 0
110 0
111 0
abc f
000 0
100 0
101 1
111 0
abc f
000 0
100 0
110 0
111 0
а б в г д е В таблиці 2.1.2 виписані шість послідовностей сусідніх наборів. Бачимо, що на послідовностях (а), (б), (в) та (д) функція не є монотонною, отже вона не монотонна. Умова виконується. 4)Самодвоїстість. Таблиця 2.1.3 abc f abc f
000 0 111 0
001 1 110 0
010 0 101 1
011 1 100 0
Оскільки на парі f (0,0,0) і f (1,1,1) (таблиця 2.1.3) функція приймає однакові значення, то функція не є самодвоїстою. Умова виконується.
5)Лінійність. Для визначення лінійності функції подамо її у вигляді полінома Жегалкіна: F=/a/bc # /abc # a/bc = (1#a)(1#b)c # (1#a)bc # a(1#b)c = c(1#a#b#ab) # (bc#abc) # (abc#ac) = (c#ac#bc#abc) # (bc#abc) # (abc#ac) = c#abc „ / ” – інверсне значеня. Оскільки функція містить добуток змінних то вона не є лінійною. Умова виконується. 7 Оскільки не виконується умова 1 (збереження константи „0”), то дана функція не утворює ФПС ФАЛ. Завдання 2.2 Мінімізувати за допомогою методу Квайна – Мак-Класкі – Петрика функцію п’яти змінних. Функцію задано за допомогою таблиці 2.2.1 Побудувати таблицю, яка ілюструє процес знаходження простих імплікант і таблицю покриття (імплікантну таблицю). За допомогою методу Петрика визначити всі мінімальні розв’язки. Кожний третій набір має невизначене значення . Відлік починається від першого згори одиничного значення функції. Таблиця 2.2.1 № набору a b c d e f
0 0 0 0 0 0 0
1 0 0 0 0 1 1(x)
2 0 0 0 1 0 1
3 0 0 0 1 1 1
4 0 0 1 0 0 0(x)
5 0 0 1 0 1 1
6 0 0 1 1 0 1
7 0 0 1 1 1 0(x)
8 0 1 0 0 0 0
9 0 1 0 0 1 0
10 0 1 0 1 0 1(x)
11 0 1 0 1 1 0
12 0 1 1 0 0 0
13 0 1 1 0 1 1(x)
14 0 1 1 1 0 0
15 0 1 1 1 1 0
16 1 0 0 0 0 0(x)
17 1 0 0 0 1 1
18 1 0 0 1 0 0
19 1 0 0 1 1 1(x)
20 1 0 1 0 0 0
21 1 0 1 0 1 1
22 1 0 1 1 0 1(x)
23 1 0 1 1 1 0
24 1 1 0 0 0 0
25 1 1 0 0 1 1(x)
26 1 1 0 1 0 0
27 1 1 0 1 1 1
28 1 1 1 0 0 1(x)
29 1 1 1 0 1 0
30 1 1 1 1 0 0
31 1 1 1 1 1 0(x)
8 Імпліканта називається простою, якщо вона є кон’юнкцією змінних і будь-яка кон’юнкція, отримана з неї шляхом викреслювання будь-яких змінних не є іпмлікантою. Побудуємо таблицю 2.2.2 яка ілюструє процес знаходження простих імплікант.Для цього в таблицю запишемо всі набори, на яких функція приймає значення „1” або „х” Таблиця 2.2.2 К П У С К П У С К П У
„К” – код набору; „П” – умовне позначення набору; „У” – позначка про участь набору у склеюванні; „С” – склеюванням яких наборів цей код утворився. В цій таблиці знаходяться всі імпліканти функції f , які мають вигляд кон’юнкцій. Простими будуть тільки ті з них, які не мають позначки „+”. Отже, простими імплікантами є кон’юнкції: abc/d/e, /a/cd/e, a/b/c/d, /ac/de, /bcd/e, abde, /a/be, /b/ce, /b/de, /a/b/c, /a/bd, a/ce. Позначимо через I1 , I2 , … , In всі прості імпліканти функції f . 9 Побудуємо таблицю покриття (таблиця 2.2.3) в якій в рядки запишемо одиничні набори функції f , а в стовпчики – прості імпліканти. Таблиця 2.2.3 abcde I1 I2 I3 I4 I5 I6 I7 I8 I9 I10 I11 I12
00010 00011 00101 00110 10001 10101 11011
*
*
*
*
*
* *
* *
* * * * * *
* *
* *
Рядок n буде покритий тоді і тільки тоді, коли до множини буде введена хоча б одна з імплікант I1 , I2 , … , In ,тобто коли диз’юнкція i1 v i2 v … v in дорівнює 1. Складемо диз’юнкцію кожного рядка імплікантної таблиці і візьмемо їхній добуток по всіх рядках. Отримаємо функцію F, яка для таблиці 2.2.3 має вигляд: f = (i2 v i10)(i7 v i8 v i10)(i4 v i7 v i9 v i11)(i5 v i10 v i11)(i3 v i8 v i9 v i12)i9(i6 v i12) = i9i10i6 v v i2i7i5i6i9 v i9i8i2i5i6 v i8i2i7i11i6i9 v i9i8i2i11i6 v i9i10i12 v i9i2i7i5i12 v i9i8i2i5i12 v i9i2i7i11i12. Отже, мінімальною ДНФ буде: f = I9 v I10 v I12 = /b/de v /a/bd v a/ce. Завдання 2.3 Мінімізувати за „1” за допомогою карт Карно функцію задану таблицею 2.2.1 Після мінімізації доповнити функції сполучними термами, підкреслити вирази для цих термів в аналітичному записі функції і позначити їх на картах Карно.
Побудуємо карту Карно (табл. 2.3.1) і проведемо склеювання Карта Карно Табл. 2.3.1 C D X 9 8
E F
B
A X
6 1 7 X 3 1 2 1
4 X 5 1 1 Х 0
C /C C /C 1C X 1D 19 X 18
1E 1F X 1B 1 1A
16 X 17
13 X 12
14
15 1 11 1 10 X
В D /B
/E E /E /E E /E A /A 10 Результати склеювання: -Клітинки 10, 13, 1B, 19 – результат a/ce, зникли 2 змінні b, d. -Клітинки 15, 11, 5, 1 – результат /b/de, зникли 2 змінні a і c. -Клітинки 6, 7, 3, 2 – результат /a/bd, зникли 2 змінні c і е. Отже результат: f = /a/bd v a/ce v /b/de Знайдемо і позначимо сполучні терми (табл. 2.3.2) : Карта Карно Табл. 2.3.2 C /C C /C 1C X 1D 19 X 18
1E 1F X 1B 1 1A
16 X 17
13 X 12
14
15 1 11 1 10 X
C D X 9 8
E F
B
A X
6 1 7 X 3 1 2 1
4 X 5 1 1 Х 0
В
D /В /E E /E /E E /E A /A Сполучними будуть терми /a/be і /a/bc. Отже, після введення сполучних термів функція набуде вигляду: f = /a/bd v /b/de v a/ce v /a/be v /a/bc. Завдання 2.4 Мінімізувати за „0” за допомогою карт Карно функції, задані таблицею 2.2.1 Після мінімізації доповнити функції сполучними термами, підкреслити вирази для цих термів в аналітичному записі функції і позначити їх на картах Карно. Побудуємо карту Карно (табл. 2.4.1) : Карта Карно Табл. 2.4.1 C /C C /C 1C X 1D 0 19 X 18 0
1E 0 1F X 1B
1A 0
16 X 17 0 13 X 12 0
14 0 15
11
10 X
C 0 D X 9 0 8 0
E 0 F 0 B 0 A X
6
7 X 3
2
4 X 5
1 Х 0 0
В
D /B /E E /E /E E /E A 11 /A Результати склеювання: -Клітинки C, D, 9, 8, E, F, B, A – результат /ab, зникли 3 змінні c, d, e. -Клітинки 1C, 1E, 16, 14, 18, 1A, 12, 10 – результат a/e, зникли 3 змінні b, c, d. -Клітинки 1C, 1D, 19, 18, C, D, 9, 8 – результат b/d, зникли 3 змінні a, c, е. -Клітинки 16, 17,13, 12 – результат a/bd, зникли 2 змінні c, e. -Клітинки 0, 1, 8, 9 – результат /a/c/d, зникли 2 змінні b, е. Оскільки склеювання проводиться за „0”, то в результаті мінімізації отримаємо диз’юнктивну нормальну форму для інверсного значення функції /f : /f = /ab v a/e v b/d v a/bd v /a/c/d. Пряме значення функції f отримується у вигляді кон’юнктивної нормальної форми: f = (a v /b)(/a v e)(/b v d)(/a v b v /d)(a v c d). Знайдемо і позначимо сполучні терми (табл. 2.4.2) : Карта Карно Табл. 2.4.2 C /C C /C 1C X 1D 0 19 X 18 0
1E 0 1F X 1B
1A 0
16 X 17 0 13 X 12 0
14 0 15
11
10 X
C 0 D X 9 0 8 0
E 0 F 0 B 0 A X
6
7 X 3
2
4 X 5
1 Х 0 0
В
D /B /E E /E /E E /E A /A Сполучними будуть терми b/e і /c/d/e. Отже після введення сполучних термів функція буде мати вигляд: /f = /ab v a/e v b/d v a/bd v /a/c/d v b/e v /c/d/e. Запишемо пряме значення функції f (разом зі сполучними термами): f = (a v /b)(/a v e)(/b v d)(/a v b v /d)(a v c d)(/b v e)(c v d v e) Таким чином кінцевий результат ми одержимо у вигляді мінімальної КНФ.
