DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Algebra di Boole
ed elementi di logica
Marco D. Santambrogio – [email protected]
Ver. aggiornata al 13 Marzo 2013
Oggi…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
2
What goes around comes around
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
SAI, SONO STANCO DEL CALCIO CHE GIOCHIAMO IN ITALIA:
ANCHE IO, CATENACCIO,
PER QUELLO IERI
SERA
DIFENSIVISTA,
POCA
CORSA
MI E’ PIACIUTO COSI’ TANTO IL MILAN
3
Info di servizio
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Feedback sulle lezioni
 Se date una valutazione ≤ 3 sul quanto la
spiegazione sia risultata chiara, vi chiederei
cortesemente di spiegare nelle note a cosa e’
dovuto questo dato
• Magari più precisione negli orari, venerdì
ho perso parte della lezione perchè ha
incominciato mezz'ora prima dell'ora
scritta nel calentario accademico
4
WAT?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Non basta dire di cercarsi la sintassi su
internet o su un libro; rimane comunque
il fatto che non si riesce a "strutturare"
l'esercizio
• Laboratori: divisione in gruppi
 38 gruppi il lunedi’ (99 studenti)
 25 gruppo il giovedi’ (71 studenti)
5
Torniamo a Venerdì 8 Marzo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
6
Struttura di un programma C
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
parte dichiarativa globale
inclusione librerie / per poter invocare funzioni utili (i/o, ...) /
dichiarazione di variabili globali e funzioni
int main ( ) {
parte dichiarativa locale
dichiarazione di variabili locali
istruzione 1;
istruzione 2;
istruzione 3;
istruzione 4;
...
istruzione N;
/ tutti i tipi di operazioni, e cioè: /
/ istr. di assegnamento /
/ istr. di input / output /
/ istr. di controllo (condizionali, cicli) /
parte esecutiva
}
Ogni programma C deve contenere un modulo int main() {...}
7
Struttura di un programma C
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Parte dichiarativa: contiene le dichiarazioni degli
elementi del programma
 Dati, ed eventualmente funzioni (ma solo nella parte globale)
• Parte esecutiva: contiene le istruzioni da eseguire,
che ricadono nelle categorie:
 Istruzioni di assegnamento ()
 Strutture di controllo:
• Condizionali (if-then-else e switch)
• Iterative, o cicli (while, do e for)
 Istruzioni di Input/Output (printf, scanf, ...)
8
Variabili e indirizzi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
3
int var;
&var
2
var
1
0
• Supponiamo che la dichiarazione riservi la zona di
memoria all’indirizzo 1
• var indica il contenuto della cella di memoria
• &var indica l’indirizzo della cella di memoria
9
Massimo Comune Divisore
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Definizione
 Dicesi Massimo Comune Divisore (M.C.D.)
il piu’ grande tra i divisori comuni a due o
piu’ numeri
• Esempi
 Dati A=12, B=15
• Divisori comuni: 1, 3 - MCD=3
 Dati A=10, B=30 e C=20
• Divisori comuni: 1, 2, 5, 10 - MCD=10
10
MCD: pseudocodice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1.
2.
3.
4.
Leggi A e B
min= il minimo tra A e B
trovato = 0; MCD = min;
Finche’ trovato != 1
1. Se MCD divide A e B
1. Allora trovato = 1
2. Altrimenti MCD = MCD - 1
5. Stampa MCD
11
MCD: diagramma di flusso
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Inizio
Leggi A e B
min=minimo{A,B}
trovato = 0
MCD=min
Stampa MCD
no
trovato!=1?
si
no
Fine
MCD divide
AeB
MCD=MCD -1
si
trovato = 1
12
Obiettivi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Algebra di Boole
 Algebra di boole a due valori: algebra di
commutazione
 Operazioni logiche
 Espressioni logiche
 Assiomi e proprietà dell’algebra di
commutazione
13
Cenni all’algebra di Boole
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• L’algebra di Boole (inventata da G. Boole,
britannico, seconda metà ’800), o algebra della
logica, si basa su operazioni logiche
• Le operazioni logiche sono applicabili a operandi
logici, cioè a operandi in grado di assumere solo i
valori vero e falso
• Si può rappresentare vero con il bit 1 e falso con
il bit 0 (convenzione di logica positiva)
14
Algebra Booleana: definizione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Algebra Booleana B è un sistema algebrico
identificato dalla sestupla
(B,+,*,’,0,1) dove:
 B è l'insieme su cui vengono definite le operazioni
