1Piero Demichelis

Algebra di Boole

2Piero Demichelis

La Logica Booleana

• Nel XIX secolo un matematico inglese, George Boole, si occupò della possibilità di ricondurre il ragionamento al rigore delle costruzioni matematiche, sviluppando l'algebra che ancor oggi porta il suo nome.

• Gli studi di Boole rimasero semplici esercizi teorici finché, all'inizio del ‘900, apparvero i primi dispositivi elettrici di commutazione (relays) e si rese necessario un supporto teorico per trattare questo tipo di circuiti.

3Piero Demichelis

La Logica Booleana

• Boole poneva alla base del ragionamento le asserzioni : queste possono essere solo vere o false, assumendo quindi due soli stati (0 e 1).

• Anche un circuito di commutazione può assumere solo due stati: chiuso (OFF) oppure aperto (ON).

• Da qui dunque l'analogia, e la possibilità di correlare situazioni apparentemente così differenti.

4Piero Demichelis

Variabili Booleane

• L'algebra booleana opera su variabili x1, x2, …….., xn che possono assumere soltanto due valori: 0 e 1. Queste variabili prendono il nome di variabili logiche o booleane.

 • Con esse si possono rappresentare eventi

tipicamente binari: per esempio, un'affermazione può essere

vera (true = 1) oppure falsa (false = 0),

un interruttore può essere aperto (ON = 1) oppure chiuso (OFF = 0),

ecc.

5Piero Demichelis

Funzioni Booleane

• Sulle variabili booleane può essere definita una funzione, detta funzione booleana, o funzione logica,

F (x1, x2, …….., xn),

la quale, in corrispondenza di ogni n-pla xi, assume soltanto valori 0 e 1.

• Una particolare funzione booleana F è definita quando ad essa è assegnata la tavola della verità, tabella in cui è specificato il valore che assume F in corrispondenza di ogni combinazione delle variabili x1, x2, …….., xn.

6Piero Demichelis

Tavola della Verità: esempio

x1 x2 F(x1, x2)

F F F

F V F

V F V

V V F

7Piero Demichelis

Funzioni Booleane

• Il numero di combinazioni di n variabili è 2 n.

• Poiché per ogni combinazione delle n variabili una funzione può assumere 2 valori, 0 oppure 1, si

possono avere 22n funzioni diverse di n variabili.

• Ad esempio con 4 variabili si hanno 24 = 16 combinazioni e 216 = 65.536 possibili funzioni.

8Piero Demichelis

Esempio di Funzione Booleana

• In una stazione un treno parte se e solo se il semaforo è verde e il capotreno ha segnalato il via.

• Variabili logiche:T: vale 1 (vero) se il treno parte;S: vale 1 (vero) se il semaforo è verde;

C: vale 1 (vero) se il capotreno ha dato il via.

• Tavola di verità:

S C T

0 0 0

0 1 0

1 0 0

1 1 1

9Piero Demichelis

Operatori Booleani• Sulle variabili logiche agiscono gli operatori logici o

booleani.

• Operatori fondamentaliAND ( ) prodotto logico

OR ( ) somma logica

NOT () negazione logica (complementazione)

• Gli operatori di somma e prodotto logico godono della proprietà associativa e distributiva come gli analoghi dell'algebra numerica.

10Piero Demichelis

Operatori Booleani

Operatore AND Operatore OR

A A

F V

V F

A B A BF F F

F V V

V F V

V V V

A B A BF F F

F V F

V F F

V V V

Operatore NOT

11Piero Demichelis

Precedenza degli Operatori

• Gerarchia degli operatori:

NOT > AND > OR

• L’ordine può essere modificato tramite l’uso delle parentesi.

• Esempi:

f = A B C A B

f = A B ( C A B )

12Piero Demichelis

Espressioni Booleane

• Un insieme di variabili booleane, a cui siano applicati gli operatori logici AND, OR e NOT, prende il nome di espressione booleana o espressione logica T .

• Una espressione T corrisponde e può rappresentare quella funzione logica F che assume valore 1 in corrispondenza di quelle combinazioni di valori delle variabili per cui T = 1 e assume valore 0 in corrispondenza di quelle per cui T = 0.

13Piero Demichelis

Notazione

• Per motivi pratici, la notazione viene così semplificata:

– AND •– OR +– NOT oppure ’

• Esempio:

A ( B )– diventa:

A + B oppure A + B’

14Piero Demichelis

Operatori Booleani non elementari

NAND (NOT AND)

A B A B

F F V

F V V

V F V

V V F

NOR (NOT OR)

A B A + B

F F V

F V F

V F F

V V F

•

Falso se A e B sono veri Vero se A e B sono falsi

15Piero Demichelis

Operatori Booleani non elementari

EXOR (OR esclusivo) EXNOR (OR esclusivo negato)

Vero se A diverso da B Vero se A uguale a BAAB = A • B + A • B

AB = A • B + A • B

A B A B

F F F

F V V

V F V

V V F

A B A B

F F V

F V F

V F F

