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

(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 ….

… proposizioni di tipo dichiarativo o descrittivo

… esprimono opinioni, giudizi, credenze, valutazioni, situazioni di fatto Le seguenti proposizioni/frasi:

• Ora è sereno

• Carlo abita a Benevento.

• Paola è iscritta all’università

• 4 è un numero primo.

• Il gatto è un mammifero

sono proposizioni semplici, ciascuna esprimente un solo fatto …

… il fatto espresso da ciascuna frase può essere VERO o FALSO

Ciascuna frase può assumere solo uno dei due valori di verità (VERO, FALSO)

(VERO, FALSO) sono i valori booleani che una frase (operando booleano / logico) può assumere

Algebra di Boole

Operatori ed Operazioni

… connettivi logici

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

operatori logici (quelli del tipo logico)

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/operando x, l’operatore di negazione not ne inverte il valore

Indicando con 0 il valore FALSO e con 1 il valore VERO:

Esempi di not

x: Ora è sereno

not x: Ora non è sereno

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/operandi x e y la frase composta 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

k: “il Benevento gioca in serie A” VERO

z: "Benevento è capitale d'Italia" FALSO w: "L’Italia ha vinto i mondiali di calcio 2018“ FALSO

j: “4 è un numero primo” FALSO

q: “il gatto è un mammifero” VERO

y or w:

"Il Napoli gioca in serie B oppure l’Italia ha vinto i mondiali di calcio 2018 "

FALSO j or q:

" 4 è un numero primo oppure il gatto è un mammifero "

VERO x or z:

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

VERO k or x:

(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/operandi 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: "il Napoli gioca in serie B" FALSO

k: “il Benevento gioca in serie A” VERO

z: "Benevento è capitale d'Italia" FALSO w: "L’Italia ha vinto i mondiali di calcio 2018“ FALSO

j: “4 è un numero primo” FALSO

q: “il gatto è un mammifero” VERO

y and w:

"Il Napoli gioca in serie B e l’Italia ha vinto i mondiali di calcio 2018 "

FALSO j and q:

" 4 è un numero primo e il gatto è un mammifero "

FALSO x and z:

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

FALSO k and x:

“il Benevento gioca in serie A e A Benevento c’è l’arco di Traiano "

VERO

(5)

Esempi di and

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

y: "Carlo abita a Benevento " FALSO

k: “Paola è iscritta all’università” VERO

x and y:

“Carlo abita a Benevento e Paola è iscritta all’università "

FALSO

Precedenza degli operatori logici

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

L’uso di parentesi può far alterare l’ordine di precedenza

(6)

Esempio

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

a = VERO b = FALSO c = FALSO

quanto vale l’espressione:

a or b and c ?

a or (b and c) = a or (FALSO)= VERO or (FALSO) = VERO

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

in funzione di tutti 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à

(7)

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à

Proprietà distributiva x and (y or z) = (x and y) or (x and z)

Es:

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 …

=

(8)

Proprietà distributiva

x and (y or z) = (x and y) or (x and z)

x y z (y or z) x and (y or z) x and y x and z (x and y) OR (x and z)

0 0 0 0 0 0 0 0

0 0 1 1 0 0 0 0

0 1 0 1 0 0 0 0

0 1 1 1 0 0 0 0

1 0 0 0 0 0 0 0

1 0 1 1 1 0 1 1

1 1 0 1 1 1 0 1

1 1 1 1 1 1 1 1

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

(9)

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

(10)

Esempio di 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

Esempio di 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

(11)

Esempio di 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

Esempio di 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

(12)

Porte logiche e tavole di verità

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 xy

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

(13)

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)

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

(14)

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

-

(15)

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)

(16)

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

D = 0

1 1 0

D = 0

1 0

0

0 0 1

D = 0

0 0

1

(17)

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

e 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 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

A B C

0

A B C

1

A B C

0

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

e 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 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

Y =

A B C

0

A B C

1

A B C

0

1 1

1 0

0

ABC

- -

ABC +

- - -

_{ABC +}

-

(18)

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 ….

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 => L1=0 L2=1

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

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

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

A B C L1 L2

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

(19)

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 => L1=1 L2=0

•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

(20)

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 ….

Esercizio

… circuito equivalente semplificato ….

B C A

L1 = AB + ABC

- -

L2 = ABC + BC

- - -

(21)

Progettare un circuito in cui due pulsanti alle due estremità di un corridoio comandano l’accensione e spegnimento di una lampada che illumina il corridoio Se la lampada è spenta la pressione di uno dei due interruttori la accende.

Se la lampada è accesa la pressione di uno dei due interruttori la spegne.

La lampada resta accesa o spenta se nessun interruttore è premuto o se vengono premuti entrambi contemporaneamente.

Esercizio

S1 S2 L_A L_B

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1

1 0 1 0 1 1 1 1

Progettare un circuito in cui due pulsanti alle due estremità di un corridoio comandano l’accensione e spegnimento di una lampada che illumina il corridoio

Se la lampada è spenta la pressione di uno dei due interruttori la accende.

Indichiamo con:

S1 e S2 i due interruttori: per ognuno di essi 0 indica ‘Non premuto’, 1 ‘Premuto’

L_Alo stato attuale della lampada

L_Blo stato della lampada dopo la pressione di uno o di entrambi gli interruttori.

Per la lampada 0 indica ‘Spenta’, 1 ‘Accesa’

Completare la tabella, definire l’espressione logica per LB e

Esercizio

(22)

S1 S2 L_A L_B

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 1

Progettare un circuito in cui due pulsanti alle due estremità di un corridoio comandano l’accensione e spegnimento di una lampada che illumina il corridoio

Se la lampada è spenta la pressione di uno dei due interruttori la accende.

Indichiamo con:

S1 e S2 i due interruttori: per ognuno di essi 0 indica ‘Non premuto’, 1 ‘Premuto’

L_Alo stato attuale della lampada

L_Blo stato della lampada dopo la pressione di uno o di entrambi gli interruttori.

Per la lampada 0 indica ‘Spenta’, 1 ‘Accesa’

L_B=(not S1 and not S2 and L_A) or (not S1 and S2 and not L_A) or (S1 and not S2 and not L_A) or (S1 and S2 and L_A)

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….

(23)

Esercizio

Valutare, tramite tabella di verità, le seguenti espressioni logiche e disegnarne i circuiti logici 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)