Mintermini e Maxtermini

Concetti Chiave

Mintermini sono combinazioni di variabili booleane in forma AND che rappresentano tutte le possibili combinazioni che producono 1 in una funzione booleana.
Maxtermini sono combinazioni di variabili booleane in forma OR che rappresentano tutte le possibili combinazioni che producono 0 in una funzione booleana.
Una funzione booleana può essere espressa come somma di mintermini o come prodotto di maxtermini, e queste forme sono chiamate forme canoniche.

Mintermini e Maxtermini

Una variabile binaria, nell'espressione di una funzione, può apparire sia nella sua forma normale, ad esempio $x$ , sia nella sua forma complementata $x'$ .

Ora consideriamo due variabili binarie $x$ e $y$ combinate con un'operazione AND: $xy$ . Poiché ogni variabile può apparire in entrambe le forme, ci sono quattro possibili combinazioni:

\begin{array}{c} x'y', \\ x'y, \\ xy', \\ xy \end{array}

Ognuno di questi quattro termini AND è chiamato mintermine, o prodotto standard.

In modo simile, $n$ variabili possono essere combinate per formare $2^n$ mintermini. I $2^n$ diversi mintermini possono essere determinati con un metodo simile a quello mostrato nella tabelle che segue per tre variabili:

**Tabella 1:** Mintermini a tre variabili
$x$	$y$	$z$	Termine	Designazione
0	0	0	$x'y'z'$	$m0$
0	0	1	$x'y'z$	$m1$
0	1	0	$x'yz'$	$m2$
0	1	1	$x'yz$	$m3$
1	0	0	$xy'z'$	$m4$
1	0	1	$xy'z$	$m5$
1	1	0	$xyz'$	$m6$
1	1	1	$xyz$	$m7$

I numeri binari da $0$ a $2^n -1$ sono elencati sotto le $n$ variabili. Ogni mintermine si ottiene da un termine AND delle $n$ variabili, con ogni variabile complementata se il bit corrispondente del numero binario è 0 e non complementata se è 1. Un simbolo per ogni mintermine è anche mostrato nella tabella ed è della forma $m_j$ , dove il pedice $j$ denota l'equivalente decimale del numero binario del mintermine designato.

In modo simile, $n$ variabili che formano un termine OR, con ogni variabile complementata o non complementata, forniscono $2^n$ possibili combinazioni, chiamate maxtermini, o somme standard. Gli otto maxtermini per tre variabili, insieme alle loro designazioni simboliche, sono elencati nella tabella seguente:

**Tabella 2:** Maxtermini a tre variabili
$x$	$y$	$z$	Termine	Designazione
0	0	0	$x + y + z$	$M0$
0	0	1	$x + y + z'$	$M1$
0	1	0	$x + y' + z$	$M2$
0	1	1	$x + y' + z'$	$M3$
1	0	0	$x' + y + z$	$M4$
1	0	1	$x' + y + z'$	$M5$
1	1	0	$x' + y' + z$	$M6$
1	1	1	$x' + y' + z'$	$M7$

Un qualsiasi maxtermine dei $2^n$ possibili per $n$ variabili possono essere determinati in modo simile. È importante notare due caratteristiche:

ogni maxtermine si ottiene da un termine OR delle n variabili, con ogni variabile non complementata se il bit corrispondente è 0 e complementata se è 1;
ogni maxtermine è il complemento del suo mintermine corrispondente e viceversa.

Mintermini e Funzioni Booleane

Esiste un'importante relazione tra mintermini e funzioni booleane:

Una funzione booleana può essere espressa algebricamente da una data tabella di verità formando un mintermine per ogni combinazione delle variabili che produce un 1 nella funzione e poi prendendo l'OR di tutti quei termini.

Per esempio, consideriamo la funzione booleana $f_1$ espressa dalla seguente tabella di verità:

**Tabella 3:** Tabella di verità per la funzione f1
$x$	$y$	$z$	Funzione $f_1$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Per ottenere l'espressione algebrica di questa funzione, dobbiamo prendere i mintermini corrispondenti alle combinazioni di variabili che producono un 1 nella funzione. Queste combinazioni sono:

