Виконання роботи
1. Побудова простих імплікант
Випишемо до графи І таблиці 2.2.2 усі набори, на яких функція f обертається в 1. Для виконання алгоритму їх зручно виписати розбитими на групи у відповідності з кількістю одиничних компонент у наборах (колонка Код у графі І табл.. 2.2.2). Оскільки мінімізуються (склеюються) лише набори, які відрізняються в одній компоненті, то для того, щоб провести всі склеювання по одній змінній, досить продивитися всі можливі пари наборів, які входять до двох сусідніх груп.
Результати склеювання наборів із графи І розмістимо у графі ІІ. Набори із графи І, що прийняли участь у склеюваннях, позначимо знаком @. У графі ІІ набори вже автоматично розбиваються на групи за кількістю одиниць.
До створених наборів знову застосовуємо операцію склеювання. Клеяться пари наборів, які мають риску на однакових місцях і відрізняються однією змінною.
В отриманій таблиці знаходяться всі імпліканти функції, які мають вигляд кон’юнкцій. Простими будуть лише ті з них, які не мають позначки +.
Таблиця 2.2.2
I |
II |
III |
||||||||
abcde Код |
П |
У |
С |
abcde Код |
П |
У |
С |
abcde Код |
П |
У |
000010 |
A0 |
+ |
A1B0 |
0010- |
K0 |
@ |
K1L1 |
010- - |
G0 |
@ |
00100 |
A1 |
+ |
A2B1 |
0100- |
K1 |
+ |
L6M1 |
-101- |
F0 |
@ |
01000 |
A2 |
+ |
A0B2 |
0-010 |
K2 |
@ |
L1M3 |
-101- |
F0 |
|
00101 |
B0 |
+ |
B1C0 |
010-1 |
L0 |
@ |
M2N0 |
1- -11 |
H0 |
@ |
01001 |
B1 |
+ |
B2C0 |
0101- |
L1 |
+ |
M0N1 |
1- -11 |
H0 |
|
01010 |
B2 |
+ |
B0C1 |
0-101 |
L2 |
@ |
|
|
|
|
10001 |
B3 |
+ |
B1C1 |
01-01 |
L3 |
@ |
|
|
|
|
10100 |
B4 |
@ |
B2C2 |
01-10 |
L4 |
@ |
|
|
|
|
01011 |
C0 |
+ |
B3C3 |
100-1 |
L5 |
@ |
|
|
|
|
01101 |
C1 |
+ |
B2C4 |
-1010 |
L6 |
+ |
|
|
|
|
01110 |
C2 |
+ |
C3D0 |
10-11 |
M0 |
+ |
|
|
|
|
10011 |
C3 |
+ |
C0D1 |
-1011 |
M1 |
+ |
|
|
|
|
11010 |
C4 |
+ |
C3D1 |
1-011 |
M2 |
+ |
|
|
|
|
10111 |
D0 |
+ |
C4D1 |
1101- |
M3 |
+ |
|
|
|
|
11011 |
D1 |
+ |
C1D2 |
-1101 |
M4 |
@ |
|
|
|
|
11101 |
D2 |
+ |
D0E0 |
1-111 |
N0 |
+ |
|
|
|
|
11111 |
E0 |
+ |
D1E0 |
11-11 |
N1 |
+ |
|
|
|
|
|
|
|
D2E0 |
111-1 |
N2 |
@ |
|
|
|
|
У Таблиці 2.2.2 позначено графи :
а b c d e (Kод) - код набору
С- склеюванням яких наборів цей код утворився;
П- умовне позначення набору;
У- позначка про участь набору у склеюванні (+ , якщо так і @, якщо набір, не приймає участь у наступному склеюванні, тобто створює просту імпліканту).