Rotation of™

198

5,7(2,b) oznacza w istocie poÅ‚Ä…czenie jedynek 5 i 7 pochodzÄ…cych wyÅ‚Ä…cznie z funkcji b (yg) i utworzenie dla tej funkcji implikantu 5,7(2)    - punkt 2.2 algorytmu. Jedynki 5 i 7 z funkcji a oraz c

poÅ‚Ä…czone nie zostaÅ‚y, gdyż poÅ‚Ä…czone być nie mogÅ‚y, bo każda z nich pochodzi z innej funkcji (5 z a, 7 z c). StÄ…d jedynki 5(a,b) i 7(b,c), przy rozważanym sklejaniu, nie zostaÅ‚y oznaczone symbolem V. Symbol ten, oznaczajÄ…cy, że danÄ… jedynkÄ™ (dany implikant) udaÅ‚o siÄ™ skleić z innÄ… jedynkÄ… czy też implikantem, można postawić tylko wtedy, gdy sklejenie miaÅ‚o miejsce w przypadku wszystkich funkcji do których dana jedynka (dany implikant) należy. 2 kolei, sklejenie np. 2(a,c) z 6(a,c) i uzyskanie implikantu 2,6(4,a.c) oznacza, że jedynki 2 i 6 zostaÅ‚y sklejone zarówno w przypadku funkcji a (uzyskano implikant 2,6(4) jak i funkcji c (uzyskano identyczny implikant). Implikant 2,6(4,a.c), jest zatem implikantem funkcji bÄ™dÄ…cej iloczynem obu funkcji a i c. Należy wiÄ™c przy obu jedynkach 2(a,c) i 6 (a,c) postawić znak V (punkt 2.3. a algorytmu). Natomiast w przypadku pary 5(a,b) i 13(a,b,c) sklejeniu podlegajÄ… jedynki 5 i 13 ale tylko pochodzÄ…ce z funkcji a i b. Zatem uzyskany implikant 5,13(8,a,b) jest implikantem funkcji bÄ™dÄ…cej iloczynem a i b. Jedynka 13 z funkcji c żadnemu sklejeniu nie podlega -stÄ…d jedynka 13 jako caÅ‚ość tzn. 13(a,b,c) nie jest oznaczona znakiem V, podczas, gdy jedynka 5(a,b)    - jest oznaczona (punkt 2.3.b

algorytmu).

W rezultacie znalezione zostały następujące proste implikanty funkcji i ich iloczynów:

f_a    :    6,14 (8,a);

f_b    :    5,7 (2,b) ;

f_c    : 6.7 (1,c) ; 7,15 (8,c) ; 13,15 (2,c) ;

^fa°^fb    ^:    14 (a>b) : 5’¹³ (8'^a-^b> :    (3.85)

f_a»f_c    :    2,6(4.a.c) ;

V^fc    ^{:    7tblC) :}

f_ ° f ^ ° f _ :    13 (a, b, c).

a. d c

Minimalny zestaw prostych implikantów nakrywajÄ…cych wszystkie jedynki funkcji f_&, f^, f_c znajduje siÄ™, analogicznie jak w przypadku minimalizacji jednej funkcji, przy pomocy tablicy Quine'a (rys. 3.29a). Przy tworzeniu tej tablicy należy pamiÄ™tać, że fakt zawierania siÄ™ jedynki w danym implikancie można zaznaczyć jedynie wtedy, gdy jest to implikant tej samej, co jedynka, funkcji lub jej iloczynu z innymi

funkcjami.

W tablicy z rys. 3.29a wystÄ™pujÄ… trzy zasadnicze proste implikanty: I4(a,b); 2.6(a,c) ; 5,13(8,a.b). UsuwajÄ…c je oraz odpowiadajÄ…ce im jedynki uzyskuje sie zredukowanÄ… tablicÄ™ przedstawionÄ… na rys. 3.29 b. Do tablicy tej zastosować można reguÅ‚Ä™ dominacji wierszy.

Uzyskuje siÄ™:

7(b,c) Å‚ 5,7(2,b),

7(b,c) Å‚ 6,7( 1,c),    (3. 87a)’

13,15(2,c) Å‚ 13(a,b,c).

Usuwając wiersze zdominowane uzyskuje się tablicę z ryą. 3.29c. Stosując, z kolei, regułę dominacji kolumn

15 s 13    .    7 s 7,    (3.87b)‘

CC    CD

i usuwajÄ…c kolumny dominujÄ…ce otrzymujemy tablicÄ™ z rys. 3.29d. Wynika z niej, że do wygenerowanych uprzednio trzech zasadniczych prostych impl ikantów należy doÅ‚Ä…czyć jeszcze dwa implikanty: 7    (b.c) f. luf, 15

(2,c).

Ostatecznie, minimalny zestaw prostych implikantów nakrywających wszystkie jedynki rozważanego zespołu funkcji jest następujący

14(a,b); 2,6(4,a.c); 5,13(8,a.b); 7(b,c);    13.15(2,c)    (3.88)

Z formy opisu poszczególnych prostych implikantów Å‚atwo odczytać, które z nich powinny być użyte do realizacji kolejnych funkcji |sposób dekodowania opisów typu (3.S8) na elementarne iloczyny zmiennych binarnych, identyczny jak w (3.55)1.

SÄ… to:    ¹

^a) dla funkcji f_a - implikanty 14; 2,6(4); 5.13(8); stÄ…d

^yl " falXj.X2.X3.X4) - 14 ♦ 2.6(4) + 5,13(8) =

- 1110 + 0010 + ^101 =

(3.89a)

^X1^X2^X3^X4 * ^xl^x3^x4 * X2^X3X4.