Algebra di Boole

(1)

Elementi di Informatica

Prof. G. A. Di Lucca - Univ. del Sannio 1

Algebra di Boole

Il nome viene da George Boole, un matematico che definì delle strutture matematiche, dette appunto algebre di Boole … logica delle proposizioni ….

…. una frase può assumere solo uno dei due valori di verità:

… o è VERA o è FALSA

valori booleani (operandi) booleani (operandi)

solo due valori: vero (1) e falso (0)

Algebra di Boole

Operatori ed Operazioni

… connettivi logici

… permettono di formare frasi più complesse e valutarne la verità

operatori logici

not, ¬, (unario) - Negazione logica

and, ,  (almeno binario) – Prodotto logico

or, , + (almeno binario) – Somma logica

_

(2)

Negazione (not) - Tavola di verità

0 1

1 0

not x x

Data una generica frase x : l’operatore di negazione not ne inverte il valore

Esempi di not

x: "piove"

not x: "non piove"

Possibili notazioni:

not x oppure

¬x oppure

x _

(3)

Somma (OR) - Tavola di verità

x y x or y

0 0 0

0 1 1

1 0 1

1 1 1

Possibili notazioni: : x or y oppure x  y oppure x + y

Data due (o più) generiche frasi x e y la frase risultante dalla loro somma logica è vera se almeno una è vera

Esempi di or

x: “A Benevento c’è l’arco di Traiano" VERO y: "il Napoli gioca in serie B" FALSO z: "Benevento è capitale d'Italia" FALSO w: " L’Italia ha vinto la Coppa del Mondo 2014“ FALSO x or z:

"A Benevento c’è l’arco di Traiano oppure Benevento è capitale d'Italia "

VERO y or w:

"Il Napoli gioca in serie B oppure l’Italia ha vinto la Coppa del Mondo 2014 "

FALSO

(4)

Prodotto (AND) - Tavola di verità

x y x and y

0 0 0

0 1 0

1 0 0

1 1 1

Possibili notazioni: : x and y oppure x  y oppure x  y

Data due (o più) generiche frasi x e y , la frase risultante dal loro prodotto logico è vera se tutte sono vere

Esempi di and

x: "A Benevento c’è l’arco di Traiano " VERO y: "Napoli è la capitale dell’Italia" FALSO

x and y:

"A Benevento c’è l’arco di Traiano e Napoli è la capitale

dell’Italia " FALSO

x: “la terra è un pianeta" VERO y: “la luna è un satellite della terra" VERO

x and y:

“la terra è un pianeta e la luna è un satellite della terra"

VERO

(5)

Precedenza degli operatori logici

Operatore unario: not Operatore binario: and Operatore binario: or

Esempio

Supponiamo di avere tre informazioni: a, b, c Sia:

a VERA b FALSA c FALSA

quanto vale l’espressione:

a or b and c ?

a or (b and c) = a or (FALSA) = VERA or (FALSA) = VERA

(6)

Esempio: si vuole valutare l’espressione a or b and c

in funzione dei possibili vari valori assunti da a, b, c

1 1

1

1 0

0 1

1

1 0

1

0 0

0

0 0

1 0

0

0 0

0 1

0

1 1

0

1 0

0 0

1

a or (b and c) b and c

c b

a

Tabella di verità

Esempio: si vuole valutare l’espressione (a or b) and c

in funzione dei possibili vari valori assunti da a, b, c

1 1

1

0 1

1

1 1

1 0

1

0 0

0

0 0

1 0

0

0 1

0

1 1

0

0 1

0 0

1

(a or b)and c a or b

c b

a

Tabella di verità

(7)

Valgono le proprietà distributive x and (y or z) = (x and y) or (x and z)

x = “quella penna mi piace“ y = "ho i soldi“ z = “ho la carta di credito"

(" quella penna mi piace" e "ho i soldi") oppure

