Implicante

Da Wikipedia, l'enciclopedia libera.

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 sorgente]

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

y = f(x_1 \dots x_{n})

un prodotto di letterali

 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  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.

Utilizzo[modifica | modifica sorgente]

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 sorgente]

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 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 sorgente]

  1. ^ Davide Quaglia, Algebra di commutazione, Università di Verona. URL consultato il 12-02-2010.
Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica