Funzioni Booleane in Forma Standard

Concetti Chiave

Le funzioni booleane possono essere espresse in forma standard come somma di prodotti o prodotto di somme.
La somma di prodotti consiste in termini AND seguiti da una porta OR, mentre il prodotto di somme consiste in termini OR seguiti da una porta AND.
Le forme standard non richiedono che tutti i letterali siano presenti in ogni termine, a differenza delle forme canoniche.
Le funzioni in forma standard sono utili per la progettazione di circuiti logici e per la minimizzazione delle funzioni booleane.

Forma Standard di una Funzione Booleana

Le due forme canoniche dell'algebra booleana sono forme di base che si ottengono dalla lettura di una data funzione dalla tabella di verità.

Sebbene utili, queste forme in casi estremamente rari sono quelle con il minor numero di letterali, perché ogni mintermine o maxtermine deve contenere, per definizione, tutte le variabili, sia complementate che non complementate. In altre parole, le forme canoniche non sono minimizzate e, pertanto, non sono le più efficienti.

Un altro modo per esprimere le funzioni booleane è in forma standard. In questa configurazione, i termini che formano la funzione possono contenere uno, due, o qualsiasi numero di letterali, ossia non è necessario che contengano tutti i letterali. Ci sono due tipi di forme standard: la somma di prodotti e i prodotti di somme.

La somma di prodotti è un'espressione booleana contenente termini AND, chiamati termini prodotto, con uno o più letterali ciascuno. La somma denota l'operazione OR di questi termini. Un esempio di una funzione espressa come somma di prodotti è

F_1 = y' + xy + x'yz'

L'espressione ha tre termini prodotto, con uno, due e tre letterali. La loro somma è, in effetti, un'operazione OR.

Il diagramma logico di un'espressione somma-di-prodotti consiste di un gruppo di porte AND seguite da una singola porta OR. Questo schema di configurazione è mostrato nella figura che segue:

**Figura 1:** Diagramma logico a due livelli della funzione F1 come somma di prodotti

Ogni termine prodotto richiede una porta AND, eccetto per un termine con un singolo letterale. La somma logica è formata con una porta OR i cui input sono gli output delle porte AND e il singolo letterale. Si assume che le variabili di input siano direttamente disponibili nei loro complementi, quindi gli invertitori non sono inclusi nel diagramma. Questa configurazione di circuito è chiamata implementazione a due livelli.

Un prodotto di somme è un'espressione booleana contenente termini OR, chiamati termini somma. Ogni termine può avere qualsiasi numero di letterali. Il prodotto denota l'operazione AND di questi termini. Un esempio di una funzione espressa come prodotto di somme è

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

Questa espressione ha tre termini somma, con uno, due e tre letterali. Il prodotto è un'operazione AND. L'uso delle parole prodotto e somma deriva dalla similarità dell'operazione AND al prodotto aritmetico (moltiplicazione) e la similarità dell'operazione OR alla somma aritmetica (addizione). La struttura di porte dell'espressione prodotto-di-somme consiste di un gruppo di porte OR per i termini somma (eccetto per un singolo letterale), seguita da una porta AND, come mostrato nella figura seguente:

**Figura 2:** Diagramma logico a due livelli della funzione F2 come prodotto di somme

Questo tipo standard di espressione risulta in una struttura a due livelli di porte.

Definizione

Funzione Booleana in Forma Standard

Una funzione booleana è espressa in Forma Standard se rispetta le seguenti regole:

La funzione è espressa su due livelli di porte logiche; ossia come:
- somma di prodotti: un gruppo di porte AND seguite da una porta OR;
- prodotto di somme: un gruppo di porte OR seguite da una porta AND.
I termini AND o OR possono contenere uno, due o più letterali, ma non è necessario che contengano tutti i letterali della funzione.
Ci si aspetta che le variabili di input siano disponibili anche con i loro complementi, quindi gli invertitori non sono inclusi nei diagrammi logici delle funzioni in forma standard.

Una funzione booleana può essere espressa in una forma non standard. Per esempio, la funzione

F_3 = AB + C(D + E)

non è né in forma somma-di-prodotti né in forma prodotto-di-somme, quindi la regola 1 viene violata.

L'implementazione di questa espressione è mostrata nella figura che segue e richiede due porte AND e due porte OR. Ci sono tre livelli di porte in questo circuito.

**Figura 3:** Diagramma Logico della Funzione F3 non in forma standard

Questa funzione può essere cambiata in una forma standard usando la legge distributiva per rimuovere le parentesi:

F_3 = AB + C(D + E) = AB + CD + CE

L'espressione somma-di-prodotti è implementata nella figura seguente:

