Minimalizacja funkcji logicznych

Na wstępie należałoby w zasadzie objaśnić podstawy tegoż zagadnienia ? zapis bitowy, funkcje Boolowskie czy też działania na nich. Jednak bądź co bądź jesteśmy na forum programistycznym ? dlatego też ograniczę się w objaśnianiu nudnych podstaw, założeń i od razu postaram się skoncentrować na tym, co w temacie.

Nie raz zapewne programując niezależnie w jakim to języku, czy też C++, Perl lub Delphi mieliście do czynienia z różnymi warunkami. Popularne ?if (a = 1) or (b = 0) and ?? (1) itd. każdy zapewne zna, nawet dopiero co początkujący programista. Zapewne każdy chciał, aby jego kod wyglądał jak najbardziej schludnie i do tego był maksymalnie krótki ? ?ale nie krótszy niż to możliwe?. Problem pojawia się, gdy przychodzi większa ilość danych występujących w naszym warunku. W zależności od tych danych musimy poskładać nasz warunek, aby został spełniony lub też nie. Zasadniczy problem pojawia się w zapisie tychże warunków (funkcji logicznych ? w przypadku zmiennych typu Boolean) zwłaszcza w sytuacjach, gdy ich ilość jest znaczna.

(1) ? aby w jakiś sposób móc zapisywać funkcje ? będą one pisane jak w środowisku Delphi.

Spójrzmy na poniższy przykład: mając dane tylko trzy zmienne Boolowskie (w różnych kombinacjach) nasza funkcja ma mieć taki rezultat:

Powstaje pytanie: jak się za to zabrać? Rzecz jasna chcielibyśmy, aby funkcja była możliwie jak najkrótsza. Zapewne można podejść do tego tak jak niektórzy początkujący programiści: spójrzmy gdzie są ?jedynki?, w ten sposób złóżmy wszystkie kombinacje. Jak widać ?jedynka? występuje w drugiej, piątej i szóstej kombinacji, zatem można zapisać tak:

If ((A = 0) and (B = 0) and (C = 1)) or ((A = 1) and (B = 0) and (A = 0)) or ((A = 1) and (B = 0) and (C = 1)) then ?

Ale czy jest to możliwie najkrótsza forma zapisu tejże funkcji? Cóż ? jeśli zadałem to pytanie to zapewne odpowiedź brzmi: Nie. W kolejnym kroku, bardziej zaawansowani programiście zaczną szukać pewnych prawidłowości ? na przykład w każdym przypadku zmienna B przyjmuje wartość 0, można zatem skrócić..

If (((A = 0) and (C = 1)) or ((A = 1) and (C = 0)) or ((A = 1) and (C = 1))) and (B = 0) then ?

.. wyłączając zmienną B poza nawias, teraz ?warunek na B? odwołuje się do wszystkich przypadków. Jednak i ten zabieg nie dał oczekiwanych rezultatów znaczącego skrócenia zapisu.

Istnieje jednak algorytm, który pozwoli na uzyskanie minimalnej formy zapisu ? co prawda nie jest on specjalnie prosty ? jednak czasami może przynieść bardzo dobre efekty. Wykorzystane zostaną tylko trzy typy operatorów (jak w zapisanych powyżej): AND, OR oraz NOT. (2)

(2) NOT w zapisie należy traktować z pewnym założeniem. W zapisach powyżej można użyć tego operatora aby oznaczyć te zmienne, które mają równać się 0, a tam gdzie ?1? ? nie pisać nic jako, że warunek sam w sobie jest tylko Boolowskiego ? nie trzeba ?rzutować? na ten typ stosując znaki równości. A zatem wyrażenie:

If (((A = 0) and (C = 1)) or ((A = 1) and (C = 0)) or ((A = 1) and (C = 1))) and (B = 0) then ?

można zamienić na:

If (((not A) and C) or (A and (not C)) or (A and C)) and (not B) then ?

Zapis staje się jak widać prostszy ? I od tej chwili będziemy używać tej konwencji.

Przed rozpoczęciem warto jeszcze wspomnieć iż istnieją dwa sposoby wykorzystania tegoż algorytmu: SOP [FDCF] (Sum Of Products) oraz POS [FCCF] (Produkt of Sum). Wykorzystamy nasz wcześniejszy przykład, przypomnę:

Mamy trzy zmienne, a zatem 2^3 = 8 kombinacji. Funkcja ma przyjmować wartość ?1? tylko dla trzech przypadków. W pierwszym kroku tabelę tą trzeba zamienić na inną postać ? tzw. mapę Karnough.

