algebra di boole, elementi di logica e mappe di...
TRANSCRIPT
![Page 1: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/1.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Algebra di Boole, elementi di logica e Mappe di Karnaugh
Marco D. Santambrogio – [email protected]
![Page 2: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/2.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Progetti
• Meeting§ Quando: 22 Marzo @2pm§ Dove: Sala Conferenze @DEIB
2
![Page 3: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/3.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Progetti
• Meeting§ Quando: 22 Marzo @2pm§ Dove: Sala Conferenze @DEIB
• Problemi email§ [email protected]§ [email protected]§ [email protected]§ [email protected]
3
![Page 4: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/4.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Progetti
• Meeting§ Quando: 22 Marzo @2pm§ Dove: Sala Conferenze @DEIB
• Problemi email§ [email protected]§ [email protected]§ [email protected]§ [email protected]
4
![Page 5: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/5.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Problema: caratteri MaIuScOli
Si scriva un programma che, preso un carattere minuscolo da tastiera, ne riporta a video l’equivalente maiuscolo
5
![Page 6: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/6.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
HELP: errori sull’input
6
![Page 7: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/7.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Problema: errori sull’input
• 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
7
![Page 8: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/8.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Pseudocodice
• Dati§ L’insieme dei caratteri ammissibili
{a, b, c, …, z}
1. Richiedere l’inserimento di un carattere
2. Se carattere inserito corretto3. Allora stampa a video carattere-324. Altrimenti stampa a video un
messaggio di errore
8
![Page 9: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/9.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Condizione da verificare
• Dati§ L’insieme dei caratteri ammissibili
{a, b, c, …, z}
• Il carattere inserito deve essere§ =>a§ <= z
9
![Page 10: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/10.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Obiettivi
• Algebra di Boole§ Algebra di boole a due valori: algebra
di commutazione§ Operazioni logiche§ Espressioni logiche
• Funzioni booleane• Forme canoniche• Karnaugh e Mappe di Karnaugh
10
![Page 11: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/11.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
11
• 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)
Cenni all’algebra di Boole
![Page 12: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/12.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
- 12 -
Algebra Booleana: definizione
• 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
![Page 13: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/13.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Algebra Booleana a due valori: Algebra di Commutazione
“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]
- 13 -
![Page 14: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/14.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
14
• 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
Operazioni logiche fondamentali
![Page 15: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/15.jpg)
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
• Mentre l’operazione a un solo elemento (unary operation) detta complementazione o negazione (NOT) è definita come
§ Nota: il simbolo associato al NOT è spesso indicato come ’(esempio x’), !(esempio !x) o sopra segnando la variabile.
0 1 1 0
+ 0 1 0 0 1 1 1 1
* 0 1 0 0 0 1 0 1
Operazioni logiche fondamentali
‘
![Page 16: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/16.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
16
Operatori logici di base e loro tabelle di verità
A B A and B0 0 00 1 01 0 01 1 1(prodotto logico)
A B A or B0 0 00 1 11 0 11 1 1(somma logica)
A not A
0 1
1 0
(negazione)
Le tabelle elencano tutte le possibili combinazioni in ingresso e il risultato associato a ciascuna combinazione
![Page 17: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/17.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
17
• 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)
Espressioni logiche (o Booleane)
![Page 18: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/18.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
A and B or not C
A B C X = A and B Y = not C X or Y
0 0 0 0 and 0 = 0 not 0 = 1 0 or 1 = 1
0 0 1 0 and 0 = 0 not 1 = 0 0 or 0 = 0
0 1 0 0 and 1 = 0 not 0 = 1 0 or 1 = 1
0 1 1 0 and 1 = 0 not 1 = 0 0 or 0 = 0
1 0 0 1 and 0 = 0 not 0 = 1 0 or 1 = 1
1 0 1 1 and 0 = 0 not 1 = 0 0 or 0 = 0
1 1 0 1 and 1 = 1 not 0 = 1 1 or 1 = 1
1 1 1 1 and 1 = 1 not 1 = 0 1 or 0 = 1
Tabella di verità di un’espressione logica
![Page 19: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/19.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
19
A B NOT ((A OR B) AND (NOT A)) 0 0 0 1 1 0 1 1
A B C ( B OR NOT C) AND (A OR NOT C) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
0100
0011
1011
0011
0101
0111
00110011
1100
01010101
01010101
10101011
00001111
10101010
10101010
10111011
10101111
Due esercizi
![Page 20: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/20.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
20
• 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)
A che cosa servono le espressioni logiche?
![Page 21: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/21.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
21
• 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)
Che cosa non si può modellare tramite espressioni logiche?
![Page 22: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/22.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
22
![Page 23: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/23.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Problema: caratteri MaIuScOli
Si scriva un programma che, preso un carattere minuscolo da tastiera, ne riporta a video l’equivalente maiuscolo
23
![Page 24: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/24.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Pseudocodice
• Dati§ L’insieme dei caratteri ammissibili
{a, b, c, …, z}
1. Richiedere linserimento di un carattere
2. Se carattere inserito corretto3. Allora stampa a video carattere-324. Altrimenti stampa a video un
messaggio di errore
24
![Page 25: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/25.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Condizione da verificare
• Dati§ L’insieme dei caratteri ammissibili
{a, b, c, …, z}
• Il carattere inserito deve essere§ =>a§ <= z
25
![Page 26: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/26.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Maiuscolo: solo if
26
![Page 27: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/27.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Maiuscolo: esecuzione
27
![Page 28: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/28.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Condizione da verificare
• Il carattere inserito deve essere§ X: =>a§ Y: <= z
• Come vogliamo che si comporti il nostro modello rispetto a X e Y?
28
![Page 29: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/29.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Condizione da verificare
• Il carattere inserito deve essere§ X: =>a§ Y: <= z
• Come vogliamo che si comporti il nostro modello rispetto a X e Y?§ Se X = 0?
29
![Page 30: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/30.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Condizione da verificare
• Il carattere inserito deve essere§ X: =>a§ Y: <= z
• Come vogliamo che si comporti il nostro modello rispetto a X e Y?§ Se X = 0? Vogliamo una uscita FALSA
30
![Page 31: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/31.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Condizione da verificare
• Il carattere inserito deve essere§ X: =>a§ Y: <= z
• Come vogliamo che si comporti il nostro modello rispetto a X e Y?§ Se X = 0? Vogliamo una uscita FALSA§ Se Y = 0?
31
![Page 32: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/32.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Condizione da verificare
• Il carattere inserito deve essere§ X: =>a§ Y: <= z
• Come vogliamo che si comporti il nostro modello rispetto a X e Y?§ Se X = 0? Vogliamo una uscita FALSA§ Se Y = 0? Vogliamo una uscita FALSA
32
![Page 33: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/33.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Condizione da verificare
• Il carattere inserito deve essere§ X: =>a§ Y: <= z
• Come vogliamo che si comporti il nostro modello rispetto a X e Y?§ Se X = 0? Vogliamo una uscita FALSA§ Se Y = 0? Vogliamo una uscita FALSA§ Se X = 1 e Y = 1? Uscita VERA!
33
![Page 34: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/34.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Condizione da verificare
• Il carattere inserito deve essere§ X: =>a§ Y: <= z
• Come vogliamo che si comporti il nostro modello rispetto a X e Y?
34
X Y USCITA0 0 00 1 01 0 01 1 1
![Page 35: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/35.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Condizione da verificare
• Il carattere inserito deve essere§ X: =>a§ Y: <= z
• Come vogliamo che si comporti il nostro modello rispetto a X e Y?
35
X Y USCITA0 0 00 1 01 0 01 1 1
Vi ricorda
qualche cosa?
![Page 36: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/36.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Condizione da verificare
• Il carattere inserito deve essere§ X: =>a§ Y: <= z
• Come vogliamo che si comporti il nostro modello rispetto a X e Y?
36
X Y USCITA0 0 00 1 01 0 01 1 1
Vi ricorda
qualche cosa?
AND!!!
![Page 37: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/37.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Condizione da verificare
• Il carattere inserito deve essere§ X: =>a§ Y: <= z
• Come vogliamo che si comporti il nostro modello rispetto a X e Y?
37
Vi ricorda
qualche cosa?
AND!!!
X Y X AND Y0 0 00 1 01 0 01 1 1
(prodotto logico)
![Page 38: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/38.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Maiuscolo: AND
38
![Page 39: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/39.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Maiuscolo: codice ottimizzato
39
![Page 40: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/40.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Maiuscolo: esecuzione
40
![Page 41: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/41.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Qualche cosa di più complesso…
• Si accettano soltanto numeri dispari, primi, oppure maggiori di tre§ a: dispari§ b: primi§ c: maggiori di 3
41
![Page 42: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/42.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Qualche cosa di più complesso…
• Si accettano soltanto numeri dispari, primi, oppure maggiori di tre§ a: dispari§ b: primi§ c: maggiori di 3
42
a b c f(a,b,c) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
![Page 43: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/43.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Qualche cosa di più complesso…
• Si accettano soltanto numeri dispari, primi, oppure maggiori di tre§ a: dispari§ b: primi§ c: maggiori di 3
43
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
![Page 44: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/44.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Qualche cosa di più complesso…
• Si accettano soltanto numeri dispari, primi, oppure maggiori di tre§ a: dispari§ b: primi§ c: maggiori di 3
44
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
![Page 45: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/45.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Per farlo…
45
Qualche definizione
![Page 46: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/46.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Letterale
• Un letterale è una coppia (Variabile,Valore)§ (x,1) è indicato come x (variabile in
forma naturale); § (x,0) rappresenta la variabile x in forma
negata (complementata) ed è indicato come x’ (oppure !x).
46
![Page 47: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/47.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Termine prodotto
• Un termine prodotto è il prodotto logico o congiunzione (AND) di più letterali.
• Un termine prodotto in cui compaiono letterali corrispondenti a tutte le variabili della funzione e tale per cui la configurazione di valori delle variabili definite dai letterali genera un valore 1 della funzione stessa nella tabella delle verità, costituisce un mintermine della funzione§ Ad esempio, a’b’c e ab’c rappresentano due
mintermini della funzione di cui si è prima data la tabella delle verità
• Un termine prodotto in cui compaiono solo alcuni dei letterali e che corrisponda a un insieme di 1 della funzione è denominato implicante.
47
![Page 48: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/48.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Termine somma (duale)
• Un termine somma è la somma logica o disgiunzione (OR) di più letterali.
• Un termine somma in cui compaiono letterali corrispondenti a tutte le variabili della funzione e tale per cui la configurazione di valori delle variabili definite dai letterali genera un valore 0 della funzione stessa nella tabella delle verità, costituisce un maxtermine della funzione§ Ad esempio, a+b+c e a+b’+c rappresentano due
maxtermini della funzione data
• Un termine somma in cui compaiono solo alcuni dei letterali e che corrisponda a un insieme di 0 della funzione è denominato implicato.
48
![Page 49: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/49.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Funzioni
• Una funzione booleana di n variabili può essere espressa attraverso una espressione booleana di n variabili costituita da letterali, costanti, operatori AND, OR e NOT.
49
![Page 50: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/50.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Funzioni
• Una funzione booleana di n variabili può essere espressa attraverso una espressione booleana di n variabili costituita da letterali, costanti, operatori AND, OR e NOT.
• Esempio di espressione booleana: f(a,b,c)=ab+a’c’
50
![Page 51: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/51.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Nota
• Il numero di espressioni booleane di n variabili definite su una algebra booleana B è infinito. § La relazione tra espressioni booleane e
funzioni booleane non è 1 a 1
51
![Page 52: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/52.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Nota
• Il numero di espressioni booleane di n variabili definite su una algebra booleana B è infinito. § La relazione tra espressioni booleane e
funzioni booleane non è 1 a 1
52
a b c f(a,b,c) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1
![Page 53: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/53.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Nota
• Il numero di espressioni booleane di n variabili definite su una algebra booleana B è infinito. § La relazione tra espressioni booleane e
funzioni booleane non è 1 a 1
53
a b c f(a,b,c) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1
f(a,b,c)= (a’*b’)’*a
f(a,b,c)= a
f(a,b,c)= ...
![Page 54: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/54.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ma quindi…
54
![Page 55: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/55.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ma quindi…
• Si accettano soltanto numeri dispari, primi, oppure maggiori di tre§ a: dispari§ b: primi§ c: maggiori di 3
55
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
![Page 56: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/56.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ma quindi…
• Data una funzione booleana§ ad esempio, mediante la tabella delle veritৠil problema è identificare almeno una
espressione booleana ad essa corrispondente
56
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
![Page 57: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/57.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ma quindi… diventa...
• Data una funzione booleana§ ad esempio, mediante la tabella delle veritৠil problema è identificare almeno una
espressione booleana ad essa corrispondente
57
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
![Page 58: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/58.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Come calcolare l’espressione booleana
• Data una funzione booleana, la soluzione iniziale al problema di determinare una sua espressione consiste nel ricorso alle forme canoniche
• Le forme canoniche sono:§ la forma somma di prodotti (SoP)§ quella prodotto di somme (PoS)
58
![Page 59: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/59.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Prima forma canonica
• Mettendo in OR i mintermini della funzione si ottiene l’espressione booleana della funzione stessa (SoP)
59
a b f(a,b) 0 0 0 0 1 1 1 0 0 1 1 1
f(a,b) =
=
![Page 60: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/60.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Prima forma canonica
• Mettendo in OR i mintermini della funzione si ottiene l’espressione booleana della funzione stessa (SoP)
60
a b f(a,b) 0 0 0 0 1 1 1 0 0 1 1 1
a b f2(a,b) 0 0 0 0 1 0 1 0 0 1 1 1
a b f1(a,b) 0 0 0 0 1 1 1 0 0 1 1 0
= +
f(a,b) =
![Page 61: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/61.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Prima forma canonica
• Mettendo in OR i mintermini della funzione si ottiene l’espressione booleana della funzione stessa (SoP)
61
a b f(a,b) 0 0 0 0 1 1 1 0 0 1 1 1
a b f2(a,b) 0 0 0 0 1 0 1 0 0 1 1 1
a b f1(a,b) 0 0 0 0 1 1 1 0 0 1 1 0
= +
a’b ab f(a,b) + =
![Page 62: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/62.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Seconda forma canonica
• Mettendo in AND i maxtermini della funzione si ottiene l’espressione booleana della funzione stessa (PoS)
62
a b f(a,b) 0 0 0 0 1 1 1 0 0 1 1 1
=
f(a,b) =
![Page 63: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/63.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Seconda forma canonica
• Mettendo in AND i maxtermini della funzione si ottiene l’espressione booleana della funzione stessa (PoS)
63
a b f(a,b) 0 0 0 0 1 1 1 0 0 1 1 1
a b f2(a,b) 0 0 1 0 1 1 1 0 0 1 1 1
a b f1(a,b) 0 0 0 0 1 1 1 0 1 1 1 1
= *
f(a,b) =
![Page 64: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/64.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Seconda forma canonica
• Mettendo in AND i maxtermini della funzione si ottiene l’espressione booleana della funzione stessa (PoS)
64
a b f(a,b) 0 0 0 0 1 1 1 0 0 1 1 1
a b f2(a,b) 0 0 1 0 1 1 1 0 0 1 1 1
a b f1(a,b) 0 0 0 0 1 1 1 0 1 1 1 1
= *
a+b a’+b f(a,b) = *
![Page 65: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/65.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Il problema di partenza
• Si accettano soltanto numeri dispari, primi, oppure maggiori di tre§ a: dispari§ b: primi§ c: maggiori di 3
65
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
![Page 66: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/66.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Prima forma canonica
!a!bc
66
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
![Page 67: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/67.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Prima forma canonica
!a!bc + !abc
67
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
![Page 68: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/68.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Prima forma canonica
!a!bc + !abc + a!bc
68
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
![Page 69: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/69.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Prima forma canonica
!a!bc + !abc + a!bc + ab!c
69
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
![Page 70: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/70.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Prima forma canonica
!a!bc + !abc + a!bc + ab!c + abc
70
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
![Page 71: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/71.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Prima forma canonica
!a!bc + !abc + a!bc + ab!c + abc
71
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
![Page 72: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/72.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Il problema
• Ridurre la complessità di una (o più) funzione(i) booleana(e) espressa(e) in forma di Prodotto di Somme o di Somma di Prodotti (SOP).
• Si considerano le forme canoniche come soluzioni iniziali
72
![Page 73: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/73.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Il problema
• Ridurre la complessità di una (o più) funzione(i) booleana(e) espressa(e) in forma di Prodotto di Somme o di Somma di Prodotti (SOP).
• Si considerano le forme canoniche come soluzioni iniziali
• Obiettivi§ Riduzione del numero dei termini
prodotto (principale)§ Riduzione del numero di letterali
(secondario)
73
![Page 74: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/74.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Si propone di identificare forme minime a due livelli applicando la regola di riduzione a Z + a' Z = (a+a') Z = Z con Z termine prodotto di n-1 variabili.§ Esempio: abcd’ + ab’cd’ = acd’
- 74 -
Karnaugh
![Page 75: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/75.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Si propone di identificare forme minime a due livelli applicando la regola di riduzione a Z + a' Z = (a+a') Z = Z con Z termine prodotto di n-1 variabili.§ Esempio: abcd’ + ab’cd’ = acd’
• La riduzione può essere applicata iterativamente§ Esempio: abc’d’+abc’d+abcd’+abcd= abc’(d’+d)
+abc(d’+d) = abc’+abc = ab(c’+c) = ab
- 75 -
Karnaugh
![Page 76: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/76.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Si propone di identificare forme minime a due livelli applicando la regola di riduzione a Z + a' Z = (a+a') Z = Z con Z termine prodotto di n-1 variabili.§ Esempio: abcd’ + ab’cd’ = acd’
• La riduzione può essere applicata iterativamente§ Esempio: abc’d’+abc’d+abcd’+abcd= abc’(d’+d)
+abc(d’+d) = abc’+abc = ab(c’+c) = ab
Nota: si osservi che la applicazione della relazione identificata è applicata ad un numero di termini pari a 2n quindi 2, 4, 8, ...
- 76 -
Karnaugh
![Page 77: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/77.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Karnaugh sul nostro esempio
f(a,b,c)=!a!bc + !abc + a!bc + ab!c + abc
77
![Page 78: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/78.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Karnaugh sul nostro esempio
f(a,b,c)=!a!bc + !abc + a!bc + ab!c + abc!ac (!b + b) + a!bc + ab!c + abc
78
![Page 79: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/79.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Karnaugh sul nostro esempio
f(a,b,c)=!a!bc + !abc + a!bc + ab!c + abc!ac (!b + b) + a!bc + ab!c + abc
!ac + a!bc + ab!c + abc
79
![Page 80: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/80.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Karnaugh sul nostro esempio
f(a,b,c)=!a!bc + !abc + a!bc + ab!c + abc!ac (!b + b) + a!bc + ab!c + abc
!ac + a!bc + ab!c + abc!ac + a!bc + ab (!c + c)
80
![Page 81: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/81.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Karnaugh sul nostro esempio
f(a,b,c)=!a!bc + !abc + a!bc + ab!c + abc!ac (!b + b) + a!bc + ab!c + abc
!ac + a!bc + ab!c + abc!ac + a!bc + ab (!c + c)
!ac + a!bc + ab
81
![Page 82: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/82.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
82
![Page 83: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/83.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Una mappa di Karnaugh è uno schema deducibile dalla rappresentazione geometrica delle configurazioni binarie.
• Definizione utili:§ Distanza di Hamming: numero di bit che cambia nel
passare da una configurazione binaria ad un’altra• Esempio: la distanza di Hamming tra le configurazioni 01001
e 10101 è 3 poiché cambiano 3 bit.
• L’applicazione della regola di riduzione consiste nell’identificare le configurazioni binarie associate ai termini prodotto che sono a distanza di Hamming unitaria.§ Esempio: i termini prodotto abcd’ e ab’cd’
corrispondono a 1110 e 1010 e sono a distanza di Hamming pari ad 1.
- 83 -
Mappe di Karnaugh
![Page 84: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/84.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Una funzione booleana a n variabili f: {0,1}n → {0,1} può essere rappresenta in modo comodo utilizzando una tabella della funzione o tabella della verità.
• In modo assolutamente equivalente una funzione a n variabili può essere associata ad una rappresentazione cartesiana in uno spazio a n dimensioni
f(a,b,c)=ONset(001,011,101,110,111)
- 84 -
Funzione in uno spazio n-D
ONset= insieme di 1 della funzione
![Page 85: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/85.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Punti a distanza di Hamming 1 in n-D
• Nella rappresentazione cartesiana di una funzione in uno spazio a n dimensioni, collegando i vertici le cui configurazioni sono a distanza di Hamming unitaria si ottiene un n-cubo. § Spazio a 1 dimensione (1 variabile)
• È una linea, e l’1-cubo è un segmento: i due vertici sono associati alle configurazioni 0 e 1
§ Spazio a 2 dimensioni (2 variabili):• È il piano, il 2-cubo è un quadrato che si ottiene dall’1-cubo per
proiezione. Si premette 0 alle configurazioni dei vertici originali, 1 a quelle dei vertici proiettati
- 85 -
1 0
01 00
11 10
![Page 86: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/86.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
§ Spazio a 3 dimensioni (3 variabili)• Il 3-cubo è un solido, che si ottiene dal 2-cubo per proiezione, premettendo 0 alle configurazioni dei vertici originali, 1 a quelle dei vertici proiettati
- 86 -
101 100
111 110
001 000
011 010
Punti a distanza di Hamming 1 in n-D
![Page 87: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/87.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
f(a,b,c)=ONset(001,011,101,110,111)
- 87 -
Funzione in uno spazio n-D
ONset= insieme di 1 della funzione
![Page 88: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/88.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
f(a,b,c)=ONset(001,011,101,110,111)
- 88 -
Funzione in uno spazio n-D
101 100
111 110
001 000
011 010 a
b
c
1
0 dove
ONset= insieme di 1 della funzione
![Page 89: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/89.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Di fatto, la rappresentazione in uno spazio a n dimensioni non è maneggevole § Quindi, si passa allo sviluppo nel piano dei cubi§ Lo sviluppo nel piano di un 3-cubo implica il taglio del
cubo§ Il taglio deve mantenere intatta, concettualmente, la
adiacenza fra vertici. Si presti molta attenzione all’ordinamento delle coordinate• Ordinamento delle coordinate mantiene le distanze di
Hamming e non coincide con la numerazione consecutiva
- 89 -
Sviluppo nel piano dei cubi
![Page 90: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/90.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Di fatto, la rappresentazione in uno spazio a n dimensioni non è maneggevole § Quindi, si passa allo sviluppo nel piano dei cubi§ Lo sviluppo nel piano di un 3-cubo implica il taglio del
cubo§ Il taglio deve mantenere intatta, concettualmente, la
adiacenza fra vertici. Si presti molta attenzione all’ordinamento delle coordinate• Ordinamento delle coordinate mantiene le distanze di
Hamming e non coincide con la numerazione consecutiva
- 90 -
101 100
111 110
001 000
011 010 a
b
c
1
0 dove
00 01 11 10 0 1
0 0 1 0 1 1 1 1
a,b c
"
"
"
Sviluppo nel piano dei cubi
![Page 91: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/91.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Si ricorda che: un implicante è un termine prodotto in cui compaiono solo alcuni dei letterali.
- 91 -
00 01 11 10 00 01 11 10
1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1
a,b c,d
F(a,b,c,d)=a’b’c’d’+a’b’cd’+a’bc’d’+ab’c’d+ ab’cd+ab’cd’
F(a,b,c,d)=a’b’d’+a’c’d’+...
raggruppamento 1
raggruppamento2
Implicante 1
Implicante 2
raggruppamento 1
raggruppamento 2
Caratteristiche delle mappe
![Page 92: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/92.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1. Individuare gli implicanti primi e primi essenziali;§ Implicante primo
• Termine prodotto associato ad un raggruppamento di dimensione massima.
§ implicante primo essenziale• Implicante primo che copre uno o più 1 non coperti
da nessun altro implicante primo.2. Copertura:
§ Scelta del minor numero di implicanti primi e primi essenziali
- 92 -
implicanti implicanti primi implicanti primi essenziali
Metodo
![Page 93: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/93.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Identificare una forma SoP che includa il numero minimo di implicanti e – a parità di numero di prodotti – gli implicanti col minimo numero di letterali (definita come forma minima) garantendo la copertura di tutti gli 1 della funzione.
• Teorema:§ Esiste sicuramente una forma minima costituita da soli
implicanti primi • sulla mappa di Karnaugh si identificano tutti gli implicanti primi.
– Nota: la somma di tutti gli implicanti primi è spesso ridondante. § Implicanti primi essenziali devono essere inclusi nella forma
minima.§ Una forma minima costituita da soli implicanti primi
essenziali è unica• Condizione sufficiente.
- 93 -
Scopo delle mappe
![Page 94: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/94.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Esempio
- 94 -
00 01 11 10 00 01 11 10
1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1
a,b c,d
1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1
raccoglimento
Raccoglimento di dimensione massima
ERRORE: valido raccoglimento solo di 2,4,...
!
![Page 95: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/95.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
- 95 -
00 01 11 10 00 01 11 10
1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1
a,b c,d
1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1
Raccoglimento di dimensione massima essenziale
1 appartenente ad un solo implicante primo
Raccoglimento di dimensione massima
!
Esempio: continua
![Page 96: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/96.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Ad ogni raccoglimento è associato un termine prodotto.
• Il termine prodotto (implicante) è ottenuto:§ identificando le variabili che non
cambiano mai di valore § riportando ogni variabile in modo
naturale • (esempio: a) se il valore che essa assume è 1 • in modo complementato (esempio: a’) se il
valore da essa assunto è 0
- 96 -
Definizione del termine prodotto
![Page 97: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/97.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
- 97 -
00 01 11 10 00 01 11 10
1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1
a,b c,d
1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1
00 01
00 01
a,b
c,d 11 10
11 10
b e d cambiano valore: non compaiono nel termine prodotto. a e c compaiono come 0 quindi a’ e c’ . Il termine prodotto è a’c’.
d cambia valore
b cambia valore !
Identificazione del termine prodotto
![Page 98: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/98.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Sotto insieme degli implicanti identificati tale per cui nessun 1 della funzione rimane scoperto.§ Poiché ogni implicante scelto aumenta il
costo della realizzazione della funzione, il numero di implicanti da scegliere deve essere il minore possibile.
§ L’obiettivo è la riduzione del costo; questo si traduce nella identificazione della copertura di minima cardinalità: • sotto insieme degli implicanti primi e primi ed
essenziali identificati che realizza una copertura della funzione che è di cardinalità minima.
- 98 -
Copertura
![Page 99: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/99.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1. Si scelgono tutti gli implicanti primi essenziali.§ Gli implicanti primi essenziali devono essere
parte della copertura poiché “sono essenziali” e, quindi, non è possibile fare a meno di loro.
2. Si eliminano tutti gli implicanti primi che sono coperti da quelli essenziali (eliminazione implicanti completamente ridondanti)§ gli implicanti eliminati, detti completamente
ridondanti, coprono degli 1 che sono già ricoperti da quelli essenziali e, quindi, non servono ed aumentano il costo.
3. Si seleziona il numero minore degli implicanti primi che sono rimasti.§ gli implicanti residui sono detti parzialmente
ridondanti.
- 99 -
Copertura: scelta implicanti
![Page 100: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/100.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
- 100 -
E quindi, il nostro esempio…
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
f (a,b,c) = 001,011,101,110,111( )∑
00 01 11 10 0 1
0 0 1 0 1 1 1 1
a,b c
![Page 101: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/101.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
- 101 -
E quindi, il nostro esempio…
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
f (a,b,c) = 001,011,101,110,111( )∑Implicanti primi essenziali
00 01 11 10 0 1
0 0 1 0 1 1 1 1
a,b c
c
![Page 102: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/102.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
- 102 -
E quindi, il nostro esempio…
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
f (a,b,c) = 001,011,101,110,111( )∑
c ab
Implicanti primi essenziali
00 01 11 10 0 1
0 0 1 0 1 1 1 1
a,b c
![Page 103: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/103.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
- 103 -
E quindi, il nostro esempio…
a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
f (a,b,c) = 001,011,101,110,111( )∑
c ab
Implicanti primi essenziali
00 01 11 10 0 1
0 0 1 0 1 1 1 1
a,b c
f(a,b,c)= ab + c Forma minima
![Page 104: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/104.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Osservazione
• Ma se la forma minima èf(a,b,c) = ab + c
104
00 01 11 10 0 1
0 0 1 0 1 1 1 1
a,b c
![Page 105: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/105.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Osservazione
• Ma se la forma minima èf(a,b,c) = ab + c
• La soluzione (S78)f(a,b,c) = !ac + a!bc + ab ?
105
00 01 11 10 0 1
0 0 1 0 1 1 1 1
a,b c
![Page 106: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/106.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Osservazione
• Ma se la forma minima èf(a,b,c) = ab + c
• La soluzione (S78)f(a,b,c) = !ac + a!bc + ab ?
106
00 01 11 10 0 1
0 0 1 0 1 1 1 1
a,b c
00 01 11 10 0 1
0 0 1 0 1 1 1 1
a,b c
![Page 107: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/107.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Problemi di fine giornata…
• 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”
107
![Page 108: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/108.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Appendice (utile per la prox exe)
108
![Page 109: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/109.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
109
• 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)
Tautologie e Contraddizioni
![Page 110: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/110.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
110
• Due espressioni logiche si dicono equivalenti (e si indica con ⇔) se hanno la medesima tabella di verità. La verifica è algoritmica. Per esempio:
A B not A and not B ⇔ not (A or B)
0 0 1 and 1 = 1 not 0 = 1
0 1 1 and 0 = 0 not 1 = 0
1 0 0 and 1 = 0 not 1 = 0
1 1 0 and 0 = 0 not 1 = 0
• Espressioni logiche equivalenti modellano gli stessi stati di verità a fronte delle medesime variabili
Equivalenza tra espressioni
![Page 111: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/111.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
111
Proprietà dell’algebra di Boole
• 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
![Page 112: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/112.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Algebra Booleana a due valori: Assiomi
• 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
Vale
per
la s
omm
a ri
spet
to a
l pro
dott
o co
me
per
il pr
odot
to r
ispe
tto
alla
so
mm
a –
non
esis
te p
rece
denz
a fr
a le
due
ope
razi
oni,
occ
orre
sem
pre
imm
agin
are
le p
aren
tesi
“so
ttin
tese
” in
torn
o a
ogni
app
licaz
ione
di
un’o
pera
zion
e.
![Page 113: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/113.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Algebra di Commutazione: Proprietà 1
1: associativaa+(b+c)=(a+b)+c a*(b*c)=(a*b)*c
2: idempotenzaa+a=a a*a=a
3: elemento nulloa+1=1 a*0=0
4: unicità elemento inverso: il complemento di a, a’, è unico
5: assorbimentoa+(a*b)=a a*(a+b)=a
![Page 114: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/114.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
- 114 -
6: Semplificazionea+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: consensoa*b+a’*c+b*c = a*b + a’*c (a+b)*(a’+c)*(b+c)=(a+b)*(a’+c)
Algebra di Commutazione: Proprietà 2
![Page 115: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/115.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
115
• 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)
Uso delle proprietà
![Page 116: Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,](https://reader034.vdocumenti.com/reader034/viewer/2022042407/5f220c3d05392207c1141e1a/html5/thumbnails/116.jpg)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Fonti per lo studio + Credits
• 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