098 3

196

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ęSci wspólne, należy uwzględnić częSci 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(x1,x2,x3,x4) = £(2,5,6,13.14),	(3.85a)
y2 = fb(xrx2,x3,x4) = £(5,7,13,14),	(3.85b)
^y3 ^= fc^(xl^,x2’^x3’^x4* ^= £(2.6,7,13.15)	(3.85c)

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

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

Pys. 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 Aplikant, jest istotna, gdyż z oczywistych powodów wolno sklejać ze sobą 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