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
_
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 3
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 _
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 5
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:
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 7
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
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 9
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
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 11
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
1
1 0
0 1
1
1 0
1 0
1
0 0
0 0
0
0 0
1 0
0
0 0
0 1
0
1 1
1 1
0
1 0
0 0
1
a or (b and c) b and c
c b
a
Tabella di verità
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 13
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
1
0 1
0 1
1
1 1
1 0
1
0 0
0 0
0
0 0
1 0
0
0 1
0 1
0
1 1
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 …
=
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 15
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à: 1x=x 0+x=x
Nullo: 0x=0 1+x=1
Idempotenza: xx=x x+x=x
Inverso: (not x)x=0 (not x)+x=1
Commutativa: xy=yx x+y=y+x
Associativa: (xy)z=x(yz) (x+y)+z=x+(y+z) Distributiva: x(y+z)=xy+xz x+(yz)=(x+y)(x+z)
= and + = or
= not
-
Principio di dualità:
derivabili l’una dall’altra scambiando:
+ con 0 con 1
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 17
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
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
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 19
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
{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
or
y pila
x Interruttori in parallelo
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 21
Esempio di 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
Interruttori in serie
x y pila
Esempio di 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
x y pila
Interruttori in serie
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 23
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
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 25
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
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 27
Semplificazione delle espressioni
F = xyz + xyz + xz = - - - (distributiva)
L’applicazione di teoremi e proprietà dell’algebra di Boole permette la semplificazione delle espressioni, ovvero dei circuiti che le
realizzano Esempio
= xy(z+z) + xz = - - (inverso)
= xy + xz -
= xy1 + xz = - (identità)
Le due funzioni sono equivalenti:
hanno la stessa tabella di verità ma la seconda funzione è realizzabile con un circuito più semplice
F = xyz + xyz + xz
- - -
F = xy + xz
-
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 29
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)
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 31
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
D = 0
1 1 0
D = 0
1 0
0
0 0 1
D = 0
0 0
1
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 33
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
0
ABC
- -
ABC +
- - -
ABC +-
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 35
B C A
Y
Y = ABC + ABC + ABC
- - - - - - 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