Algebra di Boole e
Funzioni Binarie
--
Sommario
•
•
•
•
•
•
•
Variabili Binarie
Negazione
Somma Logica
Prodotto Logico
Relazioni- proprietà
Funzioni
Minterm
•
•
•
•
Teoremi
Maxterm
Forme Canoniche
Fine lezione
Algebra di Boole
2
Variabili Binarie
• Variabile binaria: grandezza matematica
che può assumere due soli valori: 0 o 1.
• Sulle variabili binarie definiamo tre
operatori: negazione, somma e prodotto.
• La negazione di una variabile binaria a si
indica con a’ (“non a” o “a negato”)
oppure con ( a o con ā )
Algebra di Boole
3
Negazione
• Possiamo rappresentare il valore di x’
tramite tabella di verità:
x
x’
0
1
1
0
Modi equivalenti per negare una variabile X
~
X , X ', X o , X , X
Algebra di Boole
4
Somma logica
• La somma di n variabili binarie x1, x2, x3, --- xn vale 0
solo se tutte le xi (1≤i≤n) valgono contemporaneamente
0, vale 1 in ogni altro caso.
x1
x2
x1 + x2
0
0
0
0
1
1
1
0
1
1
1
1
esempio di somma logica di due variabili x1 e x2 mediante tabella di verità
Algebra di Boole
5
Prodotto logico
• Il prodotto di n variabili binarie x1, x2, x3, --- xn vale
1 solo se tutte le xi (1≤ i ≤n) sono contemporaneamente
1, vale 0 in ogni altro caso
x1
x2
x1 . x2
0
0
0
0
1
0
1
0
0
1
1
1
esempio di prodotto logico di due variabili x1 e x2 mediante tabella di verità
Algebra di Boole
6
Relazioni e proprietà
• Le relazioni e proprietà degli operatori somma e
prodotto logico sono riportate nella tabella
Somma
Prodotto
x+1=1
x·0=0
x+0=x
x·1=x
x1 + x2 = x2 + x1
x1 · x2 = x2· x1
x1 + x2 + x3 = (x1 + x2) + x3 x1 · x2· x3= (x1 · x2) · x3
x1· x2+ x1· x3= x1· (x2 + x3)
(x1 + x2) · (x1 + x3) = x1+ x2 · x3
Algebra di Boole
7
Relazioni e proprietà
• Per la negazione valgono le seguenti relazioni
e proprietà:
Negazione
0’’ = 0
1’’ = 1
x’’ = x
x + x‘ = 1
x
·
x’ = 0
x’’  x due volte negato
Algebra di Boole
8
Funzioni
• Con n variabili binarie (x1, x2, … xn) si possono formare 2n
configurazioni diverse.
• Se prendiamo, ad esempio, 2 variabili: x1, x2 dato che ognuna di
loro può valere 0 od 1, si possono creano le seguenti quattro (22)
configurazioni diverse: 00, 01, 10, 11.
• Così con 3 variabili binarie si potranno formare al massimo 23=8
configurazioni diverse che sono:
000, 001, 010, 011, 100, 101, 110, 111.
Algebra di Boole
9
Funzioni
• Diremo che una variabile y è funzione di n
variabili indipendenti x1, x2, … xn e si scrive:
y = F (x1, x2, … xn)
• quando esiste un criterio che fa corrispondere in
modo univoco ad ognuna delle 2n configurazioni di
x un determinato valore y (ovviamente 0 o 1).
Algebra di Boole
10
Funzioni
• Tutte le diverse funzioni di n variabili (x1,x2,…xn)
che si possono costruire sono pari a
2
2n
• Ad esempio tutte le diverse funzioni che si possono
formare con 3 variabili sono pari a
2  2  256
23
8
Algebra di Boole
11
Funzioni
• Una funzione può essere rappresentata
sotto forma di tabella di verità, scrivendo
accanto ad ognuna delle 2n diverse
configurazioni di x1, x2, … xn il valore
assunto dalla y.
• Ad esempio la seguente tabella
rappresenta la tabella di verità di una
delle 256 funzioni possibili di tre variabili
binarie
Cliccare sull’immagine
Algebra di Boole
12
Funzioni
Una tabella delle 256
funzioni a 3 variabili
Cliccare sull’immagine
Algebra di Boole
13
Minterm
•
Se consideriamo 3 variabili, la scrittura x1x2x3 = 011 indica
tra le 23=8 configurazioni possibili, quella in cui x1 vale 0, x2
vale 1 e x3 vale 1.
•
Questa configurazione si scrive semplicemente con il prodotto
•
Se in una configurazione una variabile compare con 1 si assume il
valore diretto se invece compare con uno 0 si assume il valore
negato.
•
Consideriamo la funzione di 3 variabili rappresentata sotto forma
di tabella di verità in fig.1 e le 3 configurazioni in cui la stessa
vale 1
•
Avremo che la funzione vale 1 per le seguenti configurazioni:
x1x2x3 ( questo e’ un minterm)
x1x2x3
x1x2x3
x1x2x3
Ciascuno di questi prodotti si chiama minterm
Algebra di Boole
14
Minterm
•
Conoscendo la tabella di verità fi una
funzione , la espressione algebrica potrà
essere espressa sotto forma di somme di
prodotti dei termini minimi.
•
Nel caso della funzione in Fig 1 scriveremo
y = x1x2x3 + x1x2x3 + x1x2x3
•
Se una funzione è direttamente espressa
sotto forma di somme di minterm sarà
possibile costruire la sua tabella di verità,
mettendo 1 nelle configurazioni relative ai
minterm, e 0 negli altri casi.
Algebra di Boole
15
Minterm
• Ad esempio data la funzione di 3 variabili
F(x,y,z) = xy’z + xyz’ + x’yz
la sua tabella di verità sarà:
x
y
z
F(x,y,z)
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
xy’z
1
0
1
1
xyz’
1
1
0
1
1
1
1
0
x’yz
Algebra di Boole
16
Teoremi
TEOREMI
Idempotenza
Assorbimento
De Morgan
Diretto
Versione Duale
x + x + x + ---+ x = x
x · x · x · --- ·x = x
x + xy = x
x · (x +y) = x
x + x’y = x + y
x · (x’ + y) = x · y
xy +yz + x’z = xy + x’z
(x +y)·(y+z)·(x’+z) = (x+y) · (x’+z)
(x+y)’ = x’ · y’
(x · y)’ = x’ + y’
Algebra di Boole
17
Maxtem
• Il teorema di De Morgan applicato alla funzione
della fig.1 ci consente di scrivere la funzione in
questo modo:
• y = (x1+x2+x3)· (x1+x2+x3)· (x1+x2+x3)·
·(x1+x2+x3)·
(x1+x2+x3)
• ossia sotto forma di prodotto di somme.
• Ciascuna delle somme chiama maxterm (termine
massimo).
Algebra di Boole
18
Maxtem
• L’espressione della y come prodotto di maxterm
si può ottenere dalla tabella di verità della
funzione;
•
ci sono tanti maxterm quanto sono i valori 0
della funzione;
• ogni maxterm è la somma di tutte le variabili
dirette
o
negate
a
seconda
che
la
configurazione contenga 1 o 0.
Algebra di Boole
19
Forma Canonica
• Entrambe le espressioni della funzione sotto
forma di:
– somme di prodotti (minterm)
– prodotti di somme (maxterm)
• si chiamano forme canoniche di una funzione
binaria.
Algebra di Boole
20
MACCHINA DEL CAFFE’/Te’
• ESEMPIO : Costruire un circuito logico che simuli
una macchina che fornisce (previo inserimento di
una moneta) caffè o tè.
• Se selezioniamo il pulsante del caffè la macchina
dovrà fornire il caffè.
• Se selezioniamo il pulsante del tè la macchina
dovrà fornire il tè.
• Se selezioniamo entrambi i pulsanti (del Tè e del
caffè) la macchina dovrà fornire Tè.
Algebra di Boole
21
Costruiamo la tabella di verità della macchina
S C T
0
0
0
0
1
1
1
1
0
1
1
0
0
1
0
1
0
0
1
1
0
0
1
1
Uscita-Tè Uscita-caffè
0
0
0
0
0
0
1
1
Algebra di Boole
0
0
0
0
0
1
0
0
22
Sfruttiamo la rappresentazione
con i minterm
per la colonna UC= Uscita-caffè
Uc  S * C *T  (C * S )*(C *T )
Ricordare DE-MORGAN
Algebra di Boole
23
• Sfruttiamo la rappresentazione con i
minterm
per la colonna UT= Uscita-Tè
UT  S * C *T  S * C *T  S *T
Algebra di Boole
24
E ORA IL CIRCUITO
Grazie a queste relazioni possiamo ottenere il circuito logico richiesto:
Algebra di Boole
25
Prossima Lezione:
ARCHITETTURA DEGLI
ELABORATORI
Arrivederci!