Algebra di Boole - University of CagliariA.A. 2013/2014 Elettronica M. Barbaro 3 Algebra di Boole...

Università di Cagliari Dipartimento di Ingegneria Elettrica ed Elettronica

Laboratorio di Elettronica (EOLAB)

Algebra di Boole

Modulo 2

A.A. 2013/2014 Elettronica M. Barbaro 2

Algebra di Boole

L’algebra di Boole o della commutazione è lo

strumento utilizzato per l’elaborazione

dell’informazione binaria.

Fu sviluppata nel 1854 da George Boole per

trattare problemi logici legati alla formulazione di

proposizioni

E’ stata poi applicata ai sistemi digitali binari

diventando lo strumento fondamentale per

l’analisi e la sintesi di blocchi logici


Algebra di Boole

Inizialmente l’algebra di Boole è stata concepita

per gestire delle proposizioni

Ciascuna proposizione può essere VERA o

FALSA

E’ possibile combinare diverse proposizioni

utilizzando gli operatori del linguaggio:

AND (e)

OR (oppure)

NOT (non)

La combinazione di più proposizioni può essere

a sua volta vera o falsa


Algebra di Boole: esempio

Ad esempio la frase: “Domani andrò al mare se farà bel tempo E NON

avrò da lavorare”

Può essere gestita con l’algebra di Boole: Y = “Domani andrò al mare”

A = “Farà bel tempo”

B = “Avrò da lavorare”

Allora posso scrivere Y = A AND (NOT B)

Il che vuole dire che Y è VERA (cioè domani andrò veramente al mare) se A è VERA (ossia farà bel tempo) e B non è VERA (cioè se non avrò da lavorare)


Algebra di Boole: esempio

La frase:

“Bisogna fare suonare la sirena se l’allarme è inserito E la

porta d’ingresso è aperta OPPURE una finestra è aperta”

Y = “Bisogna fare suonare la sirena”

A = “L’allarme è inserito”

B = “La porta è aperta”

C = “Una finestra è aperta”

Allora posso scrivere

Y = A AND (B OR C)

Il che vuole dire che Y è VERA (cioè devo fare suonare la

sirena) se A è VERA (ossia l’allarme è inserito) e B oppure C

sono VERE (cioè se la porta oppure la finestra sono aperte)


Algebra della commutazione

L’algebra della commutazione è definita su un

insieme di due elementi (0 e 1), che sono gli

elementi con cui abbiamo costruito la

rappresentazione delle informazioni e che

corrispondono al FALSO e VERO dell’algebra

inizialmente sviluppata da Boole

Gli operatori sono 3, gli stessi di Boole:

PRODOTTO LOGICO (AND, ·)

SOMMA LOGICA (OR, +)

NEGAZIONE (NOT, ‘)


Algebra della commutazione

L’algebra è definita attraverso un insieme di

assiomi che devono essere verificati una volta

definiti gli elementi (0 e 1) e gli operatori (AND,

OR e NOT)

Dagli assiomi è poi possibile ricavare molte altre

proprietà fondamentali dimostrando un insieme

di teoremi

A noi interessano solo i risultati di alcuni di

questi teoremi che sono fondamentali in fase di

progettazione di sistemi digitali


Operatori: AND

Gli operatori AND, OR e NOT sono definiti attraverso delle tabelle che definiscono quale è il risultato di una delle operazioni per qualunque possibile combinazione degli ingressi

L’operatore AND (·) è descritto dalla tabella seguente

La AND di due (o più) proposizioni è vera (ossia pari a 1) SOLO SE tutte e due le proposizioni sono VERE

X Y X · Y

0 0 0

0 1 0

1 0 0

1 1 1

Solo se X e Y sono entrambe

vere, allora X AND Y è vera

X = “C’è bel tempo” Y=“Sono in vacanza”

X · Y = “C’è bel tempo E sono in vacanza”


Operatori: OR

L’operatore OR (+) è definito dalla tabella seguente

Rappresenta l’operatore di inclusione (oppure) quindi la OR di due (o più proposizioni) è vera se almeno una delle proposizioni è VERA

Si può anche dire che la OR è FALSA solo se entrambe le proposizioni sono false

X Y X + Y

0 0 0

0 1 1

1 0 1

1 1 1

Se almeno una fra X e Y è

vera, allora X OR Y è vera

X = “La porta è aperta” Y=“La finestra è aperta”

X + Y = “La porta è aperta OPPURE la finestra è aperta”

Se sia X che Y sono false,

allora X OR Y è falsa


Operatori: NOT

L’operatore NOT è definito dalla seguente tabella.

Equivale alla NEGAZIONE del linguaggio corrente

E’ un operatore che agisce su una sola variabile (unario)