$x' y' z$ (riga 2 della tabella, corrispondente a $m_1$ )
$x y' z'$ (riga 5 della tabella, corrispondente a $m_4$ )
$x y z$ (riga 8 della tabella, corrispondente a $m_7$ )

Fatto questo, possiamo scrivere l'espressione algebrica della funzione $f_1$ mettendo in OR i mintermini ottenuti:

f_1 = x'y'z + xy'z' + xyz = m_1 + m_4 + m_7

Proviamo con un'altra funzione $f_2$ data dalla seguente tabella di verità:

**Tabella 4:** Tabella di verità per la funzione f2
$x$	$y$	$z$	Funzione $f_2$
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

In questo caso, i mintermini che danno 1 come risultato sono:

$x'yz$ (riga 4 della tabella, corrispondente a $m_3$ )
$xy'z$ (riga 6 della tabella, corrispondente a $m_5$ )
$xyz'$ (riga 7 della tabella, corrispondente a $m_6$ )
$xyz$ (riga 8 della tabella, corrispondente a $m_7$ )

Per cui, l'espressione algebrica della funzione $f_2$ diventa:

f_2 = x'yz + xy'z + xyz' + xyz = m_3 + m_5 + m_6 + m_7

Questi esempi dimostrano una proprietà importante dell'algebra booleana: qualsiasi funzione booleana può essere espressa come somma di mintermini (con somma che indica l'operazione OR di termini).

Ora consideriamo il complemento di una funzione booleana.

Supponiamo di voler ricavare l'espressione del complemento di $f_1$ , ossia $f'_1$ . Si può ottenere semplicemente dalla tabella di verità formando un mintermine per ogni combinazione che produce uno 0 nella funzione e poi facendo l'OR di quei termini. Il complemento di $f_1$ è quindi:

f_1' = x'y'z' + x'yz' + x'yz + xy'z + xyz'

Se prendiamo il complemento di della funzione $f'_1$ appena trovata ricaviamo, per dualità, la funzione originale $f_1$ ma in un'altra forma:

f_1 = (x + y + z)(x + y' + z)(x + y' + z')(x' + y + z')(x' + y' + z)

= M_0 \cdot M_2 \cdot M_3 \cdot M_5 \cdot M_6

Ossia come prodotto (inteso come AND) di maxtermini.

In altre parole, possiamo esprimere una funzione booleana come prodotto di maxtermini se prendiamo i maxtermini che danno 0 nella tabella di verità ed effettuiamo l'AND di essi.

Ad esempio, volendo esprimere la funzione $f_2$ in questa forma, cerchiamo i maxtermini che danno 0 come risultato:

$(x + y + z)$ che corrisponde al maxtermine $M_0 = 000$ ;
$(x + y + z')$ che corrisponde al maxtermine $M_1 = 001$ ;
$(x + y' + z)$ che corrisponde al maxtermine $M_2 = 010$ ;
$(x' + y + z)$ che corrisponde al maxtermine $M_4 = 100$ ;

Di questi ne facciamo l'AND e otteniamo $f_2$ :

f_2 = (x + y + z)(x + y + z')(x + y' + z)(x' + y + z)

= M_0 \cdot M_1 \cdot M_2 \cdot M_4

Questi esempi dimostrano una seconda proprietà dell'algebra booleana: qualsiasi funzione booleana può essere espressa come prodotto di maxtermini (con prodotto che significa l'operazione AND di termini).

La procedura per ottenere il prodotto di maxtermini direttamente dalla tabella di verità è la seguente:

Formare un maxtermine per ogni combinazione delle variabili che produce uno 0 nella funzione;
poi formare l'AND di tutti quei maxtermini.

Le funzioni booleane espresse come somma di mintermini o prodotto di maxtermini si dicono essere in forma canonica.

Definizione

Forma Canonica di una Funzione Booleana

Si dice che una funzione booleana è in Forma Canonica quando essa è espressa come:

Somma di mintermini;
oppure come Prodotto di Maxtermini.