(supporto)
 +,*,’ sono le operazioni binarie OR e AND e
l’operazione unaria NOT
 0,1 sono elementi speciali di B.
• 0 è l’elemento neutro rispetto a +
• 1 è l’elemento neutro rispetto a *
 Assiomi
- 15 -
Algebra Booleana a due valori:
Algebra di Commutazione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
“Tra tutte le algebre booleane, l'algebra booleana a due
valori........è la più utile. Essa è la base matematica della
analisi e progetto di circuiti di commutazione che
realizzano i sistemi digitali.”
[Lee, S.C., Digital Circuit And Logic Design. Englewood Cliffs, NJ:
Prentice-Hall, 1976]
- 16 -
Operazioni logiche fondamentali
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Operatori logici binari (con 2 operandi logici)
 Operatore OR, o somma logica
 Operatore AND, o prodotto logico
• Operatore logico unario (con 1 operando)
 Operatore NOT, o negazione, o inversione
• Poiché gli operandi logici ammettono due soli
valori, si può definire compiutamente ogni
operatore logico tramite una tabella di
associazione operandi-risultato
17
Operazioni logiche fondamentali
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Le variabili dell’algebra booleana a due valori possono assumere solo i due
valori 0 e 1
 precisamente, se x indica una variabile, è
• x = 0 se e solo se x  1
• x = 1 se e solo se x  0
• Algebra Booleana a due valori: ({0,1},+,*,’,0,1) dove + (OR) e *
(AND) sono definiti come
+ 0 1
0 0 1
1 1 1
* 0 1
0 0 0
1 0 1
• Mentre l’operazione a un solo elemento (unary operation) detta
complementazione o negazione (NOT) è definita come
‘
0 1
1 0
 Nota: il simbolo associato al NOT è spesso indicato come ’(esempio x’),
!(esempio !x) o sopra segnando la variabile.
Operatori logici di base e loro tabelle di verità
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
A B
A or B
0 0
0
0 1
1
1 0
1
1 1
1
(somma logica)
A B
A and B
0 0
0
0 1
0
1 0
0
1 1
1
(prodotto logico)
A
not A
0
1
1
0
(negazione)
Le tabelle elencano tutte le possibili combinazioni in ingresso
e il risultato associato a ciascuna combinazione
19
Pausa 5’
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
George Boole
20
Espressioni logiche (o Booleane)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Come le espressioni algebriche, costruite con:
 Variabili logiche (letterali): p. es. A, B, C  0 oppure 1
 Operatori logici: and, or, not
• Esempi:
A or (B and C)
(A and (not B)) or (B and C)
• Precedenza: l’operatore “not” precede l’operatore “and”,
che a sua volta precede l’operatore “or”
A and not B or B and C  (A and (not B)) or (B and C)
• Per ricordarlo, si pensi OR come “” (più), AND come “”
(per) e NOT come “” (cambia segno)
21
Tabella di verità di un’espressione logica
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
A and B or not C
ABC
X = A and B
Y = not C
X or Y
000
0 and 0 = 0
not 0 = 1
0
or
1
=1
001
0 and 0 = 0
not 1 = 0
0
or
0
=0
010
0 and 1 = 0
not 0 = 1
0
or
1
=1
011
0 and 1 = 0
not 1 = 0
0
or
0
=0
100
1 and 0 = 0
not 0 = 1
0
or
1
=1
101
1 and 0 = 0
not 1 = 0
0
or
0
=0
110
1 and 1 = 1
not 0 = 1
1
or
1
=1
111
1 and 1 = 1
not 1 = 0
1
or
0
=1
Due esercizi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
A
0
0
1
1
B
0
1
0
1
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
NOT ((A OR B) AND (NOT A))
1
0
1
1
C
0
1
0
1
0
1
0
1
0
0
1
1
0
1
1
1
0
1
0
1
0
1
0
0
1
1
0
0
0
0
1
1
( B OR NOT C) AND (A OR
0 1
1 0
1
0
0 0
0 1
0
0
1 1
1 0
1
0
1 1
0 1
0
0
0 1
1 0
1
1
0 0
0 1
0
1
1 1
1 0
1
1
1 1
0 1
1
1
NOT C)
1
1
0
0
1
1
0
0
1
1
1
0
1
1
1
0
0
1
0
1
0
1
0
1
23
Vero e falso in C
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• In C non esiste un tipo di dato specifico per
rappresentare i concetti vero e falso
• Una condizione assume un valore intero pari a
 0 se la condizione è falsa
 1 se la condizione è vera