**Figura 4:** Diagramma Logico della funzione F3 in forma standard

In generale, un'implementazione a due livelli è preferita perché produce la minima quantità di ritardo attraverso le porte quando il segnale si propaga dagli input all'output. Torneremo sul tempo di ritardo delle porte logiche nelle prossime lezioni.

Tuttavia, il numero di input a una data porta potrebbe non essere pratico. Ad esempio, potrebbe non essere possibile implementare un circuito con una porta OR che ha più di 4 o 5 input. In questi casi, si potrebbe dover usare un'implementazione a tre livelli.

Esempi Pratici

Vediamo alcuni esempi pratici di funzioni booleane in forma standard.

Esempio

Si prenda la funzione booleana $F$ espressa in forma standard:

F = A + B'C + AD

e la si esprima come somma di mintermini, ossia in prima forma canonica.

Per prima cosa, dobbiamo identificare i mintermini che compongono questa funzione. I mintermini sono le combinazioni di variabili che producono un risultato di 1 nella funzione. Dobbiamo, pertanto, trovare la tabella di verità della funzione $F$ :

**Tabella 1:** Tabella di verità della funzione F dell'esempio
$A$	$B$	$C$	$D$	$F$
0	0	0	0	0
0	0	0	1	0
0	0	1	0	1
0	0	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	0	0
0	1	1	1	0
1	0	0	0	1
1	0	0	1	1
1	0	1	0	1
1	0	1	1	1
1	1	0	0	1
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

Dalla tabella di verità, possiamo vedere che i mintermini che producono un risultato di 1 sono:

$A'B'CD'$ (riga 3 della tabella, corrispondente a $m_2$ )
$A'B'CD$ (riga 4 della tabella, corrispondente a $m_3$ )
$AB'C'D'$ (riga 9 della tabella, corrispondente a $m_8$ )
$AB'C'D$ (riga 10 della tabella, corrispondente a $m_9$ )
$AB'CD'$ (riga 11 della tabella, corrispondente a $m_10$ )
$AB'CD$ (riga 12 della tabella, corrispondente a $m_11$ )
$ABC'D'$ (riga 13 della tabella, corrispondente a $m_12$ )
$ABC'D$ (riga 14 della tabella, corrispondente a $m_13$ )
$ABCD'$ (riga 15 della tabella, corrispondente a $m_14$ )
$ABCD$ (riga 16 della tabella, corrispondente a $m_15$ )

Quindi, in forma compatta la funzione $F$ si esprime come:

F = \Sigma(2, 3, 8, 9, 10, 11, 12, 13, 14, 15)

Come si può vedere, la funzione $F$ in forma canonica ha una forma molto più complessa della forma standard vista sopra.

Esempio

Data la funzione $F$ in forma standard:

F = x'y + xz

vogliamo esprimerla in seconda forma canonica, ossia come prodotto di maxtermini.

Calcoliamo la tabella di verità della funzione $F$ :

**Tabella 2:** Tabella di verità della funzione F dell'esempio
$x$	$y$	$z$	$F$
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

I maxtermini che producono un risultato di 0 sono:

$x + y + z$ (riga 1 della tabella, corrispondente a $M_0$ )
$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 7 della tabella, corrispondente a $M_6$ )

Per cui, la funzione $F$ in forma canonica si esprime come:

F = \Pi(M_0, M_1, M_4, M_6)

ossia:

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

Anche in questo caso, la forma canonica della funzione $F$ è molto più complessa della sua forma standard.

Esempio

Ricaviamo il diagramma logico a due livelli per implementare la funzione booleana:

F = BC' + AB + ACD

**Figura 5:** Diagramma Logico della Funzione dell'Esempio

$A$	$B$	$C$	$D$	$F$
0	0	0	0	0
0	0	0	1	0
0	0	1	0	1
0	0	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	0	0
0	1	1	1	0
1	0	0	0	1
1	0	0	1	1
1	0	1	0	1
1	0	1	1	1
1	1	0	0	1
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

$A$	$B$	$C$	$D$	$F$
0	0	0	0	0
0	0	0	1	0
0	0	1	0	1
0	0	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	0	0
0	1	1	1	0
1	0	0	0	1
1	0	0	1	1
1	0	1	0	1
1	0	1	1	1
1	1	0	0	1
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

$A$	$B$	$C$	$D$	$F$
0	0	0	0	0
0	0	0	1	0
0	0	1	0	1
0	0	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	0	0
0	1	1	1	0
1	0	0	0	1
1	0	0	1	1
1	0	1	0	1
1	0	1	1	1
1	1	0	0	1
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1