крім А0. На перетині рядка Аi і стовпця Аj запишемо формулу переходу, яка формується таким чином: Fij=P1fij1+...+Pnfijn (n=1...N). Де fijn-формула переходу з вершини Аi у вершину Аj для n-о ГСА. Наприклад, формула переходу А0А1 буде мати вигляд F0,1=x1p1p2p3+ p1p2p3+ +p1p2p3. У результаті ми отримаємо об'єднану МСА М0 (табл.1.7). Ми маємо можливість мінімізувати формули переходу таким чином: розглядаючи ГСА Г0 як ГСА Гn, ми підставляємо певний набір Pn=1, при цьому змнн p1..pq не змінюють своїх значень під час проходу по ГСА. Таким чином, якщо у вершину Аi перехід завжди здійснюється при незмінному значенні pq, то це значення pq в рядку Аi замінимо на “1", а його інверсію на “0". Наприклад, у вершину А3 перехід здійснюється при незмінному значенні p1 і p2, отже в рядку А3 p1 і p2 замінимо на “1", а p1 і p2 на “0". У результаті отримаємо формули F3,4=p3, F3,11=p3. Керуючись вищенаведеним методом, отримаємо мінімізовану МСА М0 (табл.1.8).
По таблиці складемо формули переходу для об'єднаної ГСА Г0. Формулою переходу будемо називати слдуюче вираження: AiFi,1А1+..+Fi,kАk, де Fi,j- відповідна формула переходу з мінімізованої МСА. У нашому випадку отримаємо слдуючу систему формул:
A0x1p1p2p3A1+p1p2p3A1+p1p2p3A1+x1x2p1p2p3A2+x1x2p1p2p3A3+
+x1p1p2p3-A8+x1p1p2p3A13+p1p2p3A14
A1p1p3A2-+p1p3A6+p1p3A7
A2p1p2p3A6+p1p2p3A18+p1p2p3A21
A3p3A4+p3A11
A4A5
A5А6
Таблиця 1.7
Об`днана МСА Мo |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
A11 |
A12 |
A13 |
A14 |
A15 |
A16 |
A17 |
A18 |
A19 |
A20 |
A21 |
A22 |
Ak
A0 | _ _ _ _
x1p1p2p3+
_ _
+p1p2p3+
_ _
+p1p2p3 |
_ _ _ _
x1x2p1p2p3 | _ _ _
x1x2p1p2p3 | _ _
x1p1p2p3 | _
x1p1p2p3 | _ _
p1p2p3
A1 |
_ _ _
p1p2p3 | _ _
p1p2p3 | _ _
p1p2p3
A2 |
_ _ _
p1p2p3 | _
p1p2p3 | _ _
p1p2p3
A3 |
_ _ _
p1p2p3 | _ _
p1p2p3
A4 |
_ _ _
p1p2p3
A5 |
_ _ _
p1p2p3
A6 |
_
p1p2p3 | _ _ _
p1p2p3 | _ _
p1p2p3 | _ _
p1p2p3 | _ _
p1p2p3
A7 |
_ _
x3p1p2p3 | _ _ _
p1p2p3 | _ _ _
x3p1p2p3
A8 | _
x2p1p2p3 | _ _ _
p1p2p3+
_ _
+x2p1p2p3
A9 |
_
p1p2p3 | _ _
p1p2p3
A10 |
_ _
p1p2p3
A11 |
_ _
p1p2p3
A12 |
_ _
p1p2p3 | _ _
p1p2p3
A13 |
_
p1p2p3 | _ _
p1p2p3
A14 |
_ _ _
x1p1p2p3 | _ _
x1p1p2p3
A15 |
_ _
x3p1p2p3 | _ _ _
x3p1p2p3
A16 |
_ _
p1p2p3
A17 |
_ _
p1p2p3 | _
p1p2p3
A18 |
_
p1p2p3
A19 |
_ _ _
x1x2p1p2p3 |
_ _
x1x2p1p2p3 | _ _ _
x1p1p2p3
A20 |
_ _
p1p2p3
A21 |
_ _
p1p2p3
A22 |
_ _
p1p2p3
Таблиця 1.8
Об`днана мнмзована МСА Мo |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
A11 |
A12 |
A13 |
A14 |
A15 |
A16 |
A17 |
A18 |
A19 |
A20 |
A21 |
A22 |
Ak
A0 | _ _ _ _
x1p1p2p3+
_ _
+p1p2p3+
_ _
+p1p2p3 |
_ _ _ _
x1x2p1p2p3 | _ _ _
x1x2p1p2p3 | _ _
x1p1p2p3 | _
x1p1p2p3 | _ _
p1p2p3
A1 |
_ _
p1p3 | _
p1p3 | _
p1p3
A2 |
_ _ _
p1p2p3 | _
p1p2p3 | _ _
p1p2p3
A3 |
_
p3 |
p3
A4 |
1
A5 |
1
A6 |
_
p1p2p3 | _ _ _
p1p2p3 | _ _
p1p2p3 | _ _
p1p2p3 | _ _
p1p2p3
A7 |
x3p3 | _
p3 | _
x3p3
A8 |
x2p2p3 | _ _
p2p3+
_
+x2p2p3
A9 |
p2 | _
p2
A10 |
1
A11 |
1
A12 |
_
p2p3 | _
p2p3
A13 |
p3 | _
p3
A14 |
_
x1 |
x1
A15 |
x3 | _
x3
A16 |
1
A17 |
_ _
p1p2p3 | _
p1p2p3
A18 |
1
A19 |
_
x1x2 |
x1x2 | _
x1
A20 |
1
A21 |
1
A22 |
1
A6p1p2p3A2+p1p2p3A7+p1p2p3A121p2p3A19+p1p2p3Ak
A7x3p3A6+p3A8+x3p3A9
A8x2p2p3A17+p2p3Ak+x2p2p3Ak
A9p2-A8+p2A10
A10A3
A11Ak
A12p2p3A22+p2p3A13
A13p3A9+p3Ak
A14-x1A15+x1A16
A15x3A6+x3Ak
A16A12
A17p1p2p3A2-+p1p2p3A6
A18Ak
A19x1x2A2+x1x2A20+x1A21
A20-A17
A21Ak
A22Ak
При побудові системи дужкових формул переходу необхідно кожну формулу привести до вигляду Аx1+Вx1, де А і В -деякі вирази, а x1 і x1-логічн умови переходу. Формули переходу для вершин А3, А4, А5, А9, А10, А11, А13, А14, А15, А16, А18, А20, А21, А22 вже є елементарними (розкладеними), а в інших є вирази виду Аnxj(А) +xjpi(В). Тут pi відповідає чекаючій вершині (мал.1.6). Подібних вершин в об'єднанй ГСА бути не повинно. Для їх усунення скористаємося слдуючим правилом: додавання виразу [PqАn] не змінить формулу, якщо набір Pq не використовується для кодування ГСА або вершина Аn вдсутня в ГСА з кодом Pq. Таким чином, додаючи допоміжні набори, ми отримаємо можливість за допомогою елементарних перетворень звести формули до необхідного вигляду. Наприклад, формула A8x2p2p3A17+p2p3Ak+x2p2p3A спрощується таким чином A8=p3(x2p2A17+x2p2Ak)+p3p2Ak=p3p2(x2A17+x2Ak)+p3p2Ak=
1 Xj 0
Pi 0
1
Мал.1.6 Приклад чекаючо вершини Pi
=[p3p2(x2A17+x2Ak)]+p3p2(x2A17+x2Ak)+p3p2Ak+[p3p2Ak]=p2Ak+p2(x2A17+x2Ak). Тут вершина А8 не зустрчаться у ГСА ,в кодах яких присутн комбнац p3p2 p3p2. Нижче наведено розклад усх неелементарних формул переходу.
A0=p1(p2p3A1)+p1(x1p2p3A1+p2p3A1+x1x2p2p3-A2+x1x2p2p3A3-+
+x1p2p3A8+x1p2p3A13+p2p3A14)=p1(p2p3A1)+[p1p2p3A1]+
+p1(p2(x1p3A8+x1p3A13+p3A14)+p2(x1p3A1+p3A1+x1x2p3A2+
+x1x2p3A3-))=p1(p2A1)+[p1p2A1]+p1(p2(p3(x1A8+x1A13)+p3A14)+
+p2(p3(x1A1+x1x2A3+x1x2A23A1))= p1A1+p1(p2(p3( x1A8+
+x1A13)+p3A14)+p2(p3(x1A1+x1(x2A3+x2A2))+p3A1-))
A1=p1-(p3A7+p3A2)+p1p3A6+[p1p3A6]= p1-(p3A7+p3A2)+p1A6
A2=p1(p2p3A21)+p1(p2p3A6+p2p3A18)= p1(p2p3A21)+[p1p2p3A21]+
+p1-(p2p3A6+[p2p3A6]+p23A18+[p3p2A18])=p1(p2A21)+p1(p3A6+
+p3A18)=p1(p2A21)+[p1p2A21]+p1(p3A6+p3A18)=p1A21+p1(p3A6+
+p3A18)
A6=p1(p2p3A19)+[p1p2p3A19]+p1(p2p3A2+p2p3A7+p2p3A12+p2p3Ak)=
=p1p2A19+[p1p2A19]+p1(p2(p3A2+p3Ak)+p2(p3A7+p3A121A19+
+p1(p2(p3A2+p3Akp2(p3A7+p3A12))
A7=p3(x3A6+x3A9)+p3A8
A8=p3(x2p2A17+x2p2Ak)+p3p2Ak=p3p2(x2A17+x2Ak)+p3p2Ak=
=[p3p2(x2A17+x2Ak)]+p3p2(x2A17+x2Ak)+p3p2Ak+[p3p2Ak]=p2Ak+
+p2(x2A17+x2Ak)
A12=p2p3A22+p2p3A13+[p2p3A22]+[p2p3A13]=p3A22+p3A13
A17=p1p2p3A2+[p1p2p3A2]+p1p2p3A6+[p1p2p3A6-]=p1p2A2+[p1p2A2]+
+p1p3A6+[p1p3A6]=p1A2+p1A6-
A19=x1(x2A2+x2A20)+x1A21
Об'єднану ГСА Г0 (мал.1.7) побудуємо відповідно до формул переходу, замінюючи кожну мітку Аi відповідною операторною вершиною Yt, а кожний вираз Xi і Pj відповідними умовними вершинами.