Kilka słów wyjaśnienia: Jako kolumny i wiersze zostały podane zmienne A, B, C ? ich kolejność nie ma znaczenia (dokładniej mówiąc nie ma znaczenia czy kolumny będą reprezentowane przez A, B lub C ? podobnie wiersze). We wnętrzu tabeli wpisujemy tylko wartość funkcji dla konkretnej kombinacji ? kombinacja jest określona współrzędną. Na przykład kratka w prawym ?dolnym rogu oznacza rezultat funkcji dla A =1, B = 1 oraz C = 0 (zgodnie ze współrzędnymi). Komentarza wymaga natomiast sposób numerowania kolejnych współrzędnych: spójrzmy na pierwszy wiersz (wiersz opisujący współrzędne): 00, 01, 11, 10. Nie jest to naturalny kod dwójkowy tylko tzw. kod. Gray'a ? w każdej nowej pozycji zmienia się tylko i wyłączenie jeden bit (np. dla trzech argumentów kod Gray`a wyglądałby następująco: 000, 001, 011, 010, 110, 111, 101, 100. Również współrzędne w pierwszej kolumnie są zapisane w tym kodzie ? 0, 1 (chociaż tego nie widać). Trzeba zdawać sobie sprawę, że nie zawsze naturalny kod dwójkowy jest wszędzie optymalnym rozwiązaniem i inne zapisy liczb również są powszechnie stosowane.

Kolejnym krokiem jest połączenie tych samych wartości (samych zer (metoda POS) lub samych jedynek (metoda SOP)) w grupy. Skupmy się na razie na metodzie SOP ? suma produktów. Łączenie w grup również wymaga niestety stosownego komentarza. Powiedzmy sobie, że długość boku grupy może przyjmować tylko wartość 2^n, czyli 1, 2, 4, 8, 16 itd. A zatem grupy 1x2, 2x2, 2x4, 1x4 są dozwolone, a 1x3, 2x3, 4x5 już nie. Pyzatym grupy mogą się dowolnie przecinać (nachodzić jedna na drugą). Kratki mogą się też grupować z prawa na lewa, to znaczy: kratka z prawego ? dolnego rogu może się połączyć z kratką z rogu lewego ? dolnego lub prawego ? górnego. W ten sposób można na przykład zaznaczyć cztery kratki po rogach do jednej grupy ? jak gdyby mapa była zdjęta z siatki kuli. Nie można natomiast łączyć po ukosie.

W naszym przykładzie widzimy tylko trzy jedynki, które bez problemu łączymy w dwie, proste grupy:

Gdyby hipotetycznie została jakaś jedynka bez grupy ? łączymy ją w grupę 1x1. W zasadzie należy dążyć do uzyskania jak największych grup.

Trzecim krokiem, zarazem ostatnim jest zapis funkcji stworzony na podstawie grup. Można powiedzieć, że jest to najtrudniejsza część, gdyż wymaga poświęcenia największej uwagi. A robimy to tak: patrzymy po kolei na grupy, niech pierwszą będzie ta zielona (kolejność nie ma znaczenia). Interesują nas tylko te współrzędne, które się nie zmieniają w całej grupie. Będą to zatem: A oraz B (przyjmując wartości odpowiednio 1, 0). Współrzędna C jak widać zmienia się z ?0? na ?1?, a zatem nie bierzemy jej pod uwagę. Zapisujemy iloczyn (AND) tych dwóch współrzędnych z tym, że negujemy (NOT) tam gdzie współrzędna równa jest 0 ? jak widać jest to u nas B. A zatem mamy:

A and (not B)

W ten sposób otrzymaliście jeden ?produkt?. W metodzie tej jak sama nazwa wskazuje mamy otrzymać ich sumę, a zatem bierzemy następną grupę i postępujemy analogicznie otrzymując:

(not B) and C.

Na końcu pozostaje zsumować produkty (jest ich tyle, ile jest grup). Ostatecznie nasz warunek wygląda tak:

If (A and (not B)) or ((not B) and C) then

W ten sposób dokonaliśmy minimalizacji ? juz na pierwszy rzut oka widać, że jest to zapis bardziej elegancji niż pierwsze próby.

Wspomniałem o metodzie drugiej: POS. Jest to metoda, która działa dokładnie odwrotnie niż powyższa, mianowicie stanowi iloraz pewnych sum. W pierwszej kolejności w grupy zaznaczamy tylko zera (tak samo jak zaznaczaliśmy jedynki). Następnie dokonujemy odczytu odwracając negację: NOT tam gdzie współrzędna ma wartość ?1?. Na końcu (jak się domyślacie) zapis funkcji w postaci:

If (E or G or?) and ((not X) or G or?) itd (nazwy przykładowe).

Który jest jak widać jakby odwrotnością metody SOP.

Na koniec pozostaje pytanie: na ile opłaca się stosować tą metodę minimalizacji? Jeśli ktoś ma dobre oko oraz szybki umysł w zasadzie po kilku chwilach potrafi wysunąć odpowiedni zapis warunku z samych kombinacji, jednak nie zawsze to jest takie proste i oczywiste (np. przy większej ilości kombinacji). Również dla niewielkich ich ilości bywają problemy ? tutaj mamy natomiast pewność, że jest to najlepszy zapis z możliwych (3)

(3) Nie używając funkcji XOR :)