Metoda Petricka

W algebrze Boole'a metoda Petricka (znana również jako funkcja Petricka lub metoda rozgałęzień i ograniczeń ) jest techniką opisaną przez Stanleya R. Petricka (1931–2006) w 1956 r. Do określania wszystkich rozwiązań o minimalnej sumie produktów z głównego implikanta wykres . Metoda Petricka jest bardzo żmudna w przypadku dużych wykresów, ale łatwo ją zaimplementować na komputerze. Metoda została ulepszona przez Insleya B. Pyne'a i Edwarda Josepha McCluskeya w 1962 roku.

Algorytm

1. Zmniejsz wykres głównych implikantów, eliminując podstawowe wiersze głównych implikantów i odpowiadające im kolumny.
2. Oznacz wiersze zredukowanego wykresu implikantów liczb pierwszych ${\ Displaystyle P_ {1}}$ , ${\ Displaystyle P_ {2}}$ , ${\ Displaystyle P_ {3}}$ , ${\ Displaystyle P_ {4} }}$ itd.
3. Utwórz funkcję logiczną $która$ jest prawdziwa, gdy wszystkie kolumny są pokryte. P składa się z iloczynu sum, gdzie każdy termin sumy ma postać ${\ Displaystyle (P_ {i0} + P_ {i1} +}$${\ Displaystyle \ cdots}$${ \ displaystyle + P_ {iN}}}$ , gdzie każdy reprezentuje wiersz obejmujący kolumnę ${\ Displaystyle P_ {ij}}$${\ Displaystyle ja}$ .
4. Zastosuj $De$ Morgana rozszerzyć na $,$ stosując prawo absorpcji
5. Każdy termin w wyniku reprezentuje rozwiązanie, czyli zestaw wierszy, który obejmuje wszystkie mintermy w tabeli. Aby określić minimalne rozwiązania, najpierw znajdź te wyrażenia, które zawierają minimalną liczbę głównych implikantów.
6. Następnie dla każdego z terminów znalezionych w kroku piątym policz liczbę literałów w każdym implikacie pierwszym i znajdź całkowitą liczbę literałów.
7. Wybierz termin lub terminy złożone z minimalnej całkowitej liczby literałów i wypisz odpowiadające im sumy głównych implikantów.

Przykład metody Petricka

Poniżej znajduje się funkcja, którą chcemy zredukować:

${\ Displaystyle f (A, B, C) = \ suma m (0,1,2,5,6,7) = A'B'C'+ A'B'C + A'BC'+ AB'C+ABC'+ABC}$

Główny wykres implikantów z algorytmu Quine-McCluskey jest następujący:

	0	1	2	5	6	7	⇒	A	B	C
K = m(0,1)							⇒	0	0	—
L = m(0,2)							⇒	0	—	0
M = m(1,5)							⇒	—	0	1
N = m(2,6)							⇒	—	1	0
P = m(5,7)							⇒	1	—	1
Q = m(6,7)							⇒	1	1	—

Na podstawie znaków ✓ w powyższej tabeli zbuduj iloczyn sum wierszy, w których każdy wiersz jest dodawany, a kolumny są mnożone przez siebie:

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

Skorzystaj z prawa dystrybucji, aby zamienić to wyrażenie na sumę produktów. Użyj również następujących równoważności, aby uprościć końcowe wyrażenie: X + XY = X i XX = X i X+X=X

= (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) = (K+LM)(N+LQ)(P+MQ) = (KN +KLQ+LMN+LMQ)(P+MQ) = KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ

Teraz ponownie użyj następującej równoważności, aby jeszcze bardziej zredukować równanie: X + XY = X

= KNP + KLPQ + LMNP + LMQ + KMNQ

Wybierz produkty z najmniejszą liczbą terminów, w tym przykładzie są dwa produkty z trzema terminami:

KNP LMQ

Wybierz termin lub terminy z najmniejszą liczbą literałów. W naszym przykładzie oba produkty rozszerzają się do sześciu literałów:

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

Można więc użyć jednego i drugiego. Ogólnie rzecz biorąc, stosowanie metody Petricka jest żmudne w przypadku dużych wykresów, ale jest łatwe do wdrożenia na komputerze.

Dalsza lektura

• Krambeck, Donald (2016-02-17). „Uproszczenie pierwszego implikanta przy użyciu metody Petricka” . Wszystko o obwodach . ETech Media, LLC. Zarchiwizowane od oryginału w dniu 2017-04-12 . Źródło 2020-04-03 .
• Petrick, Stanley R. (1965). Procedura rozpoznawania gramatyk transformacyjnych (praca doktorska). Instytut Technologii Massachusetts .
•      Bolton, Martin (1990). „4. Minimalizacja”. Napisane na Uniwersytecie w Bristolu, Bristol, Wielka Brytania. W Dagless, Erik L. (red.). Projektowanie systemów cyfrowych z programowalną logiką . Seria inżynierii systemów elektronicznych (1 wyd.). Wokingham, Wielka Brytania: Addison-Wesley Publishers Ltd., str. 100–101, 115. ISBN 0-201-14545-6 . LCCN 90000007 . ISBN 978-0-201-14545-8 ark:/13960/t2f83p38r . Źródło 2021-04-17 . {{ cite book }} : CS1 maint: status adresu URL ( link ) (XIV+379+1 stron)

Linki zewnętrzne

• Samouczek dotyczący metody Quine'a-McCluskeya i Petricka
• Petricka C++ na podstawie powyższego samouczka