Розділ 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
К
П
У
С
К
П
У
С
К
П
У

00001
00010
00100
10000
a0
a1
a2
a3
+
+
+
+
a0b0
a0b1
a0b4
a1b0
a1b2
a1b3
a2b1
a2b2
a3b4
000-1
00-01
-0001
0001-
00-01
0-010
0010-
001-0
1000-
f0
f1
f2
f3
f4
f5
f6
f7
f8
+
+
+
+
+
+
+
f0g2
f0g7
f1g0
f1g8
f2g1
f2g4
f3g5
f4g0
f6g5
f7g2
00--1
-00-1
00--1
-0-01
-00-1
-0-01
00-1-
00-1-
001--
001--
k0
k1
k2
k3
k4
k5
k6
k7
k8
k9
+
+
+
+
+

00011
00101
00110
01010
10001
b0
b1
b2
b3
b4
+
+
+
+
+
b0c0
b0c2
b1c0
b1c1
b1c3
b2c0
b2c4
b4c2
b4c3
b4c5

00-11
-0011
001-1
0-101
-0101
0011-
-0110
100-1
10-01
1-001
g0
g1
g2
g3
g4
g5
g6
g7
g8
g9
+
+
+
+
+
+
+
+
g7h1
g9h0
1-0-1
1-0-1

+

00111
01101
10011
10101
10110
11001
11100
c0
c1
c2
c3
c4
c5
c6
+
+
+
+
+
+
c2d0
c5d0
1-011
110-1
h0
h1
+
+





11011
d0
+
d0e0
11-11
k0






11111
e0
+










„К” – код набору; „П” – умовне позначення набору; „У” – позначка про участь набору у склеюванні; „С” – склеюванням яких наборів цей код утворився.
В цій таблиці знаходяться всі імпліканти функції 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)
Таким чином кінцевий результат ми одержимо у вигляді мінімальної КНФ.

12