Funzioni Booleane

Concetti Chiave

Una funzione booleana è un'espressione algebrica che descrive una relazione logica tra variabili binarie.
Le funzioni booleane possono essere rappresentate in tabelle di verità, che mostrano il valore della funzione per tutte le combinazioni possibili delle variabili.
Un diagramma di circuito logico può essere creato da un'espressione booleana, mostrando come le porte logiche sono connesse per implementare la funzione.
Le funzioni booleane possono essere semplificate usando le identità dell'algebra booleana, riducendo il numero di porte e connessioni necessarie in un circuito.
Un letterale è una singola variabile in un termine di un'espressione booleana, che può essere in forma complementata o non complementata.
Un termine è un prodotto di letterali, e un'espressione booleana è una somma di termini.

Funzioni Booleane

L'algebra booleana è un'algebra che si occupa di variabili binarie e operazioni logiche.

Una funzione booleana descritta da un'espressione algebrica consiste di variabili binarie, le costanti 0 e 1, e i simboli delle operazioni logiche. Per un dato valore delle variabili binarie, la funzione può essere uguale a 1 o 0. Come esempio, consideriamo la funzione booleana

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

La funzione $F_1$ è uguale a 1 se $x$ è uguale a 1 o se sia $y'$ che $z$ sono uguali a 1. $F_1$ è uguale a 0 negli altri casi.

L'operazione di complemento stabilisce che quando $y' = 1$ , $y = 0$ . Pertanto, $F_1= 1$ se $x = 1$ o se $y = 0$ e $z = 1$ . Una funzione booleana esprime la relazione logica tra variabili binarie ed è valutata determinando il valore binario dell'espressione per tutti i possibili valori delle variabili.

Una funzione booleana può essere rappresentata in una tabella di verità. Il numero di righe nella tabella di verità è $2^n$ , dove $n$ è il numero di variabili nella funzione. Ad esempio, per la funzione $F_1$ con tre variabili, ci sono $2^3 = 8$ righe nella tabella di verità riportata di seguito:

**Tabella 1:** Tabella di Verità per la funzione F1
$x$	$y$	$z$	$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	1
1	1	0	1
1	1	1	1

Le combinazioni binarie per la tabella di verità sono ottenute dai numeri binari contando da 0 fino a $2^n - 1$ . La Tabella di sopra mostra la tabella di verità per la funzione $F_1$ . Ci sono otto possibili combinazioni binarie per assegnare bit alle tre variabili $x$ , $y$ , e $z$ . La colonna etichettata $F_1$ contiene 0 o 1 per ognuna di queste combinazioni. La tabella mostra che la funzione è uguale a 1 quando $x$ = 1 o quando yz = 01 ed è uguale a 0 altrimenti.

Una funzione booleana può essere trasformata da un'espressione algebrica in un diagramma circuitale composto da porte logiche connesse in una struttura particolare. Il diagramma del circuito logico (chiamato anche schema) per $F_1$ è mostrato nella figura che segue:

**Figura 1:** Diagramma del Circuito logico della funzione F1

C'è un invertitore per l'input $y$ per generare il suo complemento. C'è una porta AND per il termine $y'z$ e una porta OR che combina $x$ con $y'z$ . Nei diagrammi dei circuiti logici, le variabili della funzione sono prese come gli input del circuito e la variabile binaria $F_1$ è presa come l'output del circuito. Lo schema esprime la relazione tra l'output del circuito e i suoi input. Piuttosto che elencare ogni combinazione di input e output, indica come calcolare il valore logico di ogni output dai valori logici degli input.

C'è solo un modo in cui una funzione booleana può essere rappresentata in una tabella di verità. Tuttavia, quando la funzione è in forma algebrica, può essere espressa in una varietà di modi, ognuno dei quali ha logica equivalente. L'espressione particolare usata per rappresentare la funzione determinerà l'interconnessione delle porte nel diagramma del circuito logico. Viceversa, l'interconnessione delle porte determinerà l'espressione logica. Ecco un fatto chiave che motiva il nostro uso dell'algebra booleana: manipolando un'espressione booleana secondo le regole dell'algebra booleana, è talvolta possibile ottenere un'espressione più semplice per la stessa funzione e quindi ridurre il numero di porte nel circuito e il numero di input del circuito. I progettisti sono motivati a ridurre la complessità e il numero di porte perché il loro sforzo può ridurre significativamente il costo di un circuito.

