Indietro

ⓘ Metodo di Petrick




                                     

ⓘ Metodo di Petrick

Il metodo di Petrick è un algoritmo di risoluzione dei mintermini contenuti in una tabella degli implicanti primi ricavata con il metodo di Quine-McCluskey. Tale metodo, che semplifica la copertura trasponendola in forma algebrica, risulta scomodo per tabelle molto grandi, in quanto valuta tutte le possibili soluzioni, ma è facilmente implementabile in un computer tramite algoritmi di branch and bound.

Il metodo di Petrick opera seguendo questi passaggi:

  • Scelta dei termini formati dal minor numero totale di letterali e scrittura delle corrispondenti somme di implicanti primi.
  • Riduzione della tabella degli implicanti primi eliminando le righe contenenti implicanti primi essenziali le rispettive colonne;
  • Costruzione di una funzione logica P {\displaystyle P} tale che sia vera quando tutte le colonne sono coperte P {\displaystyle P} è costituita da un prodotto di somme, dove ogni termine di somma ha la forma P i 0 + P i 1 + {\displaystyle P_{i0}+P_{i1}+} ⋯ {\displaystyle \cdots } + P i N {\displaystyle +P_{iN})}, in cui P i j {\displaystyle P_{ij}} rappresentano una riga che copre la colonna i {\displaystyle i});
  • Etichettatura delle righe della tabella ridotta ;
  • Conteggio del numero dei letterali in ciascun implicante primo dei termini trovati precedentemente e ricerca del numero totale di letterali;
  • Minimizzazione di P {\displaystyle P} in somma di prodotti applicando lequivalenza X + X Y = X {\displaystyle X+XY=X} ciascun termine nel risultato rappresenta una soluzione, ovvero un insieme di righe che copre tutti i mintermini della tabella;
  • Determinazione delle soluzioni minime individuando quei termini che contengono il minor numero di implicanti primi;
                                     

1. Esempio

Supponiamo di voler ridurre la seguente funzione:

f A, B, C = ∑ m 0, 1, 2, 5, 6, 7 {\displaystyle fA,B,C=\sum m0.1.2.5.6.7}

Usando il metodo di Quine-McCluskey si perviene alla seguente tabella degli implicanti primi:

| 0 1 2 5 6 7 ---------------|------------ K 0.1 ab | X L 0.2 ac | X M 1.5 bc | X N 2.6 bc | X P 5.7 ac | X Q 6.7 ab | X

In base alle coperture segnate con una X nella tabella soprastante, si ricava il seguente prodotto di somme delle righe, dove le righe vengono addizionate le colonne moltiplicate tra loro:

K + L K + M L + N M + P N + Q P + Q {\displaystyle K+LK+ML+NM+PN+QP+Q}

Usando la proprietà distributiva le equivalenze:

  • X + X = X {\displaystyle X+X=X}
  • X = X {\displaystyle XX=X}
  • X + X Y = X {\displaystyle X+XY=X}

lespressione precedente viene semplificata e trasformata in somma di prodotti come segue:

K + L K + M L + N M + P N + Q P + Q {\displaystyle K+LK+ML+NM+PN+QP+Q}

= K + L M N + L Q P + M Q {\displaystyle =K+LMN+LQP+MQ}

= K N + K L Q + L M N + L M Q P + M Q {\displaystyle =KN+KLQ+LMN+LMQP+MQ}

= K N P + K L P Q + L M N P + L M P Q + K M N Q + K L M Q + L M N Q + L M Q {\displaystyle =KNP+KLPQ+LMNP+LMPQ+KMNQ+KLMQ+LMNQ+LMQ}

Applicando lequivalenza:

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

lespressione viene ulteriormente ridotta, diventando:

K N P + K L P Q + L M N P + L M P Q + K M N Q + K L M Q + L M N Q + L M Q = {\displaystyle KNP+KLPQ+LMNP+LMPQ+KMNQ+KLMQ+LMNQ+LMQ=}

= K N P + K L P Q + L M N P + L M Q + K M N Q {\displaystyle =KNP+KLPQ+LMNP+LMQ+KMNQ}

A questo punto scegliamo i prodotti col minor numero di termini, che in questesempio sono:

  • L M Q {\displaystyle LMQ}
  • K N P {\displaystyle KNP}

Infine, scegliamo i termini col minor numero totale di letterali; pertanto, i due prodotti si espandono entrambi in 6 letterali totali:

  • K N P {\displaystyle KNP} → a ′ b ′ + b c ′ + a c {\displaystyle ab+bc+ac}
  • L M Q {\displaystyle LMQ} → a ′ c ′ + b ′ c + a b {\displaystyle ac+bc+ab}
                                     
  • Il metodo di Quine - McCluskey o metodo degli implicanti primi è un algoritmo sviluppato da Willard Van Orman Quine ed Edward McCluskey che viene utilizzato

Anche gli utenti hanno cercato:

metodo quine,

...
...
...