title: Metodo di Petrick
text: # 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:
  
  * Riduzione della tabella degli implicanti primi eliminando le righe contenenti implicanti primi essenziali (e le rispettive colonne);
  * Etichettatura delle righe della tabella ridotta ($P_{1}$, $P_{2}$, $P_{3}$, $P_{4}$, ecc.);
  * Costruzione di una funzione logica $P$ tale che sia vera quando tutte le colonne sono coperte ($P$ è costituita da un prodotto di somme, dove ogni termine di somma ha la forma $(P_{i0}+P_{i1}+$$\cdots$$+P_{iN})$, in cui $P_{ij}$ rappresentano una riga che copre la colonna $i$);
  * Minimizzazione di $P$ in somma di prodotti applicando l'equivalenza $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;
  * Conteggio del numero dei letterali in ciascun implicante primo dei termini trovati precedentemente e ricerca del numero totale di letterali;
  * Scelta dei termini formati dal minor numero totale di letterali e scrittura delle corrispondenti somme di implicanti primi.
  
  ## Esempio
  
  Supponiamo di voler ridurre la seguente funzione:
  
      $f(A,B,C)=\sum m(0,1,2,5,6,7)$
  
  Usando il metodo di Quine-McCluskey si perviene alla seguente tabella degli implicanti primi:
  
  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 e le colonne moltiplicate tra loro:
  
      $(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)$
  
  Usando la proprietà distributiva e le equivalenze:
  
  * $X+XY=X$
  * $XX=X$
  * $X+X=X$
  
  l'espressione precedente viene semplificata e trasformata in somma di prodotti come segue:
  
  $(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$
  
  Applicando l'equivalenza:
  
  $X+XY=X$
  
  l'espressione viene ulteriormente ridotta, diventando:
  
  $KNP+KLPQ+LMNP+LMPQ+KMNQ+KLMQ+LMNQ+LMQ=$
  
  $=KNP+KLPQ+LMNP+LMQ+KMNQ$
  
  A questo punto scegliamo i prodotti col minor numero di termini, che in quest'esempio sono:
  
  * $KNP$
  * $LMQ$
  
  Infine, scegliamo i termini col minor numero totale di letterali; pertanto, i due prodotti si espandono entrambi in 6 letterali totali:
  
  * $KNP$ → $a'b'+bc'+ac$
  * $LMQ$ → $a'c'+b'c+ab$
  