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 … è detta anche 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 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à

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

(" 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 "la carta di credito")

… per comprarla …

=

(7)

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

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

- -

(8)

Porte logiche and

or

not

Rappresentazione circuitale delle operazioni logiche

Porte logiche and

or

not

Rappresentazione circuitale delle operazioni logiche

(9)

and realizzato con interruttori

{aperto = 0, chiuso = 1}

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

Contatti 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

Contatti in serie

(10)

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

Contatti 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 Contatti in parallelo

x y x or y 0 0 0 1 0 1 0 1 1 1 1 1 or

y pila

x

(11)

Porte logiche

x y x and y 0 0 0 1 0 0 0 1 0 1 1 1 and

x y x or y 0 0 0 1 0 1 0 1 1 1 1 1 or

not

x not x 0 1 1 0

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 (c and d) (a or b)and (not c) 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 1 0 1

0 1 0 0 1 1 0 1 1

0 1 0 1 1 1 0 1 1

0 1 1 0 1 0 0 0 0

0 1 1 1 1 0 1 0 1

1 0 0 0 1 1 0 1 1

1 0 0 1 1 1 0 1 1

1 0 1 0 1 0 0 0 0

1 0 1 1 1 0 1 0 1

1 1 0 0 1 1 0 1 1

1 1 0 1 1 1 0 1 1

1 1 1 0 1 0 0 0 0

1 1 1 1 1 0 1 0 1

(13)

Semplificazione

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

- - -

Il vantaggio dell’algebra di Boole sta nel fatto che permette la semplificazione dei circuiti

Esempio

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

= xy + xz -

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

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

- - -

Le due funzioni sono equivalenti:

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

(14)

Esercizio

Scrivere un’espressione booleana che determina se:

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??

… imporre con j e k 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

Esercizio

Disegnare il circuito equivalente della seguente espressione logica:

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

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

B C A

D

B C

A

D

(16)

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 e disegnare il circuito F = (not a) and b

G = (not a) or b

(17)

Soluzione: F

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

0 0 1 0

0 1 1 1

1 0 0 0

1 1 0 0