(" quella penna mi piace" e "ho la carta di credito")

… per comprarla …

“quella penna mi piace" e ( "ho i soldi" oppure “ho la carta di credito")

… per comprarla …

=

Teoremi fondamentali

Identità: 1x=x 0+x=x

Nullo: 0x=0 1+x=1

Idempotenza: xx=x x+x=x

Inverso: (not x)x=0 (not x)+x=1

Commutativa: xy=yx x+y=y+x

Associativa: (xy)z=x(yz) (x+y)+z=x+(y+z) Distributiva: x(y+z)=xy+xz x+(yz)=(x+y)(x+z)

 = and + = or = not

-

Principio di dualità:

derivabili l’una dall’altra scambiando:

+ con  0 con 1

(8)

Teorema di De Morgan (x  y) = x + y

(x + y) = x  y - -

- -

Esempio:

non ((ho i soldi) o (ho la carta di credito))

=

(non ho i soldi) e (non ho la carta di credito)

1 1

0 0

1 0

0 0

0 1

0 0

1 1

x  y (x+y)

y

x

- -

Porte logiche and

or

not

Rappresentazione circuitale delle operazioni logiche

(9)

OR realizzato con interruttori

{aperto = 0, chiuso = 1}

x y x or y aperto aperto aperto chiuso aperto chiuso aperto chiuso chiuso chiuso chiuso chiuso x y x or y

0 0 0

1 0 1

0 1 1

1 1 1

Interruttori in parallelo

or

y pila

x

OR realizzato con interruttori

x y x or y aperto aperto aperto chiuso aperto chiuso aperto chiuso chiuso chiuso chiuso chiuso x y x or y

0 0 0

1 0 1

0 1 1

1 1 1

or

y pila

x Interruttori in parallelo

(10)

and realizzato con interruttori

x y x and y aperto aperto aperto chiuso aperto aperto aperto chiuso aperto chiuso chiuso chiuso x y x and y

0 0 0

1 0 0

0 1 0

1 1 1

and

Interruttori in serie

x y pila

and realizzato con interruttori

x y x and y aperto aperto aperto chiuso aperto aperto aperto chiuso aperto chiuso chiuso chiuso x y x and y

0 0 0

1 0 0

0 1 0

1 1 1

and

x y pila

Interruttori in serie

(11)

Porte logiche

not

x not x 0 1 1 0 x

x y x or y

0 0 0

1 0 1

0 1 1

1 1 1

or x y

x y x and y

0 0 0

1 0 0

0 1 0

1 1 1

and x y

Esempio

y = ((a or b) and (not c)) or (c and d) circuito

d b

a

y

c

(12)

d b

c a

y

1 0

0

0 1

1 1

0

1

Quale è il valore di y se:

a = 1 b = 0 c = 0 d = 0

y = ((a or b) and (not c)) or (c and d)

a b c d (a or b) not c (a or b)and (not c) (c and d) y

0 0 0 0 0 1 0 0 0

0 0 0 1 0 1 0 0 0

0 0 1 0 0 0 0 0 0

0 0 1 1 0 0 0 1 1

0 1 0 0 1 1 1 0 1

0 1 0 1 1 1 1 0 1

0 1 1 0 1 0 0 0 0

0 1 1 1 1 0 0 1 1

1 0 0 0 1 1 1 0 1

1 0 0 1 1 1 1 0 1

1 0 1 0 1 0 0 0 0

1 0 1 1 1 0 0 1 1

1 1 0 0 1 1 1 0 1

1 1 0 1 1 1 1 0 1

1 1 1 0 1 0 0 0 0

1 1 1 1 1 0 0 1 1

(13)

Semplificazione delle espressioni

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

- - -

L’applicazione di teoremi e proprietà dell’algebra di Boole permette la semplificazione delle espressioni, ovvero dei circuiti che le

realizzano Esempio

= xy(z+z) + xz = - - (inverso)