• In generale, ogni valore diverso da zero è
considerato vero
 ( 3 ) VERO
 ( 1 ) VERO
 ( a – a ) FALSO
24
Problema
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Si scriva un programma in C che, dato un
numero, dica se questo è positivo o
negativo
25
Soluzione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1. Si inserisca N
2. N è maggiore di 0?
 Vero: N è positivo
 Falso: N non è positivo
26
In C: positivo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
int main()
{
int n;
printf (“Inserisci un numero\n");
scanf ("%d", &n );
if ( n > 0 )
printf ("Un numero positivo ! \n");
else
condizione
printf ("Un numero negativo o nullo\n");
printf ("Fine del programma\n");
return 0;
}
27
Problema: caratteri MaIuScOli
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Si scriva un programma che, preso un
carattere minuscolo da tastiera, ne riporta a
video l’equivalente maiuscolo
28
Maiuscolo: esecuzione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
29
HELP: errori sull’input
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
30
Problema: errori sull’input
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Problema
 Preso un dato inserito da tastiera
 Per potervi applicare la trasformazione di
nostro interesse
 Dobbiamo prima verificare che il dato sia
coerente con quanto ci aspettiamo
• Soluzione
 Definire l’insieme dei caratteri validi
 Verificare l’appartenenza del carattere
inserito, all’insieme dei caratterei validi
31
Pseudocodice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dati
 L’insieme dei caratteri ammissibili
{a, b, c, …, z}
1.
2.
3.
4.
Richiedere l’inserimento di un carattere
Se carattere inserito corretto
Allora stampa a video carattere-32
Altrimenti stampa a video un messaggio
di errore
32
Condizione da verificare
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dati
 L’insieme dei caratteri ammissibili
{a, b, c, …, z}
• Il carattere inserito deve essere
 =>a
 <= z
33
Maiuscolo: solo if
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
34
Pausa 10’
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
35
Condizione da verificare
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Il carattere inserito deve essere
 X: =>a
 Y: <= z
• X e Y devono essere entrambe vere
X Y X and Y
0 0
0
0 1
0
1 0
0
1 1
1
(prodotto logico)
36
Maiuscolo: AND
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
37
Maiuscolo: codice ottimizzato
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
38
Maiuscolo: esecuzione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
39
A che cosa servono le espressioni logiche?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• A modellare alcune (non tutte) forme di ragionamento
 A  è vero che 1 è maggiore di 2 ? (sì o no, qui è no)  0
 B  è vero che 2 più 2 fa 4 ? (sì o no, qui è sì)  1
 A and B  è vero che 1 sia maggiore di 2 e che 2 più 2 faccia 4 ?
Si ha che A and B  0 and 1  0, dunque no
 A or B  è vero che 1 sia maggiore di 2 o che 2 più 2 faccia 4 ?
Si ha che A or B  0 and 1  1, dunque sì
• OR, AND e NOT vengono anche chiamati connettivi logici,
perché funzionano come le congiunzioni coordinanti “o” ed “e”,
e come la negazione “non”, del linguaggio naturale
• Si modellano ragionamenti (o deduzioni) basati solo sull’uso di
“o”, “e” e “non” (non è molto, ma è utile)
40
Che cosa non si può modellare tramite
espressioni logiche?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Le espressioni logiche (booleane) non modellano:
 Domande esistenziali: “c’è almeno un numero reale x tale che
il suo quadrato valga 1 ?” (si sa bene che non c’è)
x | x2  1
è falso
 Domande universali: “ogni numero naturale è la somma di
quattro quadrati di numeri naturali ?” (si è dimostrato di sì)
x | x  a2b2c2d2
è vero (“teorema dei 4 quadrati”)
Più esattamente andrebbe scritto: x a,b,c,d | x  a2b2c2d2
•  e  sono chiamati “operatori di quantificazione”, e sono
ben diversi da or, and e not
• La parte della logica che tratta solo degli operatori or, and
e not si chiama calcolo proposizionale
• Aggiungendo gli operatori di quantificazione, si ha il
calcolo dei predicati (che è molto più complesso)
41
Tautologie e Contraddizioni
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Tautologia
 Una espressione logica che è sempre vera, per
qualunque combinazione di valori delle variabili
• Esempio: principio del “terzo escluso”: A or not A (tertium
non datur, non si dà un terzo caso tra l’evento A e la sua
negazione)
• Contraddizione
 Una espressione logica che è sempre falsa, per
qualunque combinazione di valori delle variabili
• Esempio: principio di “non contraddizione”: A and not A
(l’evento A e la sua negazione non possono essere
entrambi veri)
42
Equivalenza tra espressioni
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Due espressioni logiche si dicono equivalenti (e si
indica con ) se hanno la medesima tabella di
verità. La verifica è algoritmica. Per esempio:
AB
not A and not B  not (A or B)
00
1 and 1 = 1
not 0 = 1
01
1 and 0 = 0
not 1 = 0
10
0 and 1 = 0
not 1 = 0
11
0 and 0 = 0
not 1 = 0
• Espressioni logiche equivalenti modellano gli stessi
stati di verità a fronte delle medesime variabili
43
Proprietà dell’algebra di Boole
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• L’algebra di Boole gode di svariate proprietà,
formulabili sotto specie di identità
 cioè formulabili come equivalenze tra espressioni
logiche, valide per qualunque combinazione di valori
delle variabili
44
Algebra Booleana a due valori: Assiomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•
Gli operatori descritti godono delle proprietà definite dai
seguenti assiomi (postulati di Huntington):
 Le operazioni di disgiunzione (+) e congiunzione (·) sono
commutative, cioè per ogni elemento a,b  B
a+b = b+a
a·b = b·a
 Esiste un elemento neutro (o identità) rispetto a + (indicato
con 0) e un elemento neutro rispetto a · (indicato con 1), cioè:
a+0=a
a·1=a
 Le due operazioni sono distributive rispetto all’altra, cioè per
ogni a,b,c  B, risulta:
a+(b·c)=(a+b)·(a+c)
a·(b+c)=(a·b)+(a·c)
 Per ogni a  B esiste l’elemento a’ B, detto negazione
logica o complemento di a, tale che:
a+a’=1
a·a’=0
Algebra di Commutazione: Proprietà 1
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1: associativa
a+(b+c)=(a+b)+c
a*(b*c)=(a*b)*c
2: idempotenza
a+a=a
a*a=a
3: elemento nullo
a+1=1
a*0=0
4: unicità elemento inverso:
il complemento di a, a’, è unico
5: assorbimento
a+(a*b)=a
a*(a+b)=a
Algebra di Commutazione: Proprietà 2
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
6: Semplificazione
a+a’b = a+b
a*(a’+b) = a*b
7: involuzione
((a)’)’ =
a
8: Leggi di De Morgan
(a+b)’ = a’*b’
(a*b)’ = a’+b’
9: consenso
a*b+a’*c+b*c = a*b + a’*c
(a+b)*(a’+c)*(b+c)=(a+b)*(a’+c)
- 47 -
Uso delle proprietà
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Trasformare un’espressione logica in un’altra, differente
per aspetto ma equivalente:






not A and B or A 
(assorbimento)
not A and B or (A or A and B)  (togli le parentesi)
not A and B or A or A and B 
(commutativa)
not A and B or A and B or A 
(distributiva)
(not A or A) and B or A 
(legge dell’elemento 1)
true and B or A 
(vero and B  B)
B or A è più semplice dell’espressione originale
• Si può verificare l’equivalenza con le tabelle di verità
• Occorre conoscere un’ampia lista di proprietà e si deve
riuscire a “vederle” nell’espressione (talvolta è difficile)
48
Problemi di fine giornata…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Si scriva un programma in C che
richiede l’inserimento di un numero
intero positivo, se l’inserimento e’ errato
ritorna un messaggio di errore
• Si scriva un programma in C che, dati
due caratteri, li ordina in ordine
alfabetico “inverso”
49
Fonti per lo studio + Credits
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Fonti per lo studio
 Introduzione ai sistemi informatici, D.
Sciuto, G. Buonanno, L. Mari, 4a Ed,
McGrawHill
• Capitolo 2
• Credits
 Daniele Braga
• http://home.dei.polimi.it/braga/
 Cristiana Bolchini
• http://home.dei.polimi.it/bolchini/didattica/retilogichea/index.
htm