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