Il motivo della sua definizione è evidente: SE X è FALSO (0) ALLORA NOT X è VERO (1)

SE X è VERO (1) ALLORA NOT X è FALSO (0)

X X’

0 1

1 0

X è falso, allora NOT X è vero

X è vero, allora NOT X è falso

X = “C’è il sole”

X’ = “NON c’è il sole”


Assiomi

(a) (b)

1) L’algebra è CHIUSA rispetto all’operatore

+ ossia il risultato di una somma è ancora

un elemento dell’insieme {0,1}

L’algebra è CHIUSA rispetto all’operatore

· ossia il risultato di un prodotto è ancora

un elemento dell’insieme {0,1}

2) Esiste un elemento di identità (0) rispetto

alla somma tale per cui

x + 0 = x

Esiste un elemento di identità (1) rispetto

al prodotto tale per cui

x · 1 = x

3) La somma gode della proprietà

commutativa

x + y = y + x

Il prodotto gode della proprietà

commutativa

x · y = y · x

4) Il prodotto è distributivo rispetto alla

somma

x · (y + z) = x · y + x · z

La somma è distributiva rispetto al

prodotto

x + (y · z) = (x + y) · (x + z)

5) Per ogni x esiste almeno un elemento x’

(complemento) per cui

x + x’ = 1

Per ogni x esiste almeno un elemento x’

(complemento) per cui

x · x’ = 0

6) Esistono almeno due elementi diversi Esistono almeno due elementi diversi


Assiomi

Gli assiomi sono facilmente verificabili per come sono

stati definiti gli elementi {0,1} e gli operatori ( · , + , ’ )

1) Si verifica dalle tabelle che il risultato di una somma o un

prodotto è sempre 1 o 0

2) Si verifica dalle tabelle

3) E’ evidente dalla simmetria delle tabelle

4) Si può verificare generando qualsiasi combinazione di x, y e

z ed usando le tabelle per calcolare il risultato

5) Si verifica dalla tabella di definizione dell’operatore

complemento

Gli elementi sono 0 e 1 (sono almeno due e sono diversi)


Dualità

Dato che tutti gli assiomi hanno una duplice formulazione in cui operatori ed elementi di identità sono scambiati, vige il principio di dualità che dice che per ogni espressione algebrica ricavabile dagli assiomi è vera anche la formula duale che si ottiene scambiando gli operatori e gli elementi di identità

Questo, ovviamente, perché se si può dimostrare un’espressione usando una sequenza di assiomi, si può dimostrare l’espressione duale usando la forma duale dell’assioma


Teoremi

T1a) x + x = x Infatti x + x = (x + x)·1= (P2b)

= (x + x) · (x + x’) = (P5a)

= x + (x x’) = (P4b)

= x + 0 = (P5b)

= x (P2a)

T1b) x · x = x Infatti x · x = (x · x) + 0 = (P2a)

= (x · x) + (x · x’) = (P5b)

= x · (x + x’) = (P4a)

= x · 1 = (P5a)

= x (P2b)


Teoremi

T2a x + 1 = 1 T2b x · 0 = 0

T3 (x’)’ = x

T4a x + (y + z) = (x + y) + z Associatività

T4b x · (y · z) = (x · y) · z Associatività

T5a (x · y)’ = x’ + y’ (DeMorgan)

T5b (x + y)’ = x’ · y’ (DeMorgan)

T6a x + xy = x T6b x · (x+y) = x


Precedenza degli operatori

Per convenzione, l’operatore l’ordine di

precedenza degli operatori è:

NOT

AND

OR

Se si vuole alterare la precedenza si ricorre alle

parentesi


Funzioni logiche

Una funzione logica è una relazione algebrica

ingresso/uscita che lega un numero N di

ingressi con l’uscita.

F(x1,x2,…,xN)

x1

x2

xN

F


Rappresentazione di funzioni logiche

Una qualsiasi funzione logica può essere rappresentata in svariati modi. Tabella di verità: la tabella di verità ha tante righe

quante sono le possibili combinazioni degli ingressi e per ogni riga viene indicato il valore della funzione

Espressione logica: la funzione è rappresentata per mezzo di un’espressione algebrica contenente le variabili di ingresso e gli operatori logici di base

Mappe di Karnaugh: rappresentazione grafica basata sulla visualizzazione delle combinazioni di ingressi per cui la funzione vale 1 (o 0), utilizzata per la minimizzazione della funzione stessa

Schematico: rappresentazione grafica per mezzo di simboli


Principali funzioni logiche

Z=X’

Tabella di verità

Simbolo grafico

X Z

0 1

1 0

X Y Z

0 0 0

0 1 0

1 0 0

1 1 1

X Y Z

0 0 0

0 1 1

1 0 1

1 1 1

Z=X+Y Z=X•Y

Espressione

algebrica

OR AND

NOT


Principali funzioni logiche

X Y Z

0 0 1

0 1 1

1 0 1

1 1 0

X Y Z

0 0 1

0 1 0

1 0 0

1 1 0

Z=(X+Y)’ Z=(X•Y)’

NOR NAND

X Y Z

0 0 1

0 1 0

1 0 0

1 1 1

X Y Z

0 0 0

0 1 1

1 0 1

1 1 0

Z= X•Y’ + X’•Y Z=X’•Y’+X•Y

XOR XNOR


Somma canonica A B C D F

0 0 0 0 0

0 0 0 1 0

0 0 1 0 0

0 0 1 1 0

0 1 0 0 1

0 1 0 1 1

0 1 1 0 0

0 1 1 1 0

1 0 0 0 0

1 0 0 1 0

1 0 1 0 0

1 0 1 1 0

1 1 0 0 1

1 1 0 1 1

1 1 1 0 0

1 1 1 1 1

DCBA ,,,)15,13,12,5,4(

Un altro modo, molto compatto, per

rappresentare una funzione logica è

quello della sua forma canonica

(somma o prodotto)

Nel caso della somma si selezionano

solo le righe che contengono 1 e si

rappresentano con un numero che

corrisponde al numero di riga


Somma canonica

DCBA ,,,)15,13,12,5,4(

Avendo la somma canonica è possibile scrivere

facilmente l’espressione algebrica: si fa una somma

di termini ciascuno dei quali è il prodotto delle

variabili stesse prese però negate se il bit

corrispondente nel codice binario della riga è 0

(ABCD)

5d = 0101b

F=A’BC’D’+A’BC’D+ABC’D’+ABC’D+ABCD)

A e C

negate

B e D non

negate


Somma canonica

La ragione per cui si può implementare la funzione con una somma di prodotti, avendo la sua tabella di verità, sta nel fatto che la somma è pari a 1 quando almeno uno degli addendi è 1.

I prodotti sono generati in modo che siano pari a 1 quando la combinazione di ingresso è quella che corrisponde ad una riga per cui la funzione è 1

Perciò, appena la combinazione di ingresso è quella di una riga per cui la funzione deve valere 1 uno (ed uno solo) dei prodotti risulterà uguale e sarà quindi pari a 1 anche la funzione


Prodotto canonico A B C D F

0 0 0 0 0

0 0 0 1 0

0 0 1 0 0

0 0 1 1 0

0 1 0 0 1

0 1 0 1 1

0 1 1 0 0

0 1 1 1 0

1 0 0 0 0

1 0 0 1 0

1 0 1 0 0

1 0 1 1 0

1 1 0 0 1

1 1 0 1 1

1 1 1 0 0

1 1 1 1 1

Si selezionano le righe contenenti 0

Nel passare alla espressione algebrica

si usa la convenzione opposta (la

variabile è negata se c’è un 1 nel

codice della riga)

