Implicante
Il concetto di implicante è un concetto di base[1] per la definizione formale delle forme canoniche legate all'algebra di Boole ed in particolare allo studio nelle reti logiche delle porte logiche.
Definizione formale[modifica | modifica wikitesto]
Si dice implicante di f, dove f è una funzione booleana data del tipo
un prodotto di letterali[2]
tale che se P = 1 allora f = 1.
Un implicante di una funzione è quindi un termine prodotto che coinvolge solo alcune variabili di f e tale per cui la funzione vale 1.
Un implicante è rappresentabile come un gruppo di celle adiacenti di dimensione pari a che rispetti le seguenti proprietà:
- ogni cella è adiacente ad esattamente altre k celle dell'implicante
- ogni cella contiene lo stesso valore.
Il valore dipende dalla forma canonica scelta. Nel caso di una forma canonica disgiuntiva (somma di prodotti, SOP o SP) tale valore è 1, altrimenti, nel caso di una forma canonica congiuntiva (prodotto di somme, POS o PS), tale valore è 0.
Utilizzo[modifica | modifica wikitesto]
Gli implicanti sono molto importanti nello studio delle reti logiche ed in particolare sono utilizzati nei metodi di semplificazione come le mappe di Karnaugh o il metodo di Quine-McCluskey.
Caratterizzazioni[modifica | modifica wikitesto]
Un implicante non contenuto in nessun altro implicante si dice implicante primo (ossia un sottocubo di dimensione massima). Ne consegue che tale implicante è l'implicante col numero minore possibile di letterali. Ne consegue che un implicante primo è tale quando non è più suscettibile di espansione, dove per espansione si intende il processo di estensione, in tutte le direzioni, dell'implicante, in genere fatta secondo regole euristiche, purché si abbia una configurazione di arrivo valida, e quindi l'implicante finale sia composto da un numero pari di mintermini. La ricerca degli implicanti primi è la base su cui si fonda la ricerca delle mappe di Karnaugh.
Un implicante si dice implicante primo essenziale se esiste almeno un mintermine che non è coperto da nessun altro implicante primo.
Il duale dell'implicante si chiama implicato.
L'insieme degli implicanti che coprono tutti i mintermini è detto copertura. Una copertura deve contenere tutti gli implicanti primi essenziali.
Si definisce riduzione l'operazione tramite la quale, partendo da due implicanti che si sovrappongono, si giunge ad una configurazione finale di implicanti che non si sovrappongono.
Note[modifica | modifica wikitesto]
- ^ Davide Quaglia, Algebra di commutazione (PDF), su profs.sci.univr.it, Università di Verona. URL consultato il 12 febbraio 2010 (archiviato dall'url originale il 9 giugno 2006).
- ^ Una generica variabile booleana che compare all'interno di una funzione booleana è indicata con una lettera e per questo ci si fa riferimento chiamandola anche letterale.
