Fondamenti di Informatica IIIngegneria Informatica e Biomedica
I anno, II semestreA.A. 2005/2006
Prof. Mario CannataroUniversità degli Studi “Magna Graecia”di Catanzaro
Algebra di Boole
Fondamenti Informatica II - Lez. 01 22.03.2006 2
Algebra Booleana :Introduzione
Tutti i dispositivi elettronici correntemente usati si basano sull’elaborazione di valori discreti di grandezze elettriche espressi da numeri binari.
Il modello teorico di rappresentazione èrappresentato dall’algebra di BOOLE, che a sua volta è basata sulla logica classica.
Fondamenti Informatica II - Lez. 01 22.03.2006 3
Funzioni booleane (1/2)
{ }1,0 ∈z
Definizione di funzione booleana
Una funzione z = f(x1, x2, … , xn) si dice booleana se:
{ }1,0...1 ∈= nixEssendo funzioni discrete, le funzioni booleane possono essere rappresentate in forma tabellare.
Fondamenti Informatica II - Lez. 01 22.03.2006 4
Funzioni booleane (2/2)
Obiettivo: Esprimere una generica funzione f come combinazione di operatori elementari.
Fondamenti Informatica II - Lez. 01 22.03.2006 5
Algebra Booleana: Definizione
Dominio: NUMERI BINARI (COSTANTI E VARIABILI)
OperazioniBinarie :AND,OR,XOR,NAND,NOR.Unarie :NOT.
Funzioni { } { }1,01,0: →nf
Fondamenti Informatica II - Lez. 01 22.03.2006 6
Alcuni esempi di funzioni booleane
10
01
f(x1)x1
NOT
1
1
0
0
x1
00
11
10
11
f(x1, x2)x2
OR
1
1
0
0
x1
00
01
00
11
f(x1, x2)x2
AND
Fondamenti Informatica II - Lez. 01 22.03.2006 7
Funzioni standard e simboli circuitali
Fondamenti Informatica II - Lez. 01 22.03.2006 8
Proprietà dell’algebra Booleana
¬ (A + B)= ¬ A * ¬ B¬ (A * B)= ¬ A + ¬ BDeMorganA + A * B = AA * (A + B)= AAssorbimento
A *( B+C) = (A*B) + (A*C)A +(B*C) = (A+B) * (A+C)Distributiva(A + B)+ C = A + (B + C)(A * B) * C = A * (B * C) AssociativaA + B = B + AA * B = B * ACommutativa
A + ¬ A =1A * ¬ A = 0InversoA + A = AA * A = AIdempotenza1 + A = 10 * A = 0Elemento Nullo0 + A = A1 * A = A Indentità
ORANDLegge
Fondamenti Informatica II - Lez. 01 22.03.2006 9
Teorema di De Morgan
Ad Esempio la somma di due variabili può esseretrasformata in prodotto come segue
¬ (A + B)= ¬ A * ¬ B
Oppure il prodotto può essere trasformato in somma:
¬ (A * B)= ¬ A + ¬ B
Fondamenti Informatica II - Lez. 01 22.03.2006 10
Rappresentazione tabellare di una funzione booleana
UscitaVariabili d’ingressoNumero d’ordine
11 1 1701 1 0611 0 1501 0 0400 1 1300 1 0210 0 1110 0 00zx1 x2 x3
z
x1
x2
x3
Fondamenti Informatica II - Lez. 01 22.03.2006 11
Definizione di mintermine e maxtermine
Un mintermine pi è una funzione che vale 1 in corrispondenza della sola configurazione i di valori delle variabili
Un maxtermine si è una funzione che vale 0 in corrispondenza della sola configurazione i di valori delle variabili
Fondamenti Informatica II - Lez. 01 22.03.2006 12
Ancora sui mintermini ed i maxtermini
Un mintermine pi può essere rappresentato da un’espressione algebrica consistente nell’AND di tutte le variabili, dove ogni variabile compare diretta se vale 1 nella configurazione i, negata altrimenti
Un maxtermine si può essere rappresentato da un’espressione algebrica consistente nell’OR di tutte le variabili, dove ogni variabile compare negata se vale 1 nella configurazione i, diretta altrimenti
Fondamenti Informatica II - Lez. 01 22.03.2006 13
Esempi di mintermini e maxtermini
11101111s4
11110111s3
11111011s2
Maxtermini( 0 )
10000000p7
00100000p5
00000010p1
00000001p0
Mintermini( 1 )
10100011z
UscitaVariabili d’ingresso
Numero d’ordine
11 1 1701 1 0611 0 1511 0 0410 1 1310 1 0210 0 1110 0 00s6x1 x2 x3
3216
3214
3213
3212
3217
3215
3211
3210
xxxsxxxsxxxsxxxs
xxxpxxxpxxxpxxxp
++=++=++=++=⋅⋅=⋅⋅=⋅⋅=⋅⋅=
Fondamenti Informatica II - Lez. 01 22.03.2006 14
I e II forma canonica di una funzione
La I forma canonica di una funzione f è l’OR di tutti i mintermini pi per le configurazioni i dove f = 1. Tale forma è anche detta forma SP (somma di prodotti)
La II forma canonica di una funzione f è l’AND di tutti i maxtermini si per le configurazioni i dove f = 0. Tale forma è anche detta forma PS (prodotto di somme)
Fondamenti Informatica II - Lez. 01 22.03.2006 15
Esempio pratico
3216
3214
3213
3212
3217
3215
3211
3210
xxxsxxxsxxxsxxxs
xxxpxxxpxxxpxxxp
++=++=++=++=⋅⋅=⋅⋅=⋅⋅=⋅⋅=
)()()()(
321321
3213216432
321321
3213217510
xxxxxxxxxxxxssssz
xxxxxxxxxxxxppppz
++⋅++⋅⋅++⋅++=⋅⋅⋅=
⋅⋅+⋅⋅++⋅⋅+⋅⋅=+++=
Se richiamiamo i mintermini ed i maxterminidell’esempio precedente:
∏∑
=⋅⋅⋅=
=+++=
36432
37510
)6,4,3,2(
)7,5,1,0(
ssssz
ppppz
Fondamenti Informatica II - Lez. 01 22.03.2006 16
Riduzione algebrica di funzioni
Utilizzando le proprietà dell’algebra in modo opportuno è possibile semplificare le forme canoniche di una funzione. Nell’esempio precedente:
31213221
3321321321
3213217510
)()(
xxxxxxxxxxxxxxxxxx
xxxxxxppppz
⋅+⋅=⋅+⋅+++⋅=⋅⋅+⋅⋅+
+⋅⋅+⋅⋅=+++=
Fondamenti Informatica II - Lez. 01 22.03.2006 17
Completezza funzionaleL’esistenza delle forme canoniche è una dimostrazione che le funzioni AND, OR e NOT costituiscono un insieme funzionalmente completo, ovvero ciascuna funzione può essere scritta in una forma algebrica utilizzando solo questi tre operatori. Osservando poi che:
)( 2121 xxxx ⋅=+
Si può concludere che anche AND e NOT sono un insieme funzionalmente completo. Le uniche porte logiche che costituiscono da sole un insieme funzionalmente completo sono le porte NAND e NOR
Fondamenti Informatica II - Lez. 01 22.03.2006 18
Schema Completo
Z= (¬X1* ¬X2* ¬ X3) +
+ (¬X1* ¬X2 * X3) +
+ ( X1* ¬X2 * X3) +
+ ( X1 * X2 * X3)
Fondamenti Informatica II - Lez. 01 22.03.2006 19
Prima Semplificazione
Z= ¬X1 * ¬X2 (¬ X3 + X3) +
+ X1 * X3 (¬X2 + X2)
Fondamenti Informatica II - Lez. 01 22.03.2006 20
Ultima semplificazione
Z= ¬X1* ¬X2 + X1 * X3
Fondamenti Informatica II - Lez. 01 22.03.2006 21
Schema completo Prima Semplificazione
Ultima semplificazione
Top Related