DCBA ,,,)14,11,10,9,8,7,6,3,2,1,0(

F=(A+B+C+D) (A+B+C+D’) (A+B+C’+D)

(A+B+C’+D’) (A+B’+C’+D) (A+B’+C’+D’)

(A’+B+C+D) (A’+B+C+D’) (A’+B+C’+D)

(A’+B+C’+D’) (A’+B’+C’+D)


Implementazione di funzioni logiche

E’ dimostrabile che qualsiasi funzione logica

può essere implementata con i soli operatori di

somma, prodotto e negazione e con solo 2 livelli

di logica. Ossia con somme di prodotti o prodotti

di somme.

Somma di prodotti Prodotto di somme

F’

C

D’

A

B’ F

C’

D

A’

B

2° livello 1° livello 2° livello 1° livello


Insieme funzionalmente completi

L’insieme AND, OR, NOT è dunque

funzionalmente completo perché avendo a

disposizione solo tali operatori è possibile

implementare ogni funzione logica

Anche il solo insieme AND, NOT è

funzionalmente completo, grazie al teorema di

DeMorgan che consente di trasformare una

somma in un prodotto

Per dualità è completo anche il solo insieme

OR, NOT


Insieme funzionalmente completi

Il solo operatore NAND (il simbolo della NAND è

) è un insieme funzionalmente completo, infatti:

Con una NAND si può implementare l’operatore

NOT:

A’ = (AA)’ = A NAND A

Con la NAND si può implementare il prodotto

AB = (AB)’’ = (A B)’ = (A B) (A B)

Con la NAND si può implementare la somma

A+B = (A+B)’’ = (A’B’)’ = (A A) (B B)

Analogamente si può mostrare che la sola NOR

è un insieme funzionalmente completo


Implementazione con operatori NAND

F

C’

D

A’

B

F

C’

D

A’

B F

C’

D

A’

B

Per il teorema di DeMorgan è

possibile trasformare la somma

di prodotti in modo da avere

solo operatori NAND

(X•Y)’=NAND(X,Y) (X’+Y’)=(X•Y)’=NAND(X,Y)


Implementazione con operatori NOR

F

C’

D

A’

B

F

C’

D

A’

B F

C’

D

A’

B

Analogamente è possibile

realizzare il prodotto di somme

con soli operatori NOR

(X+Y)’=NOR(X,Y) (X’ • Y’)=(X+Y)’=NOR(X,Y)


Mappe di Karnaugh

La rappresentazione per mezzo di mappe di

Karnaugh permette di trovare l’implementazione

in forma minima.

1 1

1 1

1

AB CD

01

10

11

00

00 01 11 10

F=F(A,B,C,D) Indici di colonne o righe adiacenti

differiscono di un solo bit

Si rappresenta un 1 nelle caselle

che corrispondono a combinazioni

di ingresso per cui F=1

L’ultima colonna (riga) è adiacente

alla prima.


Mappe di Karnaugh

CD

00 01 11 10 AB

1

0 4 12 8

1 5 13 9

3 7 15 11

2 6 14 10

00

01

11

10

1

1

1 1

Le singole celle, per

comodità, possono

essere etichettate con

il numero

corrispondente alla

combinazione ABCD

ossia ogni cella

corrisponde ad una

delle righe della

tabella di verità


Mappe di Karnaugh

Per minimizzare la funzione si coprono tutte le caselle contenenti gli 1 con gli implicanti più grandi possibili (ossia con riquadri contenenti un numero di caselle che sia una potenza di 2 e che contengono solo 1).

Dopodiché la forma su due livelli di logica della funzione è ottenuta come somma dei prodotti rappresentati dagli implicanti

1 1

1 1

1

CD

01

10

11

00

00 01 11 10 AB

F=BC’+ABD

Quando i nomi di variabile sono

costituiti da una sola lettera è

possibile omettere il simbolo del

prodotto (•)


Mappe di Karnaugh

1 1

1 1

1

CD

01

10

11

00

00 01 11 10 AB

Per ogni implicante si mettono

solo le variabili che non cambiano

all’interno dell’implicante stesso

Se dentro l’implicante la variabile è pari

a 1 si mette la variabile stessa,

altrimenti si mette la variabile negata

F=BC’+ABD

Un implicante con

2k caselle ha N-k

variabili


Mappe di Karnaugh

1 1

1 1

1

CD

01

10

11

00

00 01 11 10 AB

Vediamo perché questi quattro 1 sono

rappresentati dal prodotto BC’

A’BC’D’+ABC’D’+A’BC’D+ABC’D =

= (A’+A)BC’D’ + (A’+A)BC’D = BC’D’ + BC’D =

= (D+D’)BC’ = BC’

A’BC’D’ ABC’D’

A’BC’D ABC’D


Mappe di Karnaugh

Per ottenere la funzione in termini di prodotto di

somme bisogna modificare la rappresentazione:

Si mettono zeri nelle caselle corrispondenti a

combinazioni d’ingresso per cui la funzione è 0

Si coprono con implicanti contenti solo zeri

Nell’espressione algebrica dell’implicato si mette la

variabile stessa se essa compare col valore 0

altrimenti si mette la variabile negata se compare

col valore 1


Mappe di Karnaugh

0 0

0 0

0 0 0

0 0 0 0

AB CD

01

10

11

00

00 01 11 10

F=B (C’+D) (A+C’)

Nel caso della funzione precedente

F

C’

C’

D

A

B

Nella rappresentazione grafica

vengono di solito omessi gli

inverter (porte NOT)


Mappe di Karnaugh a 5 variabili

DE

00 01 11 10 BC

0 4 12 8

1 5 13 9

3 7 15 11

2 6 14 10

00

01

11

10

DE

00 01 11 10 BC

16 20 28 24

17 21 29 25

19 23 31 27

18 22 30 26

00

01

11

10

A=0 A=1

Le due mappe sono adiacenti se sovrapposte una

sull’altra, in quanto fra celle omologhe dell’una e dell’altra

cambia solo la variabile A

F=F(A,B,C,D,E)

Algebra di Boole - University of CagliariA.A. 2013/2014 Elettronica M. Barbaro 3 Algebra di Boole...

Documents

Transcript of Algebra di Boole - University of CagliariA.A. 2013/2014 Elettronica M. Barbaro 3 Algebra di Boole...