Rotation of˜

19S

opisywaniu poszczególnych funkcji takimi wyrażeniami, które mają możliwie dużą liczbę części wspólnych.

W przypadku NPS funkcji zasada ta jest Å‚atwa do praktycznego wykorzystania. Elementami NPS funkcji sÄ… iloczyny literałów opisujÄ…ce poszczególne proste implikanty. Jeżeli zależy nam na wyrażeniach zawierajÄ…cych możliwie duże części wspólne, należy uwzglÄ™dnić części wspólne implikantów różnych funkcji, tzn. proste implikanty iloczynów poszczególnych funkcji. Minimalnego zbioru prostych implikantów nakrywajÄ…cych jedynki wszystkich funkcji poszukuje siÄ™ wówczas wÅ›ród prostych implikantów funkcji i prostych implikantów wszystkich kombinacji iloczynów funkcji.

Zbiór wszystkich prostych implikantów dla zespoÅ‚u funkcji można okreÅ›lić posÅ‚ugujÄ…c siÄ™ tablicami Karnaugha (dotyczy to raczej prostszych przypadków), bÄ…dź też zmodyfikowanÄ… wersjÄ… Etapu I metody Quine’a-McCluskey’a. Ta ostatnia metoda jest znacznie bardziej uniwersalna, gdyż może być stosowana do dowolnie zÅ‚ożonych zespołów funkcji. Ona też zostanie omówiona jako pierwsza. Wykorzystany do tego bÄ™dzie poniższy przykÅ‚ad.

Przykład 3.23 [41

Rozpatrywany jest zespół trzech funkcji przełączających zapisanych dziesiętnie

yj = fa*^xi•^x2'^x3-*4) ^= £(2,5,6,13,14),	(3.85a)
y2 = fb(xrx2,x3,x4) = £(5,7,13,14),	(3.85b)
^y3 ^= ('c(^xr^x2-^x3-^xa^) = £(2.6,7,13.15)	(3.85c)

Algorytm Etapu I metody Quine’a-McCluske’ ya dla minimalizacji zespołów funkcj i:

1. DziesiÄ™tne reprezentacje zespołów wartoÅ›ci zmiennych dla których funkcje sÄ… równe jednoÅ›ci lub nieokreÅ›lone należy podzielić na grupy o jednakowych indeksach i wypisać w pierwszej kolumnie w kolejnoÅ›ci zgodnej ze wzrastajÄ…cÄ… wartoÅ›ciÄ… indeksu. Dodatkowo, w nawiasie należy zaznaczyć np. symbolami literowymi do których funkcji poszczególne zespoÅ‚y wartoÅ›ci zmiennych należą (kolumna 1 w tablicy z rys. 3.28).

2.    Procedura Å‚Ä…czenia opiera siÄ™ na zasadach obowiÄ…zujÄ…cych przy minimalizacji jednej funkcji (rozdz. '3.4.2), rozszerzonych o dodatkowe reguÅ‚y:

2.1.    Można Å‚Ä…czyć tylko te wyrażenia, które majÄ… choć jeden wspólny symbo1 funkcj i.

2.2.    Przy powstaÅ‚ym w wyniku poÅ‚Ä…czenia wyrażeniu należy wpisać tylko te symbole funkcji, które sÄ… wspólne dla obu Å‚Ä…czonych wyrażeÅ„, np. z poÅ‚Ä…czenia 5 (a.b) z 7 (b,c) powstaje 5,7 (2,b) (kolumna 2 tablicy z rys. 3.28).

2.3.    Znak V należy postawić tylko w tych przypadkach, gdy:

a) Å‚Ä…czone sÄ… dwa wyrażenia o takich samych symbolach literowych (wtedy znak V należy postawić przy obu Å‚Ä…czonych wyrażeniach, np. przy Å‚Ä…czeniu 2 (a.c) z 6 (a.c)), b) Å‚Ä…czone sÄ… dwa wyrażenia, z których jedno ma symbole literowe bÄ™dÄ…ce podzbiorem drugiego (wtedy znak V należy postawić przy tym pierwszym ), np. przy Å‚Ä…czeniu 5(a,b) z 13 (a.b.c) znak V należy postawić tylko przy 5 (a.b).

Prostymi implikantami sÄ… oczywiÅ›cie wszystkie te wyrażenia, które nie oznaczono znakiem V ; tradycyjnie, bÄ™dÄ… one oznaczone symbolem gwiazdki *.

Indeks	Ko1umna 1	Kolumna 2
1	2(a,c) V	2. 6(4,a.c) *
2	5(a,b) V 6(a,c) V	5,    7(2,b) 5,13(8,a.b) * 6.    7(1,c) 6, 14(8,a)
3	7(b,c) 13(a,b,c) * 14(a,b)
		7.15(8,c) 13.15(2,c)
4	15(c) V

Sys. 3.28. Generowanie prostych implikantów (przykład 3.23)

Jak widać (rys. 3.28) informacja o tym do których funkcji należy dana jedynka (punkt 1 algorytmu - oznaczenie literowe) czy też dany ^lmplikant, jest istotna, gdyż z oczywistych powodów wolno sklejać ze ^s°bÄ… jedynie elementy pochodzÄ…ce z tej samej funkcji (punkt 2. 1 algorytmu). A zatem poÅ‚Ä…czenie jedynek 5(a,b) i 7(b.c) w implikant