Algebra di Boole

1

2

Algebra di Boole• Insieme di regole algebriche della logica binaria che stanno

alla base del funzionamento dei calcolatori• È costituita da:

– un insieme di variabili booleane A,B,C,... che possono assumere solo i valori 1 (vero) o 0 (falso).

– un insieme di funzioni (operazioni) che operano sulle variabili di input e danno delle variabili di output

– un insieme di leggi (assiomi) che definiscono le proprietà delle funzioni.

3

Elementi dell’algebra di Boole

• Gli elementi dell'insieme B di un'algebra di Boole possono essere astratti o concreti; ad esempio possono essere numeri, proposizioni, insiemi o reti elettriche.

4

Variabili Logiche

• Una Variabile Logica è una variabile che può assumere solo due valori:

• True (vero, identificato con 1) • False (falso, identificato con 0)

5

Funzioni

• Usando le variabili booleane, si possono costruire le funzioni booleane F(x,y,z)che possono assumere solo due stati:– true– false

6

Tabella di verità

• Ogni funzione booleana è caratterizzata dalla propria tabella di verità che riporta il suo valore per ogni possibile configurazione delle variabili in essa contenute.

x y z F0 0 0 10 0 1 00 1 0 10 1 1 11 0 0 01 0 1 11 1 0 01 1 1 0

7

Tabella di verità

• La Tabella di Verità di un’espressione logica identifica la cosiddetta funzione booleana.

8

Costanti booleane

• Oltre alle variabili vi sono anche le costanti• Essendo l’Algebra Booleana definita su due

soli simboli, esistono solo due costanti:– 0– 1

9

Connettivi logici

• Le operazioni booleane fondamentali, rappresentate dai Connettivi Logici sono:– Congiunzione (AND )– Disgiunzione (OR )– Negazione (NOT )

10

Funzioni BooleaneCombinando variabili logiche mediante i connettivi logicisi ottengono le espressioni logiche.

• Un’espressione logica può essere definita in manieraesaustiva tramite la sua Tabella di Verità, che riporta ilsuo valore per ogni possibile configurazione delle variabili in essa contenute (Vedi la sezione Algoritmi).

• La Tabella di Verità di un’espressione logica identifica la cosiddetta funzione booleana

11

L’operatore NOT

• Il risultato è il complemento (la negazione) dell’unica variabile

x NOT x 0 1 1 0

12

L’operatore AND

• Il risultato è vero solo se sono vere entrambe le variabili

a b a AND b0 0 00 1 01 0 01 1 1

13

L’operatore OR

• Il risultato è vero solo se è vera almeno una delle variabili

a b a OR b0 0 00 1 11 0 11 1 1

14

L’operatore XOR

• Il risultato è vero solo se è vera solo una delle due variabili

a b a XOR b0 0 00 1 11 0 11 1 0

15

Priorità degli operatori

16

Proprietà delle funzioni logiche• p. commutativa

– A AND B = B AND A A OR B = B OR A• p. associativa

– (A AND B) AND C = A AND (B AND C) (A OR B) OR C = A OR (B OR C)

• p. distributiva– A AND (B OR C) = (A AND B) OR (A AND C) A OR (B AND C) = (A OR B)

AND (A OR C) • leggi di idempotenza e complementazione

– 0 OR A=A 0 AND A=0 1 OR A=1 1 AND A=A A OR A=A A AND A=A NOT ( NOT A)=A A OR NOT A = 1 A AND NOT A = 0

17

Leggi di De Morgan

– A AND B = NOT (( NOT A) OR ( NOT B))

– A OR B = NOT (( NOT A) AND ( NOT B))

– NOT(A AND B) = NOT A OR NOT B

– NOT(A OR B) = NOT A AND NOT B

Cioè

18

Tavole di verità ed espressioni

E’ possibile :

– data la tavola di verità ricavare l’espressione corrispondente

– data una espressione booleana trovare la tavola di verità corrispondente.

19

Equivalenza tra espressioni

• Due espressioni sono uguali (o logicamente equivalenti) se il loro valore di verità è identico per ogni assegnazione delle variabili.

• L’equivalenza può essere verificata mediante le tabelle di verità..

20

Esempio

21

Esercizi propostiESERCIZIO 2Costruire le tavole di verità delle seguenti

espressioni logiche:

1. NOT (A OR B)2. A AND NOT(B)3. A AND B OR C4. A AND (B OR C)5. NOT(A) AND B OR NOT(C)6. A AND (NOT(B) OR C)

ESERCIZIO 1Se a=5, b=7 e c=0Determinare se le seguenti espressioni sono vere o false (V=1, F=0):

1. (a>0) and (b>0)2. (3<a) and (b<2)3. (a<=2) and (b<3)4. (a<=2) or (b<3)5. not(a>0) and (b>1)6. not(a>0) or (b>1)7. (a>1) and not(b>0)8. not ((a>0) or (b<2))9. (a<>5) and (c>0)10. (a<>5) or (c>0)11. (a<>5) and (c=0)12. (a=5) or (c=0)13. (a<3) and (b>0) or (c>=0)14. (a<3) and ((b>0) or (c>=0))15. not(a<3) and (b>0) or not(c>=0)16. (a<3) and not(b>0) or (c>=0)

22

Esercizi proposti

Disegnare la tavola di verità della seguente espressione logica

NOT(A) AND (B OR NOT(C))

Dimostrare la 1° legge di De MorganNOT(A AND B) = NOT A OR NOT B