Funzioni Booleane in Forma Canonica

Nella lezione precedenta abbiamo visto che una funzione booleana può essere espressa in due forme equivalenti: come somma di mintermini oppure come prodotto di maxtermini.

Queste due forme prendono il nome di Forme Canoniche. In questa lezione studieremo le proprietà di queste due forme, come ricavare le funzioni booleane in queste forme e come convertire da una forma all'altra.

Concetti Chiave

Le funzioni booleane possono essere espresse come somma di mintermini o prodotto di maxtermini.
La somma di mintermini è ottenuta sommando i mintermini che producono un risultato di 1 nella tabella di verità.
Il prodotto di maxtermini è ottenuto moltiplicando i maxtermini che producono un risultato di 0 nella tabella di verità.
Una funzione booleana in forma canonica è espressa come somma di mintermini o prodotto di maxtermini.
Il complemento di una funzione in forma canonica può essere ottenuto invertendo i mintermini e i maxtermini.
La conversione tra somma di mintermini e prodotto di maxtermini può essere effettuata utilizzando le proprietà dell'algebra booleana.

Prima Forma Canonica: Somma di mintermini

Nella lezione precedente, abbiamo affermato che, per $n$ variabili binarie, si possono ottenere $2^n$ mintermini distinti e che qualsiasi funzione booleana può essere espressa come somma di mintermini.

I mintermini la cui somma definisce la funzione booleana sono quelli che danno gli 1 della funzione in una tabella di verità. Poiché la funzione può essere 1 o 0 per ogni mintermine, e poiché ci sono $2^n$ mintermini, si può calcolare che tutte le funzioni che possono essere formate con $n$ variabili sono $2^{2^n}$ .

Risulta talvolta conveniente esprimere una funzione booleana nella sua forma somma-di-mintermini. Se la funzione non è in questa forma, può essere resa tale espandendo prima l'espressione in una somma di termini AND. Ogni termine viene quindi ispezionato per vedere se contiene tutte le variabili. Se manca una o più variabili, viene posto in AND con un'espressione come $x + x'$ , dove $x$ è una delle variabili mancanti.

Chiariamo questo procedimento con l'esempio seguente.

Supponiamo di avere la funzione:

F = A + B'C

Vogliamo esprimere questa funzione in forma canonica come somma di mintermini. La funzione ha tre variabili: $A$ , $B$ , e $C$ . Il primo termine $A$ manca di due variabili; pertanto possiamo scrivere:

A = A(B + B') = AB + AB'

Questa funzione manca ancora di una variabile, quindi:

A = AB(C + C') + AB'(C + C')

= ABC + ABC' + AB'C + AB'C'

Il secondo termine $B'C$ manca di una variabile; quindi:

B'C = B'C(A + A') = AB'C + A'B'C

Combinando tutti i termini, abbiamo

F = A + B'C

= ABC + ABC' + AB'C + AB'C' + A'B'C

Tuttavia $AB'C$ appare due volte, e secondo il teorema:

x + x = x

è possibile rimuovere una di quelle occorrenze. Riorganizzando i mintermini in ordine crescente, otteniamo finalmente

F = A'B'C + AB'C' + AB'C + ABC' + ABC

= m_1 + m_4 + m_5 + m_6 + m_7

Quando una funzione booleana è nella sua forma somma-di-mintermini, è talvolta conveniente esprimere la funzione nella seguente notazione breve:

F(A, B, C) = \Sigma(1, 4, 5, 6, 7)

Il simbolo di somma $\Sigma$ sta per l'operazione OR dei termini; i numeri che lo seguono sono gli indici dei mintermini della funzione. Le lettere tra parentesi che seguono $F$ formano una lista delle variabili nell'ordine preso quando il mintermine viene convertito in un termine AND.

Una procedura alternativa per derivare i mintermini di una funzione booleana è ottenere la tabella di verità della funzione direttamente dall'espressione algebrica e poi leggere i mintermini dalla tabella di verità.

Consideriamo, ad esempio, la funzione booleana data nell'esempio precedente:

F = A + B'C

La tabella di verità di $F$ è mostrata di seguito:

**Tabella 1:** Tabella di verità per la funzione F
$A$	$B$	$C$	$F$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Questa tabella può essere derivata direttamente dall'espressione algebrica elencando le otto combinazioni binarie sotto le variabili $A$ , $B$ , e $C$ e inserendo 1 sotto $F$ per quelle combinazioni per cui $A$ = 1 o $BC$ = 01.

Dalla tabella di verità, possiamo poi prendere i cinque mintermini della funzione come 1, 4, 5, 6, e 7 a cui corrisponde un 1 nella colonna $F$ . Quindi, possiamo scrivere la funzione come somma di tali mintermini:

F(A, B, C) = \Sigma(1, 4, 5, 6, 7)

= A'B'C + AB'C' + AB'C + ABC' + ABC

Ricapitolando:

Definizione

Funzione Booleana in Prima Forma Canonica: Somma di Mintermini

Una funzione booleana è in Prima Forma Canonica se è espressa come somma di tutti i mintermini che producono un risultato di 1 nella tabella di verità della funzione. La notazione breve per una funzione in questa forma è $\Sigma$ seguita dagli indici dei mintermini:

F = \Sigma(m_a, m_b, \ldots, m_n)

Dove $m_a, m_b, \ldots, m_n$ sono gli indici dei mintermini della funzione che restituiscono 1 nella tabella di verità.

Seconda Forma Canonica: Prodotto di Maxtermini

Ciascuna delle $2^{2^n}$ funzioni di $n$ variabili binarie può essere anche espressa come prodotto di maxtermini.

Per esprimere una funzione booleana come prodotto di maxtermini, deve prima essere portata in una forma di termini OR. Questo può essere fatto usando la legge distributiva:

x + yz = (x + y)(x + z)

Poi qualsiasi variabile mancante $x$ in ogni termine OR viene messa in OR con $xx'$ .

Chiariamo questo procedimento con un esempio.

Vogliamo esprimere la funzione booleana:

F = xy + x'z

come prodotto di maxtermini.

Per prima cosa, bisogna convertire la funzione in termini OR usando la legge distributiva:

F = xy + x'z = (xy + x')(xy + z)

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

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

La funzione ha tre variabili: $x$ , $y$ , e $z$ . Ogni termine OR manca di una variabile; pertanto, combiniamo l'AND del termine mancante con il suo complemento al termine dove manca:

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

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

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

Combinando tutti i termini e rimuovendo quelli che appaiono più di una volta, otteniamo finalmente

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

= M_0 \cdot M_2 \cdot M_4 \cdot M_5

Un modo conveniente per esprimere questa funzione è il seguente:

F(x, y, z) = \Pi(0, 2, 4, 5)

Il simbolo di prodotto, $\Pi$ $, denota l'operazione AND dei maxtermini; i numeri sono gli indici dei maxtermini della funzione.

Ricapitolando:

Definizione

Funzione Booleana in Seconda Forma Canonica: Prodotto di Maxtermini

Una funzione booleana è in Forma Canonica se è espressa come prodotto di tutti i maxtermini che producono un risultato di 0 nella tabella di verità della funzione. La notazione breve per una funzione in questa forma è $\Pi$ seguita dagli indici dei maxtermini:

F = \Pi(M_a, M_b, \ldots, M_n)

Dove $M_a, M_b, \ldots, M_n$ sono gli indici dei maxtermini della funzione che restituiscono 0 nella tabella di verità.

Conversione tra Forme Canoniche

Il complemento di una funzione espressa come somma di mintermini è uguale alla somma dei mintermini mancanti dalla funzione originale. Questo perché la funzione originale è espressa da quei mintermini che rendono la funzione uguale a 1, mentre il suo complemento è 1 per quei mintermini per cui la funzione è 0.

Come esempio, si consideri la funzione dell'esempio precedente:

F(A, B, C) = A'B'C + AB'C' + AB'C + ABC' + ABC

Questa funzione, in notazione compatta, può essere scritta come:

F(A, B, C) = \Sigma(1, 4, 5, 6, 7)

Questa funzione ha un complemento che può essere espresso velocemente come:

F'(A, B, C) = \Sigma(0, 2, 3) = m_0 + m_2 + m_3

Ora, se prendiamo il complemento di $F'$ per il teorema di DeMorgan, otteniamo $F$ in una forma diversa:

F = (m_0 + m_2 + m_3)'

= m'_0 \cdot m'_2 \cdot m'_3

= M_0 \cdot M_2 \cdot M_3 = \Pi(0, 2, 3)

L'ultima conversione segue dalla definizione di mintermini e maxtermini come visto nella lezione precedente. Dalla tabella, è chiaro che vale la seguente relazione:

m'_j = M_j

Cioè, il maxtermine con pedice $j$ è un complemento del mintermine con lo stesso pedice $j$ e viceversa.

L'ultimo esempio dimostra la conversione tra una funzione espressa in forma canonica somma-di-mintermini e la sua equivalente in forma prodotto-di-maxtermini.

Allo stesso modo, si può dimostrare che la conversione tra il prodotto di maxtermini e la somma di mintermini è simile.

Ora enunciamo una procedura di conversione generale. Per convertire da una forma canonica all'altra:

Si scambiano i simboli $\Sigma$ e $\Pi$ ;
Si elencano quei numeri mancanti dalla forma originale. Per trovare i termini mancanti, si deve ricordare che il numero totale di mintermini o maxtermini è $2^n$ , dove $n$ è il numero di variabili binarie nella funzione.

Una funzione booleana può essere convertita da un'espressione algebrica a un prodotto di maxtermini per mezzo di una tabella di verità e della procedura di conversione canonica.

Si consideri, per esempio, l'espressione booleana:

F = xy + x'z

Prima, deriviamo la tabella di verità della funzione, come mostrato nella tabella seguente:

**Tabella 2:** Tabella di verità per la funzione F
$x$	$y$	$z$	$F$	Tipo
0	0	0	0	Maxtermine
0	0	1	1	Mintermine
0	1	0	0	Maxtermine
0	1	1	1	Mintermine
1	0	0	0	Maxtermine
1	0	1	0	Maxtermine
1	1	0	1	Mintermine
1	1	1	1	Mintermine

Gli 1 sotto $F$ nella tabella sono determinati dalla combinazione delle variabili per cui $xy = 11$ o $xz = 01$ . I mintermini della funzione sono ricavati dalla tabella di verità come 1, 3, 6, e 7. La funzione espressa come somma di mintermini è

F(x, y, z) = \Sigma(1, 3, 6, 7)

F(x, y, z) = m_1 + m_3 + m_6 + m_7

F' = \Sigma(0, 2, 4, 5)

Poiché c'è un totale di otto mintermini o maxtermini in una funzione di tre variabili, determiniamo che i termini mancanti sono 0, 2, 4, e 5. La funzione espressa come prodotto di maxtermini è

F(x, y, z) = \Pi(0, 2, 4, 5)

la stessa risposta ottenuta nell'esempio di sopra.

Esempi

Proviamo a risolvere alcuni esercizi pratici per consolidare la comprensione delle forme canoniche.

Esempio

Trovare un'espressione prodotto di maxtermini per:

F(x, y, z) = \Sigma(1, 2, 3, 5, 7)

Per prima cosa, applicando la procedura di conversione, sostituiamo il simbolo $\Sigma$ con $\Pi$ e troviamo i mintermini mancanti. Poiché ci sono otto mintermini in totale, i mintermini mancanti sono 0, 4, e 6. Quindi, l'espressione prodotto di maxtermini è:

F = \Pi(0, 4, 6)

Adesso possiamo scrivere l'espressione in forma algebrica:

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

Esempio

Trovare un'espressione somma di mintermini per:

F(x, y, z) = \Pi(1, 3, 4, 6)

Sostituiamo il simbolo $\Pi$ con $\Sigma$ e troviamo i maxtermini mancanti. Poiché ci sono otto maxtermini in totale, i maxtermini mancanti sono 0, 2, 5, e 7. Quindi, l'espressione somma di mintermini è:

F = \Sigma(0, 2, 5, 7)

Adesso possiamo scrivere l'espressione in forma algebrica:

F = x'y'z' + x'y'z + xy'z' + xyz

Esempio

Si identifichino i mintermini e maxtermini della tabella di verità per la funzione $F$ mostrata sotto.

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

I mintermini sono le combinazioni di variabili che producono un 1 nella funzione. Dalla tabella, i mintermini sono:

$x'y'z$ (riga 2 della tabella, corrispondente a $m_1$ )
$x'y$ (riga 4 della tabella, corrispondente a $m_3$ )
$xy'z'$ (riga 5 della tabella, corrispondente a $m_4$ )
$xyz'$ (riga 7 della tabella, corrispondente a $m_6$ )

Per cui, la funzione $F$ può essere espressa come somma di mintermini:

F = x'y'z + x'y + xy'z' + xyz'

= \Sigma(1, 3, 4, 6)

I maxtermini sono le combinazioni di variabili che producono un 0 nella funzione. Dalla tabella, i maxtermini sono:

$x'y'z'$ (riga 1 della tabella, corrispondente a $M_0$ )
$x'y'z$ (riga 3 della tabella, corrispondente a $M_2$ )
$xy'z$ (riga 6 della tabella, corrispondente a $M_5$ )
$xyz$ (riga 8 della tabella, corrispondente a $M_7$ )

Per cui, la funzione $F$ può essere espressa come prodotto di maxtermini:

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

= \Pi(0, 2, 5, 7)