Metoda Quine’a-McCluskeya - Teoria Układów Logicznych

Teoria Układów Logicznych  1 Metoda Quine’a-McCluskeya    Mamy przykładową funkcję  F(A,B,C,D).  Wybrano cztery zmiennych, gdyż  metoda ta dla większej liczby zmiennych jest bardziej pracochłonna i jest możliwa do  praktycznego wykorzystania w zasadzie tylko jako algorytm komputerowy. Funkcję  opiszemy przy pomocy zbiorów F1 i F*.   F1={1,5,7,8,9,13,15}-zbiór argumentów dla których nasza funkcja przyjmuje  wartość logiczną 1,  oraz F*={4,14}- zbiór argumentów gdzie funkcja jest nieokreślona  czyli 0 lub 1.  Naszym zadaniem będzie znaleźć minimalną postać dysjunkcyjną (sumę  iloczynów) tej funkcji.  Łączymy zbiór F1  ze zbiorem F* i otrzymujemy zbiór F={1,4,5,7,8,9,10,14,15}.  Argumenty tego zbioru wypisujemy w kolejności dziesiętnej w postaci kolumny  A  (poniżej) i dla każdego z nich odpowiednio postać binarną-wektory.    Następnie grupujemy te wektory  o tej samej liczbie jedynek. Grupy szeregujemy rosnąco  według liczby jedynek, tak jak w kolumnie  B          A             B           1 0001 1  0001 + 4 0100 4  0100 + 5 0101 8  1000 + 7 0111       8 1000 5  0101 + 9 1001 9  1001 + 13 1011       14 1110 7  0111 + 15 1111 13  1011 +      14  1110 +              15  1111 +                                            Teraz porównujemy  wektory z postaci  B  o k-tej liczbie jedynek z wektorami o k+1  liczbie jedynek i łączymy te które różnią się tylko jednym bitem, np. 0001 i 0101 czyli1 i  5 róznią się jedną pozycją  zatem tworzymy nowy wektor 0*01 gdzie symbol *  wstawiamy w miejsce gdzie te wektory się różnią (w pozycję różniących bitów  wpisujemy  *). Tak postępujemy aż do wyczerpania się dalszych łączeń jak przedstawia  poniższa tabela  C.  Wektory z   B  użyte w  C  oznaczamy symbolem +. Połączenia, które  powstały są przedstawione w  C.      Teoria Układów Logicznych  2 C    Implikanty  niewykorzystanych    Połączeń    1 i 5  0*01      +        1 i 9  *001      +        4 i 5  010*  A‘BC‘      8 i 9  100*  AB‘C‘      5 i 7  01*1      +        5 i 13  *101      +        9 i 13  1*01      +        7 i 15  *111      +        13 i 15  11*1      +        14 i 15  111*  ABC          Z tabelą  C  postępujemy podobnie jak z   B  tzn. porównujemy np. (1i5)i(1i9) czyli 0*01 i  *001 widzimy że różnią się więcej niż jedną pozycją zatem nie możemy ich połączyć, w  przypadku różnicy na jednej pozycji łączymy te wektory i na tą pozycje dajemy *.  ... zobacz całą notatkę