1

Algebra Booleana

Generalità

In quasi tutti i tipi di calcolatori elettronici le informazioni vengono elaborate in forma digitale, ossia i segnali elettri-

ci che le rappresentano possono assumere due soli valori distinti. I circuiti che eseguono queste elaborazioni sono

chiamati circuiti logici e presentano, appunto, la caratteristica di operare con segnali binari. Vengono pertanto rea-

lizzati con dispositivi che possono assumere solo due stati diversi: diodi in conduzione o non, transistor in satura-

zione o in interdizione, ecc.... Per il funzionamento del circuito logico non è importante conoscere il valore numeri-

co del segnale binario, ma basta rilevarne il livello; in genere questo può essere indicato con “0” ed “1” o con “L”

ed “H” (Low = basso, High = alto). Il funzionamento di un tale circuito può quindi essere descritto da un punto di

vista logico senza preoccuparsi della sua struttura fisica; allo scopo può essere utilizzata l’algebra di Boole (G.

Boole, 1815- 1864). L’algebra di Boole, o algebra binaria, è infatti una logica matematica basata su due diverse

situazioni che si escludono reciprocamente. Per variabile booleana si intende una qualunque grandezza che può

assumere due soli stati (interruttore aperto o chiuso, affermazione vera o falsa, lampada accesa o spenta, livello

di tensione alto o basso, diodo in conduzione o non, ecc...). Ai due diversi livelli logici vengono associati i simboli

“0” ed “1”. Le generiche variabili vengono identificate da lettere (per esempio a, b, c ........; A, B, C, ecc.........) e,

ad ognuno dei due stati logici che possono assumere, può essere associato, arbitrariamente, il valore “0” o “1”.

Nel 1938 Shannon applicò le regole dell’algebra di Boole alla progettazione di circuiti di commutazione a relè, at-

tribuendo i valori “1” e “0” ai due stati fisici di questi due dispositivi. Questo metodo è tuttora utilizzato per l’analisi

e la sintesi dei circuiti in quanto consente di esplicitare a mezzo di funzioni booleane le connessioni dei circuiti e le

operazioni da esse eseguite.

2

Funzioni booleaneUna funzione booleana, infatti, fornisce un’uscita logica in corrispondenza di

ogni combinazione dei livelli delle variabili d’ingresso.

Le operazioni fondamentali dell’algebra di Boole sono le seguenti:- AND o prodotto logico- OR o somma logica- NOT o negazione, complementazione

AND o prodotto logicoSi consideri la seguente proposizione logica:

vado in barca se viene anche Marco ed è bel tempo

La gita in barca è condizionata dall’avverarsi di entrambi le condizioni poste

- Se si assegnano alle variabili i valori “0” ed “1” si può scrivere:

Q (1 = vado in barca, 0 = non vado in barca)A (1 = viene Marco, 0 = non viene Marco)B (1 = è bel tempo, 0 = è cattivo tempo)

dove A e B sono le variabili indipendenti e Q quella dipendente

3

Le “n” variabili possono assumere 2n configurazioni diverse; nella tabella della verità riportata nella figura sotto- te vengono prese in considerazione le quattro (22) combinazioni con il corrispondente livello assunto dalla variabile dipendente.

Nella figura è altresì riportato un circuito ad interruttori per realizzare una porta AND ed il simbolo grafico della stessa secondo gli standard USA e I.E.C..L’equazione logica (prodotto logico) che sintetizza le combinazioni riportate nella tabella è la seguente:

Q = A x B La Q si trova al livello “alto” solo se entrambe le variabili indipendenti A e B assumono questo livello. Si può gene-ralizzare l’equazione al caso di “n” variabili e dire che Q vale 1 se, e solo se, tutte le “n” variabili valgono 1.

4

Or o somma logica- Si consideri la seguente proposizione logica:

la barca a vela si muove se c’è vento o se remo

Affinché la barca si muova è sufficiente che si verifichi una sola delle due condizioni sopra enunciate.Se, anche in questo caso, si assegnano alle variabili i valori “0” ed “1” si può scrivere:

Q (1 = la barca si muove, 0 = la barca non si muove)

A (1 = c’è vento, 0 = non c’è vento)

B (1 = io remo, 0 = io non remo),Dove A e B sono variabili indipendenti e Q quella dipendente.

Nella figura seguente è riportata la tabella della verità della proporzione logica in esame nella quale si evidenzia che Q è a livello “basso” (0) solo se entrambe le variabili indipendenti sono a livello “0” .

Nella figura è altresi riportato un circuito ad interruttori per realizzare una porta OR e i due simboli grafici della stessa porta secondo gli standard USA e I.E.C.

5

L’equazione logica (somma logica) che sintetizza le combinazioni riportate nella tabella della verità è la seguente:

Q = A + B

Si può generizzare l’equazione al caso “n” variabili e dire che Q vale 1 se una sola delle n variabili vale 1.

Per le funzioni AND ed OR, prima esaminate, valgono le seguenti proprietà:

1) Commutativa A * B * C = C * A * BA + B + C = C + A + B

2) Associativa ( A * B ) * C = A * ( B * C )( A + B ) + C = A + ( B + C )

3) Distributiva A * ( B + C ) = ( A * B ) + ( A * C )

A + ( B * C ) = ( A + B ) * ( A + C )

Le proprietà precedenti, come tutti i teoremi dell’algebra booleana, possono essere verificate confrontando le tabelle della verità di ogni relazione.

6

NOT o negazione, complementazioneSi consideri la seguente proposizione logica:

vado in barca se non pioveI valori delle variabili sono:

Q (1 = vado in barca, 0 = non vado in barca)A (1 = piove, 0 = non piove)

Dove A è la variabile indipendente e Q quella dipendente. A queste condizioni corrisponde la seguente equazione

algebrica:

Q = Ā A livello simbolico, per negare una grandezza si deve soprassegnare il simbolo.

Ovviamente una doppia negazione riporta alla variabile non negata.=A = A

Nella figura riportata qui di seguito è rapresentato un circuito a relè per realizzare una porta NOT

e I due simboli grafici della stessa porta secondo gli standard USA e I.E.C.

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24