fondamenti di informatica · l’algebra di boole –2/4 •relazione con i circuiti logici •si...
TRANSCRIPT
![Page 1: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/1.jpg)
Fondamenti di InformaticaAlgebra d i Boole
P r o f. R a f fa e l e P i z zo l a n t e
A . A . 2 0 1 6 / 1 7
![Page 2: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/2.jpg)
L’Algebra di Boole – 1/4• Storia• Il matematico inglese George Boole nel 1847 fondò un campo della
matematica e della filosofia chiamato logica simbolica
• Shannon per primo applicò la logica simbolica ai circuiti logici nel 1939
• Basi• Variabili booleane (o binarie)
• Variabili i cui valori possono essere 0 oppure 1
• Funzioni booleane
• Funzioni i cui input ed output sono variabili booleane
Algebra di Boole
![Page 3: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/3.jpg)
L’Algebra di Boole – 2/4•Relazione con i circuiti logici• Si studia l’algebra booleana poiché le sue funzioni sono
isomorfe ai circuiti digitali:• un circuito digitale può essere espresso tramite un’espressione booleana e
viceversa
• Le variabili booleane corrispondono a segnali
• Le funzioni booleane corrispondono a circuiti
Algebra di Boole
![Page 4: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/4.jpg)
L’Algebra di Boole – 3/4• Una variabile booleana è• Una variabile che può assumere esclusivamente UN valore fra 0 o 1
• Sia 𝑥 una variabile booleana, allora 𝑥 = 0 oppure 𝑥 = 1
• Contempla quindi due stati che si escludono a vicenda: 0 e 1 (falso e vero)• Gli stati possono descrivere, ad esempio, lo stato di apertura o chiusura di un
circuito, ecc.
0 1
Algebra di Boole
![Page 5: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/5.jpg)
L’Algebra di Boole – 4/4 • Sulle variabili e i valori booleani si definiscono gli operatori• AND• OR• NOT• Ed altri definiti a partire da essi
•Gli operatori AND e OR sono operatori binari: agiscono su dueoperandi
•L’operatore NOT è un operatore unario: agisce su un solo operando
•Un operando può essere:• Variabile booleana• Valore booleano (1 o 0)
Algebra di Boole
![Page 6: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/6.jpg)
Gli operatori (o funzioni)• Gli operatori (o funzioni)• AND
• OR
• NOT
Algebra di Boole
![Page 7: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/7.jpg)
Gli operatori (o funzioni)• Gli operatori (o funzioni)• AND
• OR
• NOT
Algebra di Boole
![Page 8: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/8.jpg)
AND – Prodotto Logico• Il risultato dell’operatore (o funzione) AND è 1 se il valore di entrambi gli operandi è 1. Il risultato è 0 negli altri casi
• Date n variabili binarie indipendenti, il loro prodotto logico (AND) è dato da
x1 x2 … xn =0 se almeno una xi vale 0, 𝑐𝑜𝑛 1 ≤ 𝑖 ≤ 𝑛
1 se x1= x2= …= xn = 1
𝑥1 𝑥2 𝐹 𝑥1, 𝑥2 = 𝑥1 × 𝑥20 0 0
0 1 0
1 0 0
1 1 1
Algebra di Boole
![Page 9: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/9.jpg)
AND – Prodotto Logico• Il risultato dell’operatore (o funzione) AND è 1 se il valore di entrambi gli operandi è 1. Il risultato è 0 negli altri casi
• Date n variabili binarie indipendenti, il loro prodotto logico (AND) è dato da
x1 x2 … xn =0 se almeno una xi vale 0, 𝑐𝑜𝑛 1 ≤ 𝑖 ≤ 𝑛
1 se x1= x2= …= xn = 1
𝑥1 𝑥2 𝐹 𝑥1, 𝑥2 = 𝑥1 × 𝑥20 0 0
0 1 0
1 0 0
1 1 1
Tavola di verità
Algebra di Boole
![Page 10: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/10.jpg)
AND – Prodotto LogicoPossibili Rappresentazioni• x & y
• x and y
• x ∧ 𝒚
• x ∩ 𝒚
• x * y
• x × 𝒚
• xy
Algebra di Boole
![Page 11: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/11.jpg)
AND – Prodotto LogicoPossibili Rappresentazioni• x & y
• x and y
• x ∧ 𝑦
• x ∩ 𝑦
•x * y
• x × 𝒚
• xy
Algebra di Boole
![Page 12: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/12.jpg)
Gli operatori (o funzioni)• Gli operatori (o funzioni)• AND
• OR
• NOT
Algebra di Boole
![Page 13: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/13.jpg)
OR – Somma Logica• Il risultato dell’operatore (o funzione) OR è 1 se almeno uno degli operandi vale 1. Il risultato è 0 negli altri casi
• Date n variabili binarie, la loro somma logica (OR) è data da
x1+ x2+ …+ xn =
1 se almeno una xi vale 1, 𝑐𝑜𝑛 1 ≤ 𝑖 ≤ 𝑛
0 se x1= x2= …= xn = 0
𝑥1 𝑥2 𝐹 𝑥1, 𝑥2 = 𝑥1 + 𝑥20 0 0
0 1 1
1 0 1
1 1 1
Algebra di Boole
![Page 14: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/14.jpg)
OR – Somma LogicaPossibili Rappresentazioni• x | y
• x # y
• x or y
• x ∪ 𝒚
• x ∨ 𝒚
• x + y
Algebra di Boole
![Page 15: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/15.jpg)
OR – Somma LogicaPossibili Rappresentazioni• x | y
• x # y
• x or y
• x ∪ 𝑦
• x ∨ 𝑦
• x + y
Algebra di Boole
![Page 16: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/16.jpg)
Gli operatori (o funzioni)• Gli operatori (o funzioni)• AND
• OR
• NOT
Algebra di Boole
![Page 17: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/17.jpg)
NOT – Negazione • L’operatore (o funzione) NOT, inverte il valore dell’operando su cui opera
•Doppia negazione:
• L’elemento ҧ𝑥 viene detto complemento di x
𝑥1 𝐹 𝑥1 = 𝑥10 1
1 0
Algebra di Boole
![Page 18: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/18.jpg)
NOT – NegazionePossibili Rappresentazioni• y = ~x
• y = !x
• y = not x
• y = x’
• y = ¬𝒙
• y = ഥ𝒙
Algebra di Boole
![Page 19: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/19.jpg)
NOT – NegazionePossibili Rappresentazioni• y = ~x
• y = !x
• y = not x
• y = x’
• y = ¬𝑥
• y = ഥ𝒙
Algebra di Boole
![Page 20: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/20.jpg)
Algebra di Boole: Alcune Identità
Funzione AND Funzione OR Funzione NOT
0 × 0 = 0 0 + 0 = 0 x+ ҧ𝑥 = 1
0 × 1 = 0 0 + 1 = 1 x × ҧ𝑥 = 0
1 × 0 = 0 1 + 0 = 1 Ӗ𝑥 = 𝑥
1 × 1 = 1 1 + 1 = 1
x × 0 = 0 x + 0 = x
0 × x = 0 0 + x = x
x × 1 = x x + 1 = 1
1 × x = x 1 + x = 1
x × x = x x + x = x
Algebra di Boole
![Page 21: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/21.jpg)
Algebra di Boole: Alcune Identità
Funzione AND Funzione OR Funzione NOT
0 × 0 = 0 0 + 0 = 0 x+ ҧ𝑥 = 1
0 × 1 = 0 0 + 1 = 1 x × ҧ𝑥 = 0
1 × 0 = 0 1 + 0 = 1 Ӗ𝑥 = 𝑥
1 × 1 = 1 1 + 1 = 1
x × 0 = 0 x + 0 = x
0 × x = 0 0 + x = x
x × 1 = x x + 1 = 1
1 × x = x 1 + x = 1
x × x = x x + x = x
Prodotto Logico
Algebra di Boole
![Page 22: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/22.jpg)
Algebra di Boole: Alcune Identità
Funzione AND Funzione OR Funzione NOT
0 × 0 = 0 0 + 0 = 0 x+ ҧ𝑥 = 1
0 × 1 = 0 0 + 1 = 1 x × ҧ𝑥 = 0
1 × 0 = 0 1 + 0 = 1 Ӗ𝑥 = 𝑥
1 × 1 = 1 1 + 1 = 1
x × 0 = 0 x + 0 = x
0 × x = 0 0 + x = x
x × 1 = x x + 1 = 1
1 × x = x 1 + x = 1
x × x = x x + x = x
Somma Logica
NOTA: 1+1=1
Algebra di Boole
![Page 23: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/23.jpg)
Algebra di Boole: Alcune Identità
Funzione AND Funzione OR Funzione NOT
0 × 0 = 0 0 + 0 = 0 x+ ҧ𝑥 = 1
0 × 1 = 0 0 + 1 = 1 x × ҧ𝑥 = 0
1 × 0 = 0 1 + 0 = 1 Ӗ𝑥 = 𝑥
1 × 1 = 1 1 + 1 = 1
x × 0 = 0 x + 0 = x
0 × x = 0 0 + x = x
x × 1 = x x + 1 = 1
1 × x = x 1 + x = 1
x × x = x x + x = x
Legge dell’idempotenza
Algebra di Boole
![Page 24: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/24.jpg)
Algebra di Boole: Proprietà e Leggi
Proprietà Commutativa Leggi di Assorbimento
Proprietà Distributiva Leggi di De Morgan
Proprietà Associativa Altre Note
𝑥1𝑥2 = 𝑥2𝑥1𝑥1+ 𝑥2 = 𝑥2+ 𝑥1
𝑥1+ 𝑥1𝑥2 = 𝑥1𝑥1(𝑥1+ 𝑥2) = 𝑥1
𝑥1 𝑥2+ 𝑥3 = 𝑥1𝑥2+ 𝑥2𝑥3𝑥1+ 𝑥2𝑥3 = 𝑥1+ 𝑥2 + (𝑥1+ 𝑥3)
𝑥1 𝑥2𝑥3 = (𝑥1𝑥2)𝑥3𝑥1+ 𝑥2+ 𝑥3 = 𝑥1+ 𝑥2 + 𝑥3
𝑥1+ 𝑥2 = ഥ𝑥1 × ഥ𝑥2𝑥1 × 𝑥2 = ഥ𝑥1+ ഥ𝑥2
𝑥1+ ഥ𝑥1𝑥2 = 𝑥1+ 𝑥2𝑥1( ഥ𝑥1+ 𝑥2) = 𝑥1𝑥2
Algebra di Boole
![Page 25: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/25.jpg)
Leggi di De Morgan
Leggi di De Morgan – 1/2
𝑥1+ 𝑥2 = ഥ𝑥1 × ഥ𝑥2𝑥1 × 𝑥2 = ഥ𝑥1+ ഥ𝑥2
Algebra di Boole
![Page 26: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/26.jpg)
Leggi di De Morgan
Leggi di De Morgan – 1/2
𝑥1+ 𝑥2 = ഥ𝑥1 × ഥ𝑥2𝑥1 × 𝑥2 = ഥ𝑥1+ ഥ𝑥2
• Il complemento di due o più variabili poste in OR è uguale all’AND dei complementi delle singole variabili
Algebra di Boole
![Page 27: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/27.jpg)
Leggi di De Morgan
Leggi di De Morgan – 2/2
𝑥1+ 𝑥2 = ഥ𝑥1 × ഥ𝑥2𝑥1 × 𝑥2 = ഥ𝑥1+ ഥ𝑥2
• Il complemento di due o più variabili poste in AND è equivalente all’OR dei complementi delle singole variabili
Algebra di Boole
![Page 28: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/28.jpg)
Osservazioni• Dalle leggi di De Morgan si evince che la sceltadelle funzioni OR, AND e NOT, come operatoriprimitivi, è ridondante• L’operazione logica AND può essere espressa in funzione
delle operazioni OR e NOT
• In modo analogo, l’operazione OR può essere espressatramite AND e NOT
Algebra di Boole
![Page 29: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/29.jpg)
Funzioni Logiche (o Booleane) – 1/5• Date n variabili booleane indipendenti: x1, x2,…, xn,queste possono assumere 2n configurazioni distinte• Ad esempio per n = 4 si hanno 16 (24) configurazioni
• Esempio di configurazione su n = 4
• 𝑥1 = 1, 𝑥2 = 0, 𝑥3 = 0, 𝑥4 = 1
• Ogni riga mostra (in rosso) il valore restituito da F apartire da una particolare configurazione dell’input
x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Algebra di Boole
![Page 30: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/30.jpg)
Funzioni Logiche (o Booleane) – 2/5• 010 indica la configurazione in cui
• 𝒙𝟏 = 0• 𝒙𝟐 = 1• 𝒙𝟑 = 0
• Questa configurazione si scrive semplicemente con ilprodotto logico
• 𝒙𝟏𝒙𝟐𝒙𝟑
x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Algebra di Boole
![Page 31: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/31.jpg)
Funzioni Logiche (o Booleane) – 2/5• 010 indica la configurazione in cui
• 𝒙𝟏 = 0• 𝒙𝟐 = 1• 𝒙𝟑 = 0
• Questa configurazione si scrive semplicemente con ilprodotto logico
• 𝒙𝟏𝒙𝟐𝒙𝟑
• Una configurazione specifica è individuataunivocamente da un AND (prodotto logico) di tutte levariabili, dove quelle corrispondenti ai valori 0compaiono negate
• Prodotto fondamentale o prodotto minimo
• minterm
x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
x1x2x3010
Algebra di Boole
![Page 32: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/32.jpg)
Funzioni Logiche (o Booleane) – 2/5
ഥ𝑥1 ഥ𝑥2 ഥ𝑥3
ഥ𝑥1 ഥ𝑥2 𝑥3
ഥ𝑥1 𝑥2 ഥ𝑥3
ഥ𝑥1 𝑥2𝑥3
𝑥1 ഥ𝑥2 ഥ𝑥3
𝑥1 ഥ𝑥2 𝑥3
𝑥1 𝑥2 ഥ𝑥3
𝑥1 𝑥2𝑥3
Configurazioni x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Tutte le configurazioni della tavola di verità dell’esempio
Algebra di Boole
![Page 33: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/33.jpg)
Funzioni Logiche (o Booleane) – 3/5• Una variabile y è una funzione booleana delle n variabili indipendentix1, x2,…, xn, se esiste un criterio che fa corrispondere in modo univocoad ognuna delle 2n configurazioni delle variabili xi un valore di y (chepotrà essere 0 oppure 1)
• Una funzione può essere rappresentata in maniera esplicita tramite latabella (o tavola) di verità, in cui si elencano tutte le possibilicombinazioni di x1, x2, …, xn, con associato il valore di y
y = F(x1, x2, …, xn)
y = x1+ x2
𝑥1 𝑥2 𝑦
0 0 0
0 1 1
1 0 1
1 1 1
Algebra di Boole
![Page 34: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/34.jpg)
Funzioni Logiche (o Booleane) – 3/5– Tavola di verità –
• Modo sistematico per specificare il valore di una funzione per tutte le possibili combinazioni di valori di input• Una funzione che prende 2 input ha 4 = 22 righe
• Una funzione che prende n input ha 2n righe
• Esempio (2 variabili: x e y 4 righe):
x 𝑦 𝐹𝑢𝑛𝑧𝑖𝑜𝑛𝑒 𝐹
0 0 1
0 1 0
1 0 0
1 1 1
Algebra di Boole
![Page 35: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/35.jpg)
Funzioni Logiche (o Booleane) – 4/5• Oltre che con la tavola di verità, ogni funzione booleana può esseredeterminata tramite la sua espressione booleana
• Per passare dalla rappresentazione mediantetavola di verità alla notazione tramiteespressione booleana è necessario:
1. Identificare tutte le righe della tavola di veritàche danno 1 in output
2. Per ogni riga con un 1 in output, scrivere ilminterm della configurazione delle variabiliche la definiscono
3. Collegare tramite OR tutti i minterm ottenuti
x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Algebra di Boole
![Page 36: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/36.jpg)
Funzioni Logiche (o Booleane) – 4/5• Oltre che con la tavola di verità, ogni funzione booleana può esseredeterminata tramite la sua espressione booleana
• Per passare dalla rappresentazione mediantetavola di verità alla notazione tramiteespressione booleana è necessario:
1. Identificare tutte le righe della tavola di veritàche danno 1 in output
2. Per ogni riga con un 1 in output, scrivere ilminterm della configurazione delle variabiliche la definiscono
3. Collegare tramite OR tutti i minterm ottenuti
x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Algebra di Boole
![Page 37: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/37.jpg)
x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Funzioni Logiche (o Booleane) – 4/5• Oltre che con la tavola di verità, ogni funzione booleana può esseredeterminata tramite la sua espressione booleana
• Per passare dalla rappresentazione mediantetavola di verità alla notazione tramiteespressione booleana è necessario:
1. Identificare tutte le righe della tavola di veritàche danno 1 in output
2. Per ogni riga con un 1 in output, scrivere ilminterm della configurazione delle variabiliche la definiscono
3. Collegare tramite OR tutti i minterm ottenuti
Algebra di Boole
![Page 38: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/38.jpg)
x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Funzioni Logiche (o Booleane) – 4/5• Oltre che con la tavola di verità, ogni funzione booleana può esseredeterminata tramite la sua espressione booleana
• Per passare dalla rappresentazione mediantetavola di verità alla notazione tramiteespressione booleana è necessario:
1. Identificare tutte le righe della tavola di veritàche danno 1 in output
2. Per ogni riga con un 1 in output, scrivere ilminterm della configurazione delle variabiliche la definiscono
3. Collegare tramite OR tutti i minterm ottenuti
Algebra di Boole
![Page 39: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/39.jpg)
x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Funzioni Logiche (o Booleane) – 4/5• Oltre che con la tavola di verità, ogni funzione booleana può esseredeterminata tramite la sua espressione booleana
• Per passare dalla rappresentazione mediantetavola di verità alla notazione tramiteespressione booleana è necessario:
1. Identificare tutte le righe della tavola di veritàche danno 1 in output
2. Per ogni riga con un 1 in output, scrivere ilminterm della configurazione delle variabiliche la definiscono
3. Collegare tramite OR tutti i minterm ottenuti
ഥ𝑥1 𝑥2𝑥3
Algebra di Boole
![Page 40: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/40.jpg)
x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Funzioni Logiche (o Booleane) – 4/5• Oltre che con la tavola di verità, ogni funzione booleana può esseredeterminata tramite la sua espressione booleana
• Per passare dalla rappresentazione mediantetavola di verità alla notazione tramiteespressione booleana è necessario:
1. Identificare tutte le righe della tavola di veritàche danno 1 in output
2. Per ogni riga con un 1 in output, scrivere ilminterm della configurazione delle variabiliche la definiscono
3. Collegare tramite OR tutti i minterm ottenuti
ഥ𝑥1 𝑥2𝑥3 𝑥1 ഥ𝑥2 𝑥3
Algebra di Boole
![Page 41: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/41.jpg)
x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Funzioni Logiche (o Booleane) – 4/5• Oltre che con la tavola di verità, ogni funzione booleana può esseredeterminata tramite la sua espressione booleana
• Per passare dalla rappresentazione mediantetavola di verità alla notazione tramiteespressione booleana è necessario:
1. Identificare tutte le righe della tavola di veritàche danno 1 in output
2. Per ogni riga con un 1 in output, scrivere ilminterm della configurazione delle variabiliche la definiscono
3. Collegare tramite OR tutti i minterm ottenuti
ഥ𝑥1 𝑥2𝑥3 𝑥1 ഥ𝑥2 𝑥3 𝑥1 𝑥2 ഥ𝑥3 𝑥1 𝑥2𝑥3
Algebra di Boole
![Page 42: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/42.jpg)
x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Funzioni Logiche (o Booleane) – 4/5• Oltre che con la tavola di verità, ogni funzione booleana può esseredeterminata tramite la sua espressione booleana
• Per passare dalla rappresentazione mediantetavola di verità alla notazione tramiteespressione booleana è necessario:
1. Identificare tutte le righe della tavola di veritàche danno 1 in output
2. Per ogni riga con un 1 in output, scrivere ilminterm della configurazione delle variabiliche la definiscono
3. Collegare tramite OR tutti i minterm ottenuti
ഥ𝑥1 𝑥2𝑥3 𝑥1 ഥ𝑥2 𝑥3 𝑥1 𝑥2 ഥ𝑥3 𝑥1 𝑥2𝑥3
Algebra di Boole
![Page 43: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/43.jpg)
x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Funzioni Logiche (o Booleane) – 4/5• Oltre che con la tavola di verità, ogni funzione booleana può esseredeterminata tramite la sua espressione booleana
• Per passare dalla rappresentazione mediantetavola di verità alla notazione tramiteespressione booleana è necessario:
1. Identificare tutte le righe della tavola di veritàche danno 1 in output
2. Per ogni riga con un 1 in output, scrivere ilminterm della configurazione delle variabiliche la definiscono
3. Collegare tramite OR tutti i minterm ottenuti
ഥ𝑥1 𝑥2𝑥3+ 𝑥1 ഥ𝑥2 𝑥3+ 𝑥1 𝑥2 ഥ𝑥3+𝑥1 𝑥2𝑥3
Algebra di Boole
![Page 44: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/44.jpg)
Funzioni Logiche (o Booleane) – 5/5• 𝐹 𝑥1, 𝑥2, 𝑥3 = ഥ𝑥1 𝑥2𝑥3+ 𝑥1 ഥ𝑥2 𝑥3+ 𝑥1 𝑥2 ഥ𝑥3+ 𝑥1 𝑥2𝑥3
• Con l’uso dei minterm possiamo determinarel’espressione booleana di una funzionebooleana a partire dalla tavola di verità
• L’espressione booleana trovata si chiamaforma canonica della funzione e si ottiene conuno sviluppo in minterm• Una somma (OR) di prodotti (AND)
• Se un minterm assume valore 1 anche lafunzione F assume il valore 1
• Tutte le funzioni logiche possono essereriportate in forma canonica
x1 x2 x3 F(x1, x2, x3)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Algebra di Boole
![Page 45: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/45.jpg)
Esempio (dalla tavola di verità alla funzione):
Funzione Exclusive OR (XOR) • Il comportamento della funzione Exclusive OR (XOR) su due variabili indipendenti può essere descritto con la seguente tavola di verità
• Sostanzialmente la funzione XOR verifica la disuguaglianza di due variabili• Restituisce 1 sse 𝑥1 e 𝑥2 sono diversi
• Restituisce 0 sse 𝑥1 e 𝑥2 sono uguali
𝑥1 𝑥2 𝑋𝑂𝑅
0 0 0
0 1 1
1 0 1
1 1 0
Algebra di Boole
![Page 46: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/46.jpg)
Dalla Funzione alla Tavola di Verità• Vediamo un esempio per la funzione • 𝐹 = 𝑥 × (𝑦 + 𝑧)
x y z F
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0
Algebra di Boole
![Page 47: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/47.jpg)
Esercizio per Casa: Dalla Tavola di Verità all’Espressione Booleana
Tavola di Verità della funzione X
A B C X
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
X = ______________________________
Algebra di Boole
![Page 48: Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si studia l’algebrabooleana poiché le sue funzioni sono isomorfe ai circuiti digitali:](https://reader033.vdocumenti.com/reader033/viewer/2022052611/5f08afb97e708231d4233af7/html5/thumbnails/48.jpg)
Riferimenti• Libro di testo• Capitolo 3
• Paragrafo 4
Algebra di Boole