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.

Si dice implicante di f, dove f è una funzione booleana data del tipo

${\displaystyle y=f(x_{1}\dots x_{n})}$

un prodotto di letterali^[2]

${\displaystyle P=x_{i}^{a_{1}}\dots x_{j}^{a_{k}}}$

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 ${\displaystyle 2^{k}}$ 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.

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.

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.

Portale Matematica: accedi alle voci di Teknopedia che trattano di Matematica