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 (, , , , ecc.); Costruzione di una funzione logica tale che sia vera quando tutte le colonne sono coperte ( è costituita da un prodotto di somme, dove ogni termine di somma ha la forma , in cui rappresentano una riga che copre la colonna ); Minimizzazione di in somma di prodotti applicando l'equivalenza (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:
Usando il metodo di Quine-McCluskey si perviene alla seguente tabella degli implicanti primi:
| 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
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:
Usando la proprietà distributiva e le equivalenze:
l'espressione precedente viene semplificata e trasformata in somma di prodotti come segue:
Applicando l'equivalenza:
l'espressione viene ulteriormente ridotta, diventando:
A questo punto scegliamo i prodotti col minor numero di termini, che in quest'esempio sono:
Infine, scegliamo i termini col minor numero totale di letterali; pertanto, i due prodotti si espandono entrambi in 6 letterali totali:
→ →
Note
Categoria:Logica matematica Categoria:Elettronica digitale Categoria:Algebra di Boole