Corso di Calcolatori Elettronici I

Algebra di Boole

Lezione 5
Prof. Simon Pietro Romano
 Da Boole a Shannon
• L’algebra di Boole fu introdotta nel 1854
come strumento per la soluzione
matematica di problemi di logica
• George Boole (1815-1864)
– An investigation into the laws of thought on
which are founded the mathematical theories
of logic and probabilities (1854)
• Il suo uso per descrivere reti binarie di
commutazione si deve a Claude Shannon
– A symbolic analysis of relay and switching
circuits (1938)
 Algebra di Boole
• L’Algebra di Boole può essere vista come
un’algebra astratta definita su un supporto K =
{0,1} e tre operazioni
– AND (⋅): K×K→K
– OR (+): K×K→K
– NOT (¬): K →K

x y x AND y x y x OR y x NOT x
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1
 Algebra di Boole: proprietà (1)

• Proprietà commutativa:
x AND y = y AND x x OR y = y OR x
• Proprietà associativa:
(x AND y) AND z = x AND (y AND z)
(x OR y) OR z = x OR (y OR z)
• per la proprietà associativa posso definire AND e OR a più di 2 operandi
• es. x AND y AND z = (x AND y) AND z = x AND (y AND z)
• Proprietà di idempotenza:
x AND x = x x OR x = x
• Proprietà di assorbimento:
x AND (x OR y) = x x OR (x AND y) = x
Algebra di Boole: proprietà (2)

• Proprietà distributiva
x AND (y OR z) = (x AND y) OR (x AND z)
x OR (y AND z) = (x OR y) AND (x OR z)
• Proprietà di convoluzione
NOT (NOT x) = x
• Proprietà del minimo e del massimo:
x AND 0 = 0
x OR 1 = 1
 Algebra di Boole come reticolo (1)
• Un’algebra astratta è una terna <K, ·,+> costituita da un
insieme K (sostegno) sul quale sono definite due leggi
binarie di composizione interna “+” e “·”
⋅: K × K → K
+: K × K → K
• Un'algebra astratta <K,+, ⋅> si dice reticolo se per ogni
coppia di elementi di K le operazioni “+” e “·” soddisfano
le proprietà commutativa, associativa, di assorbimento e di
idempotenza
• Un reticolo nel quale vale la proprietà distributiva sia di “+”
rispetto a “·” che di “·” rispetto a “+” si dice reticolo
distributivo
 Proprietà dei reticoli
• I reticoli sono ordinati, ovvero
posseggono una relazione d’ordine “≤”
così definita
def
x≤y⇔x+y=y⇔x⋅y=x
w Ricordiamo che una relazione d’ordine “≤”
deve godere delle seguenti proprietà:
n riflessiva: x ≤ x
n antisimmetrica: x ≤ y e y ≤ x => x = y
n transitiva: x ≤ y e y ≤ z => x ≤ z
 Algebra di Boole come algebra astratta
• Un reticolo distributivo si dice dotato di minimo e massimo
assoluti se in K sono presenti due elementi - che
indicheremo con 0 e 1 rispettivamente - i quali verificano la
proprietà del minimo e massimo per ogni elemento a di K:
a · 0 = 0 (0 ≤ a) a + 1 = 1 (a ≤ 1)
• Un reticolo distributivo si dice complementato se per ogni
elemento a di K esiste ed è unico un elemento (che diremo
complemento di a ed indicheremo con ¬a) per il quale è
valida la proprietà del complemento:
a · ¬a = 0 a + ¬a = 1
• Un reticolo distributivo, dotato di minimo e massimo
assoluti e complementato, si dice un'algebra di Boole
• L’algebra a due valori definita nelle slide precedenti
ne rappresenta un caso particolare
 AdB come reticolo:
postulati definitori
Commutativa P1 a+b=b+a P’1 a•b=b•a

Associativa P2 (a+b)+c =a+(b+c) P’2 (a•b) •c=a• (b•c)

Idempotenza P3 (a+a)=a P’3 (a•a)=a

Assorbimento P4 a+(a•b)=a P’4 a• (a+b)=a

Distributiva P5 a• (b+c)=a•b+a•c P’5 a+(b•c)=(a+b)•(a+c)

Min e max P6 a•0=0 P’6 a+1=1

Complemento P7 a•(ā)=0 P’7 a+(ā)=1

 Legge di dualità
• Da qualsiasi identità booleana se ne può
trarre un'altra per dualità, sostituendo cioè
ad ogni operatore e agli elementi 0 ed 1 il
rispettivo duale
• In altre parole, i 14 postulati impiegati per
definire l'algebra non sono tutti
indipendenti fra loro
 Teorema di De Morgan

NOT (x AND y) = (NOT x) OR (NOT y)

NOT (x OR y) = (NOT x) AND (NOT y)

 AdB: altre proprietà
• 0 ed 1 sono l’uno il complemento dell’altro
¬0 = 1 ¬1 = 0
• Convoluzione: negando due volte un
elemento si ottiene l’elemento stesso
¬(¬ a) = a
• 0 è l’elemento neutro della somma
a+0=a
• 1 è l’elemento neutro del prodotto
a⋅1=a
 Assorbimento del complemento

a + ab = a + b
w Per la dimostrazione usate la proprietà distributiva
ed infine il complemento
 Teorema di De Morgan
