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 realizzati con dispositivi che possono assumere solo due stati diversi: diodi in conduzione o non, transistor in saturazione o in interdizione, ecc.... Per il funzionamento del circuito logico non è importante conoscere il valore numerico 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è, attribuendo 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.
1
Funzioni booleane
Una 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 logico
Si 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,
A (1 = viene Marco,
B (1 = è bel tempo,
0 = non vado in barca)
0 = non viene Marco)
0 = è cattivo tempo)
dove A e B sono le variabili indipendenti e Q quella dipendente
2
Le “n” variabili possono assumere 2n configurazioni diverse; nella tabella della verità riportata nella figura sottote 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ò generalizzare l’equazione al caso di “n” variabili e dire che Q vale 1 se, e solo se, tutte le “n” variabili valgono 1. 3
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.
4
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*B
A+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.
5
NOT o negazione, complementazione
Si consideri la seguente proposizione logica:
vado in barca se non piove
I valori delle variabili sono:
Q (1 = vado in barca,
A (1 = piove,
0 = non vado in barca)
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.
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24