Metoda lui Petrick

Metoda Petrick este un algoritm de mintermi de rezoluție conținut într-un tabel de implicați obținut mai întâi cu metoda Quine-McCluskey . Această metodă, care simplifică acoperirea prin transpunerea acesteia în formă algebrică, este incomodă pentru tabele foarte mari, deoarece evaluează toate soluțiile posibile, dar este ușor de implementat într-un computer prin intermediul algoritmilor de ramificare și legați .

Metoda lui Petrick funcționează urmând acești pași: ^[1]

Reducerea tabelului implicaților primi prin eliminarea rândurilor care conțin implicați primari esențiali (și coloanele respective);
Etichetare redusă a rândului tabelului ( $P_{1}$ ${\ displaystyle P_ {1}}$ $P_1$ , $P_{2}$ ${\ displaystyle P_ {2}}$ $P_ {2}$ , $P_{3}$ ${\ displaystyle P_ {3}}$ $P_ {3}$ , $P_{4}$ ${\ displaystyle P_ {4}}$ $P_ {4}$ , etc.);
Construirea unei funcții logice $P.$ ${\ displaystyle P}$ $P.$ astfel încât este adevărat atunci când toate coloanele sunt acoperite ( $P.$ ${\ displaystyle P}$ $P.$ este alcătuit dintr-un produs de sume, în care fiecare termen sumă are forma $(P_{i0}+P_{i1}+$ ${\ displaystyle (P_ {i0} + P_ {i1} +}$ $(P _ {{i0}} + P _ {{i1}} +$ $\cdots$ ${\ displaystyle \ cdots}$ $\ cdots$ $+P_{iN})$ ${\ displaystyle + P_ {iN})}$ $+ P _ {{iN}})$ , in care $P_{ij}$ ${\ displaystyle P_ {ij}}$ $P_ {ij}$ reprezintă un rând care acoperă coloana $the$ ${\ displaystyle i}$ $the$ );
Minimizarea $P.$ ${\ displaystyle P}$ $P.$ pe lângă produsele care aplică echivalența $X+XY=X$ ${\ displaystyle X + XY = X}$ $X + XY = X$ (fiecare termen din rezultat reprezintă o soluție, care este un set de rânduri care acoperă toate mintermele tabelului);
Determinarea soluțiilor minime prin identificarea acelor termeni care conțin cel mai mic număr de implicați primi;
Numărarea numărului de litere din fiecare implicant prim al termenilor găsiți anterior și căutarea numărului total de litere;
Alegerea termenilor formați prin cel mai mic număr total de literali și scrierea sumelor corespunzătoare ale primilor implicați.

Exemplu

Să presupunem că dorim să reducem următoarea funcție: ^[1]

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

{\ displaystyle f (A, B, C) = \ sum m (0,1,2,5,6,7)}

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

Folosind metoda Quine-McCluskey ajungem la următorul tabel cu implicați principali:

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

Pe baza coperților marcate cu un X în tabelul de mai sus, se obține următorul produs al sumelor rândurilor, unde se adaugă rândurile și coloanele se înmulțesc între ele:

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

{\ displaystyle (K + L) (K + M) (L + N) (M + P) (N + Q) (P + Q)}

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

Folosind proprietatea distributivă și echivalențele:

$X+XY=X$ ${\ displaystyle X + XY = X}$ $X + XY = X$
$XX=X$ ${\ displaystyle XX = X}$ $XX = X$
$X+X=X$ ${\ displaystyle X + X = X}$ $X + X = X$

expresia anterioară este simplificată și transformată în suma produselor după cum urmează:

$(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)$ ${\ displaystyle (K + L) (K + M) (L + N) (M + P) (N + Q) (P + Q)}$ $(K + L) (K + M) (L + N) (M + P) (N + Q) (P + Q)$

$=(K+LM)(N+LQ)(P+MQ)$ ${\ displaystyle = (K + LM) (N + LQ) (P + MQ)}$ $= (K + LM) (N + LQ) (P + MQ)$

$=(KN+KLQ+LMN+LMQ)(P+MQ)$ ${\ displaystyle = (KN + KLQ + LMN + LMQ) (P + MQ)}$ $= (KN + KLQ + LMN + LMQ) (P + MQ)$

$=KNP+KLPQ+LMNP+LMPQ+KMNQ+KLMQ+LMNQ+LMQ$ ${\ displaystyle = KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ}$ $= KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ$

Aplicarea echivalenței:

$X+XY=X$ ${\ displaystyle X + XY = X}$ $X + XY = X$

expresia este redusă și mai mult, devenind:

$KNP+KLPQ+LMNP+LMPQ+KMNQ+KLMQ+LMNQ+LMQ=$ ${\ displaystyle KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ =}$ $KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ =$

$=KNP+KLPQ+LMNP+LMQ+KMNQ$ ${\ displaystyle = KNP + KLPQ + LMNP + LMQ + KMNQ}$ $= KNP + KLPQ + LMNP + LMQ + KMNQ$

În acest moment alegem produsele cu cei mai puțini termeni, care în acest exemplu sunt:

$K. Nu. P.$ ${\ displaystyle KNP}$ $KNP$
$L M. Î$ ${\ displaystyle LMQ}$ $LMQ$

În cele din urmă, alegem termenii cu cel mai mic număr total de literali; prin urmare, ambele produse se extind în 6 litere totale:

$K. Nu. P.$ ${\ displaystyle KNP}$ $KNP$ → $a'b'+bc'+ac$ ${\ displaystyle a'b '+ bc' + ac}$ $a'b '+ bc' + ac$
$L M. Î$ ${\ displaystyle LMQ}$ $LMQ$ → $a'c'+b'c+ab$ ${\ displaystyle a'c '+ b'c + ab}$ $a'c '+ b'c + ab$

Notă

^ ^A ^b(EN)Jim Frenzel - ECE 349 - Studiu de fond în elementele fundamentale ale computerului digital - Prelegerea 10

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[uidaho-1] A ^b(EN)Jim Frenzel - ECE 349 - Studiu de fond în elementele fundamentale ale computerului digital - Prelegerea 10

[1]