a ⋅ b= a + b (1) (1.1) Dimostrazione
a + b = a ⋅b (2) a + b + a ⋅b = a + a ⋅b + b + a ⋅b = ( P 1,P 3)

= a + b + b +a= ( ass .comp )

=a+a +b+b = ( P 1)

(a + b)+ (a ⋅ b) = 1 (1.1) = 1+ 1 = 1 ( P '7,P '6)

(a + b) ⋅ (a ⋅ b) = 0 (1.2)
(1.2) Dimostrazione
(a + b ) ⋅ a ⋅ b = a ⋅ a ⋅ b + b ⋅ a ⋅ b = ( P 5)

= 0⋅b + 0⋅a= ( P 7)

=0+0 =0 ( P 6,P 3)

La (1) vale per dualità

 Principio di eliminazione
• Nell’algebra di Boole non vale il principio
di eliminazione
• x+y=x+z non implica necessariamente y=z
• L’implicazione vale se è verificata la
condizione aggiuntiva x⋅y=x⋅z
 Algebre di Boole (al plurale)
• La definizione di AdB come reticolo non
specifica quale sia K e come siano definite le
operazioni “+” , “·” e “¬”
– Specifica soltanto un insieme di proprietà che devono
essere soddisfatte da tali operazioni
• Sono così possibili diversi modelli di algebra di
Boole , uno dei quali è quello introdotto all’inizio
• Altri possibili modelli di algebra di Boole:
– l’algebra dei circuiti
– l’algebra della logica delle proposizioni
– l’algebra degli insiemi
 Algebra della logica
• L’insieme K={F,V} su cui siano definite le operazioni
• Congiunzione(^)
• Disgiunzione (v)
• Negazione (¬)
è un’algebra di Boole con F = 0, V = 1,
congiunzione = ⋅ , disgiunzione = +, negazione = ¬

x y x^y x y xvy x ¬x
F F F F F F F V
F V F F V V V F
V F F V F V
V V V V V V
 Algebra delle logica
• Due funzioni notevoli nell’algebra delle proposizioni:
a⇔b
– Funzione equivalenza
f (a, b) = ab + ab

– Funzione implicazione a ⇒ b, f (a, b) = a + b

Si dice che x implica y se e solo se dalla verità di x (antecedente) scaturisce

necessariamente la verità di y (conseguente). In termini algebrici, essendo
l’implicazione falsa se e solo se x è vera e y è falsa, applicando il Teorema di De
Morgan, si ha
x ⇒ y = xy
x⇒y =x+y
 Algebra della logica
• Se x ⇒ y è vera, allora x + y = 1
x + y = x ⋅y + y ( ass .compl )

= x ⋅ y + xy + y ( P 4)

= x ⋅ y ⋅ y + xy + yy ( P 3)

= (x + y ) ⋅ y + (x + y ) ⋅ y = 1 ( DeMorgan )

per le proprietà dell’equivalenza

ab + ab
x+y =y ⇔x ≤y

l'implicazione è la relazione d'ordine nell'algebra della logica

Algebra degli insiemi
Algebra degli insiemi (2)
 Algebra degli insiemi (3)
• Dati due insiemi A,B ∈ T,sono definite le operazioni di
• Unione (∪)
• Intersezione (∩) A∩B
• Complemento (~)
T A∪B
A B
a ∩ Φ= Φ
a ∪ T= T
Diagramma
di Venn

la sestupla ‹K, ∪, ∩, ~,Φ,T› è un’algebra di Boole

ove:
– K indica l’insieme delle parti di T
– Φ indica l’insieme vuoto
• La relazione d’ordine ≤ equivale alla relazione di inclusione tra insiemi
 Teorema di Stone
• Ogni algebra di Boole è rappresentabile su
un'algebra di insiemi
• Il modello degli insiemi (equivalentemente
i diagrammi di Venn) può essere assunto
come strumento per verificare o
dimostrare proprietà di una qualsiasi
algebra di Boole

23
 Circuiti logici
• I circuiti logici sono circuiti elettronici nei quali una grandezza
elettrica ai morsetti di ingresso e di uscita può assumere solo due
valori , convenzionalmente rappresentati con i due elementi
dell’algebra di Boole 0 ed 1.
• In elettronica digitale si studia come realizzare circuiti elettronici per i
quali il legame tra ingressi ed uscite corrisponde a quello delle
operazioni fondamentali AND, OR e NOT dell’algebra di Boole
– PORTE LOGICHE
• Nelle reti logiche unilaterali, le uscite della rete corrispondono a
valori di grandezze elettriche misurate in opportuni punti del circuito;
il flusso dell’elaborazione procede fisicamente in un’unica direzione,
dai segnali di ingresso verso i segnali di uscita
– Es. la d.d.p. misurata rispetto a massa
• Nelle reti logiche bilaterali, invece, l’uscita della rete è determinata
dalla presenza o dall’assenza di “contatto” tra due punti della rete.
Segnali in circuiti elettronici digitali

da: G. Bucci. Calcolatori Elettronici – Architettura e organizzazione. © McGraw-Hill, 2009

 Porte logiche o gate
Circuiti elettronici che realizzano le operazioni fondamentali

x
z z = x AND y
y

x
z z = x OR y
y

x y y = NOT x
Un esempio di rete logica

y = b ⋅ c ⋅ (a ⋅ d + b + c) + c ⋅(d + a) ⋅ (b + c)