Consideriamo, per esempio, la seguente funzione booleana:

F_2 = x'y'z + x'yz + xy'

Questa funzione ha la seguente tabella di verità:

**Tabella 2:** Tabella di Verità per la funzione F2
$x$	$y$	$z$	$F_2$
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	0

Uno schema di un'implementazione di questa funzione con porte logiche è mostrato nella figura che segue:

**Figura 2:** Diagramma Logico della funzione F2

Le variabili di input $x$ e $y$ sono complementate con invertitori per ottenere $x'$ e $y'$ . I tre termini nell'espressione sono implementati con tre porte AND. La porta OR forma l'OR logico dei tre termini. Dalla tabella di verità si può osservare come la funzione è uguale a 1 quando $xyz$ è uguale a 001 o a 011 o quando $xy$ è uguale a 10 (indipendentemente dal valore di $z$ ). In tutti gli altri casi la funzione $F_2$ è uguale a 0. Questo insieme di condizioni produce quattro 1 e quattro 0 per $F_2$ .

Ora consideriamo la possibile semplificazione della funzione applicando alcune delle identità dell'algebra booleana:

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

La funzione è ridotta a solo due termini e può essere implementata con meno porte logiche e meno connessioni come mostrato nella figura seguente:

**Figura 3:** Diagramma Logico minimizzato della funzione F2

È ovvio che il secondo circuito è più semplice di quello precedente, tuttavia entrambi implementano la stessa funzione. Per mezzo di una tabella di verità, è possibile verificare che le due espressioni sono equivalenti. L'espressione semplificata è uguale a 1 quando $xz = 01$ o quando $xy = 10$ . Questo produce gli stessi quattro 1 nella tabella di verità. Poiché entrambe le espressioni producono la stessa tabella di verità, sono equivalenti.

Pertanto, i due circuiti hanno gli stessi output per tutte le possibili combinazioni binarie di input delle tre variabili. Ogni circuito implementa la stessa identica funzione, ma quello con meno porte e meno input alle porte è preferibile perché richiede meno connessioni e componenti: in altre parole, il secondo circuito è più semplice e più economico da costruire.

In generale, ci sono molte rappresentazioni equivalenti di una funzione logica. Trovare la rappresentazione più economica della logica è un compito di progettazione molto importante a cui dedicheremo le prossime lezioni.

Manipolazioni Algebriche

Quando un'espressione booleana viene implementata con porte logiche, ogni termine richiede una porta e ogni variabile all'interno del termine designa un input per quella porta.

Definiamo un letterale come una singola variabile all'interno di un termine, in forma complementata o non complementata.

La funzione $F_2$ in versione non minimizzata:

F_2 = x'y'z + x'yz + xy'

ha tre termini e otto letterali, mentre la versione minimizzata:

F_2 = x'z + xy'

ha due termini e quattro letterali.

Riducendo il numero di termini, il numero di letterali, o entrambi, in un'espressione booleana, è spesso possibile ottenere un circuito più semplice. La manipolazione dell'algebra booleana consiste principalmente nel ridurre un'espressione con lo scopo di ottenere un circuito semplificato. Le funzioni fino a cinque variabili possono essere semplificate tramite il metodo delle mappe di Karnaugh che vedremo nelle prossime lezioni.

Per funzioni booleane complesse e con molti output differenti, i progettisti di circuiti digitali utilizzano programmi di minimizzazione computerizzati in grado di produrre circuiti ottimali con milioni di porte logiche. I concetti introdotti in queste lezioni forniscono il quadro di riferimento per questi strumenti. L'unico metodo manuale disponibile è un procedimento tentativo basato sulle relazioni fondamentali e su altre tecniche di manipolazione, che, pur diventando familiari con l'uso, rimangono comunque soggette ad errori umani. Gli esempi che seguono illustrano la manipolazione algebrica dell'algebra booleana per familiarizzare il lettore con questo importante compito di progettazione.