= xy + xz -

= xy1 + xz = - (identità)

Le due funzioni sono equivalenti:

hanno la stessa tabella di verità ma la seconda funzione è realizzabile con un circuito più semplice

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

- - -

F = xy + xz

-

(14)

Esercizio

Specificare usando espressioni booleane che:

il valore di una variabile i è nell’intervallo da 1 a 100, estremi inclusi

1. (i>=1) 2. (i<=100)

(i>=1) and (i<=100)

Esercizio

Scrivere un’espressione booleana che determina se:

il valore di una delle due variabili intere j e k è un multiplo dell’altro

(j % k = 0) (k % j = 0)

(j % k = 0) or (k % j = 0) Corretto??

… opportuno imporre che j e k siano diversi da 0

(j ≠ 0) and (k ≠ 0)

(15)

Esercizio

Disegnare il circuito equivalente della seguente espressione logica:

C = (A OR B) OR NOT (A AND B) C = [(A OR B)] OR [NOT (A AND B)]

A B

C

Quanto vale C se A=0 e B=1 ?

C = (0 OR 1) OR NOT (0 AND 1) C = 1 OR NOT (0) = 1

Quanto vale D se A=1, B=0 e C = 0 ?

Esercizio

Disegnare il circuito equivalente della seguente espressione logica:

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

Quanto vale D se A=0, B=1 e C = 1 ?

B C A

D

1 1

0

D 1

0 0

1

D 0

1 0

D = 0

(16)

Esercizio

Progettare un dispositivo con tre pulsanti ed una uscita che deve essere Vera ( cioè 1) quando un solo pulsante è premuto

Ciascun Pulsante può assumere un valore in (Alzato, Premuto) Indicando: Alzato = 0 Premuto = 1

ciascuno dei tre pulsanti con A, B, C e l’uscita con Y possiamo costruire una tabella di verità riportante le condizioni per cui deve essere Y=1

A B C Y

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 0

Y = ABC + ABC + ABC

- - - - - -

A B C 0

A B C 1 A B C

0

B C A

Y

Y = ABC + ABC + ABC

- - - - - - Esercizio

A B C Y

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 0 … Disegnare il corrispondente circuito logico ….

(17)

Esercizio

Progettare un dispositivo in cui tre deviatori (A, B, C) comandano due lampade (L1 e L2) secondo le seguenti regole:

•A=B=C=0 => L1=L2=1 (accese)

•A=0, B=C=1 => L2=1 L1=0

•A=B=C=1 => L1=L2=1

•A=B=0 C=1 => L2=0 L1=1

•in tutti gli altri casi => L1=L2=0

A B C L1 L2 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1

L1 = ABC + ABC + ABC

- - - - -

L2 = ABC + ABC + ABC

- - - -

Esercizio

L1 = ABC + ABC + ABC

- - - - -

L2 = ABC + ABC + ABC

- - - -

… Disegnare il corrispondente circuito logico ….

B C A

L1

L2

(18)

L1 = ABC + ABC + ABC

- - - - -

L2 = ABC + ABC + ABC

- - - - Esercizio

L1 = AB(C + C) + ABC = AB + ABC

- - - - -

L2 = ABC + (A + A)BC = ABC + BC

- - - - - - -

… semplificando ….

… Disegnare il corrispondente circuito logico semplificato ….

B C A

L1 = AB + ABC

- -

L2 = ABC + BC

- - - Esercizio

… circuito equivalente semplificato ….

(19)

Esercizio

Costruire le tabelle delle verità, ed i circuiti logici equivalenti, delle seguenti espressioni logiche:

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

A B C D

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

… lo studente svolga l’esercizio….

Esercizio

Valutare, tramite tabella di verità, le seguenti espressioni logiche e disegnarne i circuiti relativi:

F = not a and c or ((b or c) and (a and c))

G =(not (a and b or c)) and (b and not c and a)