Metoda Petricka

Metoda Petricka znana również jako metoda podziału i ograniczeń w algebrze Boole’a została opisana przez Stanleya R. Petricka (1931–2006) w 1956 roku do określenia wszystkich rozwiązań minimalnych sum iloczynów metody Quine’a-McCluskeya. Metoda Petricka jest bardzo żmudna dla dużej liczby zmiennych, ale jest łatwa do implementacji na komputerze.

1. Redukujemy wykres implikantów prostych przez eliminację istotnych implikantów prostych – ich wierszy i odpowiednich kolumn.
2. Oznaczamy wiersze zredukowanego wykresu przez $P_{1},$ $P_{2},$ $P_{3},$ $P_{4}$ itd.
3. Tworzymy funkcję logiczną $P,$ która jest true, kiedy wszystkie kolumny są pokryte. P składa się z iloczynu sum, gdzie każda suma ma postać $(P_{i0}+P_{i1}+\ldots +P_{iN}),$ gdzie każdy $P_{ij}$ reprezentuje wiersz pokrywający kolumnę $i.$
4. Redukujemy $P$ do minimalnej sumy iloczynów przez wymnożenie i zastosowanie $X+XY=X.$
5. Każdy człon rezultatu prezentuje rozwiązanie, to znaczy zbiór wierszy, które pokrywają wszystkie iloczyny zupełne tabeli. Aby określić minimalne rozwiązania, najpierw znajdujemy te człony, które zawierają minimalną liczbę implikantów prostych.
6. Następnie dla każdego członu znalezionego w kroku 6, zliczamy liczbę literałów w każdym implikancie prostym i znajdujemy ogólną liczbę literałów.
7. Wybieramy ten człon albo człony, które są złożone z minimalnej ogólnej liczby literałów i zapisujemy odpowiednie sumy implikantów prostych.

Przykład metody Petricka

Zredukujmy następującą funkcję:

$f(A,B,C)=\sum m(0,1,2,5,6,7).$

Wykres implikantów prostych z metody Quine’a-McCluskeya przedstawia się: (uwaga, inaczej niż w punkcie 2, oznaczyliśmy wiersze literami K..Q)

                | 0 1 2 5 6 7
 ---------------|------------
   K (0,1) a'b' | X X
   L (0,2) a'c' | X   X
   M (1,5) b'c  |   X   X
   N (2,6) bc'  |     X   X
   P (5,7) ac   |       X   X
   Q (6,7) ab   |         X X

Bazując na znaku X-tej tabeli, budujemy iloczyn sum wierszy, gdzie każdy wiersz jest dodawany, a kolumny są mnożone razem:

 (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)

Używamy prawa rozdzielności, aby uzyskać sumę iloczynów. Również używamy następujących równoważności do uproszczeń: X + XY = X i XX = X i X+X=X. Z tych uproszczeń wynika, że (A+B)(A+C) = AA+BA+AC+BC = A+BA+AC+BC = A+AC+BC = A+BC, których użyjemy na początku, aby zredukować liczbę elementów iloczynu. Poza tym A(A+B)=A (A+B)(A+CD)=A+BCD (A+B)(A+C+D) = A+BC+BD

 = (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)
 = (K+LM)(N+LQ)(P+MQ)

To pierwsze przekształcenie można wykonać, tworząc tablicę N×N, gdzie N to liczba kolumn

     |0 1 2 5 6 7
 ----|------------
   0 |\_X X
   1 |  \_  X
   2 |    \_  X
   5 |      \_  X 
   6 |        \_X
   7 |          \

Oznaczamy przez X wiersz n, kolumnę m, gdy literał występuje zarówno w n, jak i m. Mając teraz zaznaczone, wybieramy (0,1), wykreślamy rząd 0 i 1, następnie (2,6), wykreślamy 2 i 6 i zostaje (5,7). Mając (2,6), mnożymy 2-gą i 6-tą sumę przez siebie.

 = (KN+KLQ+LMN+LMQ)(P+MQ)

Mnożymy pierwszą i drugą sumę, każdy z każdym. Na razie nic nie da się uprościć w pierwszym nawiasie, bo żaden człon nie zawiera w całości innego (aby zastosować X + XY = X) Mnożymy ostatecznie to co w nawiasie przez ostatni człon:

 = KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ

Teraz używamy znowu X + XY = X do uproszczania

 = KNP + KLPQ + LMNP + KMNQ + LMQ

skracamy, bo LMPQ, KLMQ i LMNQ zawierają LMQ.

Wybieramy iloczyny z minimalną liczbą składników. W tym przypadku będą dwa iloczyny z trzema składnikami:

 KNP
 LMQ

Wybieramy iloczyny z najmniejszą liczbą literałów razem. W naszym przypadku obydwa iloczyny będą miały po 6 literałów:

KNP    rozwija się do    a'b'+ bc'+ ac
LMQ    rozwija się do    a'c'+ b'c + ab

Może być użyty albo jeden, albo drugi.

Linki zewnętrzne

• simpogical Tutorial metod Quine-McCluskey i Petricka(pdf).
• Prime implicant simplification using Petrick’s method metoda Petricka