Esempi di minimizzazione

Proviamo a minimizzare le seguenti espressioni booleane in modo da ottenere un numero minimo di letterali.

Esempio

x(x' + y) =

xx' + xy =

0 + xy =

= xy

Esempio

x + x'y

Se si osserva bene, questa espressione è la duale della precedente. La minimizzazione procede come segue:

x + x'y =

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

1(x + y) =

= x + y

Esempio

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

x + xy' + xy + yy' =

x(1 + y + y') =

= x

Esempio

xy + x'z + yz =

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

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

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

xy + x'z

Esempio

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

Per dualità dall'esempio precedente, si ha:

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

(x + y)(x' + z)

Complemento di una Funzione

Il complemento di una funzione $F$ è $F'$ e si ottiene dallo scambio degli 0 con 1 e degli 1 con 0 nel valore di $F$ . Il complemento di una funzione può essere derivato algebricamente attraverso i teoremi di DeMorgan, visti nella lezione precedente per due variabili. I teoremi di DeMorgan possono essere estesi a tre o più variabili. La forma a tre variabili del primo teorema di DeMorgan è derivata come segue, dai postulati e teoremi elencati nella lezione precedente:

Dimostrazione

Estensione del primo teorema di DeMorgan a tre variabili

Vogliamo dimostrare che:

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

Per prima cosa, poniamo $x = B + C$ .

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

per il teorema di DeMorgan abbiamo che

= A'x'

Sostituendo $x = B + C$ abbiamo:

= A'(B + C)'

all'interno della parentesi, per il teorema di DeMorgan, si ha:

= A'(B'C')

e per la proprietà associativa:

= A'B'C'

abbiamo dimostrato il teorema.

I teoremi di DeMorgan per qualsiasi numero di variabili assomigliano al caso a due variabili nella forma e possono essere derivati per sostituzioni successive simili al metodo usato nella dimostrazione precedente. Questi teoremi possono essere generalizzati come segue:

(A + B + C + D + \cdots + F)' = A'B'C'D' \cdots F'

(ABCD \cdots F)' = A' + B' + C' + D' + \cdots + F'

Il risultato fondamentale che si ricava dai teoremi di DeMorgan è il seguente:

Definizione

Complemento di una funzione

Per ottenere il complemento di una funzione booleana bisogna:

Scambiare gli operatori AND e OR;
Complementare ogni letterale.

Esempi di Complemento di una Funzione

Vediamo ora alcuni esempi di come calcolare il complemento di una funzione booleana.

Esempio

Si trovi il complemento della funzione:

F_1 = x'yz' + x'y'z

Sfruttando il risultato fondamentale, per calcolare il complemento di $F_1$ , convertiamo dapprima tutti gli operatori AND in OR e viceversa:

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

poi complementiamo ogni letterale:

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

Esempio

Si trovi il complemento della funzione:

F_2 = x(y'z + yz)

Anche in questo caso, dapprima convertiamo gli operatori AND in OR e viceversa:

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

Poi complementiamo ogni letterale:

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

Se poi espandiamo l'ultima espressione, otteniamo:

F'_2 = x' + yy' + yz' + y'z + z'z'

F'_2 = x' + yz' + y'z

Esempio

Esempio

Rappresentiamo il diagramma logico della funzione booleana:

F = x'y + xy'

Andiamo per ordine. Per prima cosa, abbiamo bisogno di una porta OR a due ingressi che combini i due termini $x'y$ e $xy'$ :

**Figura 4:** Implementazione della funzione F: Passo 1

Poi, abbiamo bisogno di due porte AND a due ingressi, una per ciascun termine:

**Figura 5:** Implementazione della funzione F: Passo 2

Infine, abbiamo bisogno di due invertitori per generare i complementi delle variabili $x$ e $y$ :

**Figura 6:** Implementazione della funzione F: Passo 3

Adesso troviamo la tabella di verità per la funzione booleana dell'esempio:

F = x'y + xy'

La risposta è:

**Tabella 3:** Tabella di Verità per la funzione F
x	y	F
0	0	0
0	1	1
1	0	1
1	1	0