Implicanti e mintermini

Un implicante di una funzione booleana è un prodotto elementare che, se vero (cioè pari a 1), rende la funzione vera.

Dove un prodotto elementare è un gruppo di letterali moltiplicati insieme. Ad esempio, un prodotto elementare è \(x \cdot \overline{y}\) che viene spesso scritto senza il segno della moltiplicazione come \(x\overline{y}\).

In altre parole, un implicante è un termine che, quando è vero, garantisce che la funzione booleana sia vera, ma non necessariamente il contrario.

Gli implicanti possono essere:

• Implicanti primi
  Un implicante primo è un implicante che non può essere ulteriormente ridotto senza cambiare il valore della funzione. Non può essere sostituito completamente da un altro implicante più semplice. Non tutti gli implicanti primi includono necessariamente tutte le variabili della funzione, a differenza dei mintermini.
• Implicanti essenziali
  Un implicante essenziale è un tipo di implicante primo che è l'unico che determina una o più uscite della tabella di verità. È essenziale per la copertura minima della funzione.
• Mintermini
  Un mintermine è un caso specifico di implicante. È un prodotto di tutte le variabili in una funzione booleana, ognuna presente nella sua forma diretta o complementata (negata). I mintermini rappresentano ogni possibile combinazione di variabili che risultano nella funzione che diventa vera.

Nella forma canonica disgiuntiva (somma di prodotti), una funzione booleana può essere espressa come la somma (OR) di tutti i suoi mintermini, ovvero le combinazioni di ingressi per le quali la funzione è vera.

Esempio

Facciamo un esempio concreto con una funzione booleana \( f \) di tre variabili: \( A \), \( B \), e \( C \) e vediamo come si possono identificare gli implicanti, gli implicanti primi e i mintermini.

Supponiamo che la tabella di verità di \( f \) sia la seguente:

$$
\begin{array}{|c|c|c|c|}
\hline
A & B & C & f(A, B, C) \\
\hline
0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 \\
\hline
\end{array}
$$

Questa tabella mostra chiaramente tutte le combinazioni possibili delle variabili \( A \), \( B \), e \( C \), insieme ai corrispondenti valori della funzione \( f \).

Ogni riga della tabella di verità dove \( f \) è 1 rappresenta un mintermine della funzione booleana.

In questo caso i mintermini sono:

• \( \overline{A} \overline{B} C \)  per la seconda riga, dove A = 0, B = 0, C = 1
• \( \overline{A} B C \)  per la quarta riga, dove A = 0, B = 1, C = 1
• \( A \overline{B} \overline{C} \)  per la quinta riga, dove A = 1, B = 0, C = 0
• \( A \overline{B} C \)  per la sesta riga, dove A = 1, B = 0, C = 1
• \( A B C \)  per l'ottava riga, dove A = 1, B = 1, C = 1

La funzione \( f \) può essere scritta come la somma dei suoi mintermini.

Questa forma è detta DNF (forma normale disgiuntiva).

$$ f = \overline{A} \overline{B} C + \overline{A} B C + A \overline{B} \overline{C} + A \overline{B} C + A B C $$

Per trovare gli implicanti primi, dobbiamo cercare termini che non possono essere ulteriormente ridotti.

Noteremo che alcuni dei mintermini possono essere combinati per ridurre l'espressione:

• \( \overline{A} \overline{B} C \) + \( \overline{A} B C \) possono essere combinati come \( \overline{A} C \) rimuovendo \( B \)

  Nella somma il letterale B è presente sia in forma diretta $ B $ che negata $ \overline{B} $ generando un'identità.  $ B + \overline{B} = 1 $ Quindi, può essere rimosso $$  \overline{A} \color{red}{\overline{B}} C  + \overline{A} \color{red}B C  = \overline{A} C $$

• \( A \overline{B} \overline{C} \) + \( A \overline{B} C \) + \( A B C \) possono essere combinati come \( A \) rimuovendo \( B \) e \( C \)

  Nella somma i letterale B e C sono presenti sia in forma diretta $ B $ e $ C $ che negata $ \overline{B} $ e $ \overline{C} $ generando due identità.  $ \overline{B} + \overline{B} + B  = 1 $ e $ \overline{C} + C + C = 1 $ Quindi, possono essere rimossi  $$ A \color{red}{ \overline{B} } \color{blue}{ \overline{C} } + A \color{red}{ \overline{B}} \color{blue}C + A \color{red}B \color{blue}C = A $$

Pertanto, gli implicanti primi della funzione booleana sono:

• \( \overline{A} C \)
• \( A \)

Grazie agli implicanti primi possiamo semplificare la funzione booleana.

$$ f = \underbrace{ \overline{A} \overline{B} C + \overline{A} B C }_{ \overline{A} C } + \underbrace{ A \overline{B} \overline{C} + A \overline{B} C + A B C }_{ A } $$

La funzione \( f \) semplificata con gli implicanti primi è la seguente:

$$ f = \overline{A} C + A $$

Questo mostra come gli implicanti, e in particolare gli implicanti primi, possono essere utilizzati per semplificare una funzione booleana partendo dai suoi mintermini.