V V V

16Piero Demichelis

Espressione duale

• Una espressione Tb è detta duale di una espressione Ta se è ottenuta da quest'ultima sostituendo l'operatore AND con l'operatore OR, e viceversa, e la cifra 0 con la cifra 1, e viceversa.

• Esempio:

Ta = a • c + a • b + 0

Tb = Tad = (a + c) • (a + b) • 1

17Piero Demichelis

Teoremi

• I teoremi dell’algebra logica possono essere utilizzati

per dedurre espressioni che abbiano un minor numero di termini (semplificazione delle espressioni logiche).

• Al contrario dell'algebra ordinaria, dove non è possibile dimostrare i teoremi sostituendo alle variabili tutti i valori che possono assumere, nell'algebra booleana i teoremi sono dimostrabili per “induzione completa”, cioè verificandone la validità per tutte le combinazioni di valori (0 o 1) delle variabili.

• Per ogni teorema esiste il teorema duale, ottenuto applicando la regola di dualità. Si può dimostrare che, provata la validità di un teorema, risulta provata la validità anche del teorema duale.

18Piero Demichelis

Teoremi

1. Proprietà commutativaA B = B AA + B = B + A

2. Proprietà associativaA B C = (A B) C = A (B C)A + B + C = (A + B) + C = A + (B + C)

3. Proprietà distributivaA ( B + C ) = A B + A CA + ( B C ) = ( A + B ) ( A + C )

19Piero Demichelis

Teoremi

4. A F = F A V = A

5. A + F = A A + V = V6. A A = F A + A = V

7. A = A A A = A A A = A

8. A + A B = A9. A ( A + B ) = A10. A + A B = A + B11. A ( A + B ) = A B

20Piero Demichelis

Teorema di De Morgan

f ( a, b, ..., z; +, ) = f ( a, b, ..., z; , + )

Esempi:A + B = ( A B )

( A + B ) = A B

( A B ) = A B

21Piero Demichelis

Espressione canonica

• Un problema logico viene espresso mediante frasi che esprimono le condizioni che devono essere soddisfatte affinché si verifichi qualche evento.

• Avendo enucleato le variabili booleane indipendenti, è possibile descrivere lo stesso problema per mezzo della tavola della verità della variabile indipendente (funzione booleana).

• Resta da fare un ultimo passo, ovvero il passaggio dalla tavola di verità all’espressione logica che la rappresenta.

22Piero Demichelis

Espressione canonica

• Per ottenere l’espressione logica dalla tavola di verità si può applicare la seguente regola pratica:

1. l'espressione è formata da tanti termini, legati dall'operatore OR, quanti sono gli 1 della funzione;

2. in ogni termine compaiono tutte le variabili indipendenti, legate dall'operatore AND, nella forma affermata o negata a seconda che per quella combinazione nella tavola della verità assumano il valore 1 o 0.

• L'espressione che si trova con questo metodo è detta canonica, ed è una delle tante espressioni equivalenti che possono rappresentare la stessa funzione.

23Piero Demichelis

Espressione canonica: esempio

• Esempio: si supponga che l’analisi del problema abbia condotto alla seguente tavola di verità:

x y z F0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 0

1 1 1 1

a

b

c

d

24Piero Demichelis

Espressione canonica: esempio

• Applicando alla precedente tavola di verità le regole per l’estrazione dell’espressione canonica otteniamo la seguente espressione:

F = x y z + x y z + x y z + x y z

• Questa espressione può essere ridotta con l’uso dei teoremi dell’algebra di Boole.

a b c d

25Piero Demichelis

Minimizzazione dell’espressione

F = x y z + x y z + x y z + x y z

F = x z ( y + y ) + x z ( y + y )

F = x z + x z

F = z ( x + x )

F = z

=1 =1

=1

26Piero Demichelis

Applicazioni

• Il campo di applicazione dell’algebra di Boole è molto vasto, consentendo di risolvere problemi che, in origine, sono di natura molto diversa dalla logica.

• Ad esempio la somma di due numeri binari può essere ricondotta a una sequenza di somme elementari di 3 bit di ugual peso: x y c S Rip

0 0 0 0 0

0 1 0 1 0

1 0 0 1 0

1 1 0 0 1

0 0 1 1 0

0 1 1 0 1

1 0 1 0 1

1 1 1 1 1

27Piero Demichelis

Applicazioni

• Considerando x, y e c variabili logiche possiamo scrivere:

S = c • x • y + c • x • y + c • x • y + c • x • y =

= c • ( x • y + x • y ) + c • ( x • y + x • y ) =

= c • ( x y ) + c • ( x y ) =

= c x y

• Un analoga funzione può essere scritta per il riporto risolvendo così, con semplicità, il problema della somma binaria

28Piero Demichelis

Applicazioni

xn

• Realizzando le due funzioni (risultato e riporto) in un unico dispositivo elettronico otteniamo un circuito di addizione completa (full adder)

yn rn-1

sncarry

x0 y0 0

s0r0

x1 y1 r0

s1r1