Rotation of�

184

3.4.3. Minimalizacja funkcji słabo określonych

W wielu praktycznych zagadnieniach występują funkcje wielu zmiennych, określone jedynie dla niewielkiej liczby zespołów wartości zmiennych. Uwzględnianie wszystkich zespołów wartości zmiennych dla których funkcja jest nieokreślona (zbiór F ), niezbędne w metodzie Quine’a-McCluskey’a, powoduje, że w tych przypadkach metoda ta staje się mało efektywna. Wyznacza się bowiem wiele prostych implikantów (prostych implicentów), które nie pokrywają żadnych jedynek (żadnych zer) funkcji.

Definicja 3. 17

Funkcja przełączająca n zmiennych f(x^,X2.....x_n) jest słabo

określona, gdy spełniony jest warunek

|F^!u F°| < |f""'” |,    (3.67)

gdzie |F| oznacza liczbę elementów zbioru F.

Warunek (3.67) jest równoważny poniższemu:

|Dⁿ| < £ 2ⁿ = 2ⁿ~¹.    (3.68)

przy czym Dⁿ oznacza dz i edz i nę funkcj i f (por. wyrażeń i e (3.2)).

A zatem, o funkcji słabo określonej mówi się w przypadku, gdy liczba jej "kresek" (nieokreśloności) jest większa niż sumaryczna liczba jej zer i jedynek.

Przedmiotem rozważali będzie tu minimalizacja normalnej postaci sumy (NPS) funkcji. W tym celu najpierw należy znaleźć wszystkie proste implikanty funkcji. W przedstawionych dotychczas metodach minimalizacji, poszukiwanie prostych implikantów wymaga rozważenia wszystkich jedynek i “kresek" funkcji. Jednakże, z punktu widzenia złożoności obliczeniowej, w przypadku funkcji słabo określonych dużo korzystniejszy jest algorytm uzyskiwania prostych implikantów na podstawie zer i jedynek funkcji. Algorytm wyjaśniony będzie na poniższym przykładzie.

Przykład 3.17 [11]

Rozpatrywana jest funkcja pięciu zmiennych f(Xj,x_2>x₃.X_4>x₅),

określona następująco:

F¹ = |3, 12. 13. 16.25.29j. F° = -|l, 10,21,281    (3.63)

Binarne zbiory 5* i 5® odpowiadające F* i F*^ są zatem następujące:

^X1^X2^X3^X4^X5 ^ 0 0 0 1 1 0 110 0 < 0 110 1?-1 0 0 0 0 110 0 1 1110 1

5° =

^X1^X2^X3^X4^X5

OOOOl'

¹ 01010?

10 10 1

1110 0 b

(3.70)

Poszukiwania prostych implikantów tej funkcji dokonuje się z pomocą tzw. tablicy niezgodności przedstawionej na rys. 3.25.

Rys. 3.25. Tablica niezgodności do przykładu 3.17