Algebra di Boole e reti combinatorie · OR ovvero la somma OR(x,y) con x, y variabili che possono...
Transcript of Algebra di Boole e reti combinatorie · OR ovvero la somma OR(x,y) con x, y variabili che possono...
Algebra di Boole e reti logiche
Giovedì 8 ottobre 2015
Punto della situazione
• Abbiamo visto le varie rappresentazioni dei numeri in binario e in altre basi e la loro aritmetica
• Adesso vedremo la logica digitale usata dal calcolatore nell’ottica di
• Costruire l’ALU, Unità Logica Aritmetica, e altri moduli combinatorici
• L’ALU è usata da quasi tutti i tipi di istruzioni dell’architettura che studieremo
AND ovvero il prodottoAND(x,y) con x, y variabili che possono assumere valore Vero o Falso.
Risultato Vero se entrambe le variabili sono poste a Vero, Falso, altrimenti.
Interpretando Vero come 1 e Falso come 0
AND(x,y) corrisponde al prodotto x y.
AND(F,F) = FAND(F,V) = FAND(V,F) = FAND(V,V) = V
0 0 = 00 1 = 01 0 = 01 1 = 1
x y x y 0 0 00 1 01 0 01 1 1
Tavola di verità
OR ovvero la sommaOR(x,y) con x, y variabili che possono assumere valore Vero o Falso.
Risultato Vero se almeno una variabile è posta a Vero, Falso, altrimenti.
Interpretando Vero come 1 e Falso come 0
OR(x,y) corrisponde alla somma x + y, in cui 1+1 = 1.
OR(F,F) = FOR(F,V) = VOR(V,F) = VOR(V,V) = V
0 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 1
x y x + y 0 0 00 1 11 0 11 1 1
Tavola di verità
NOT ovvero la negazioneNOT(x) con x variabile che può assumere valore Vero o Falso.
Risultato Vero se la variabile è posta a Falso;
Falso, altrimenti.
Interpretando Vero come 1 e Falso come 0
NOT(x) corrisponde alla negazione.
NOT(V) = FNOT(F) = V
0 = 11 = 0
x x 0 11 0
XOR o OR esclusivoXOR(x,y) con x, y variabili che possono assumere valore Vero o Falso.
Risultato Vero se una variabile è posta a Vero, ma non entrambe,
Falso, altrimenti.
Interpretando Vero come 1 e Falso come 0
XOR(x,y) corrisponde a x y + x y = x y
XOR(F,F) = FXOR(F,V) = VXOR(V,F) = VXOR(V,V) = F
0 0 = 00 1 = 11 0 = 11 1 = 0
x y x y 0 0 00 1 11 0 11 1 0
f1(0,1)=0, f1(1,1) = 1f2(0,1,0)= 11 + 0 + 0 = 1 f3(0,0,0)= 1 + 0(0 + 1) = 1
La combinazione delle variabili e degli operatori viene chiamata espressione logica.
Mappa di verità o tavola di verità: tabella che definisce i valori dell’output per ogni possibile input
Espressione SOPLetterale = variabile o la sua negazione
• Un’espressione booleana è in forma normale SOP (Sum Of Products) quando è l’OR/somma di AND/prodotto di letterali
• Mintermine = prodotto di letterali in cui compare ognivariabile o vera o negata
• Una espressione normale SOP è in forma canonica SOP se i suoi termini sono tutti mintermini
Scambiando Somma con Prodotto si definiscono le espressioni POS
3131321 xxxxxxx
321321321 xxxxxxxxx
Espressione POSLetterale = variabile o la sua negazione
• Un’espressione booleana è in forma normale POS (Product Of Sums ) quando è il prodotto (AND) di somme (OR) di letterali
• Maxtermine = somma di letterali in cui compare ognivariabile o vera o negata
• Una espressione normale POS è in forma canonica POS se i suoi termini sono tutti maxtermini
))(( 3132 xxxx
))(( 321321 xxxxxx
Circuito per l’ AND
Circuito per l’ OR
Circuito per lo XOR
Rete logica
Una rete logica è un’interconnessione di porte logiche AND, OR, NOT, in modo che ogni uscita da una porta alimenti al più un ingresso di una porta e non vi sono cicli
Valori in uscitax1= 0, x2= 0, x3= 1
Analisi di una rete: dalla rete alla funzione
• Ogni rete logica calcola una funzione booleana dei suoi ingressi
f(x1,x2,x3) = x3 ( x1 . x2) + (x1+x3)
Risultato principale
Corrispondenza fra funzioni logiche e reti logiche:
Analisi: data una rete determinare la funzione calcolata
Sintesi: data una funzione logica costruire una rete che la calcola
• Per ogni funzione logica possiamo costruire una rete logica che la realizza e viceversa
• Ogni funzione logica può essere espressa in termini soltanto di AND, OR, NOT.
Analisi e Sintesi di reti
• Analisi è abbastanza semplice:– Calcola per ogni porta logica di cui sono specificati
tutti gli input l’espressione booleana associataall’output• Fino ad ottenere l’espressione associata al terminale d’uscita
della rete
• Vediamo ora la sintesi di una funzione logica f:1. Da f alla tavola di verità2. Dalla tavola di verità all’espressione «SOP»3. Dall’espressione «SOP» ad una rete a due stadi: il primo di
porte AND, il secondo con una sola porta OR
Tavole di verità di minterminiPer ogni mintermine, la tavola di verità ha un solo valore 1.
Per esempio:
se f = x3 x2 x1 allora avrà un solo 1 in corrispondenza di x3=0, x2=1, x1=1.
• Ricorda:
• Il prodotto è 1 sse ogni fattore è 1x3 x2 x1 f
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 0
Viceversa, se la tavola di verità di f ha un solo valore 1 necessariamente f è un mintermine.
f = x3 x2 x1
Dalla tavola di verità alla SOP
Se invece la tavola di verità ha più occorrenze di 1:
f ha valore 1 se:
x3=0, x2=1, x1=1 oppure
x3=1, x2=0, x1=1
x3 x2 x1 f
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 0
1 1 1 0
x3 x2 x1
x3 x2 x1
f = x3 x2 x1 + x3 x2 x1
Espressione canonica SOP
1. Per ogni 1 nella tavola di verità trovare il mintermine corrispondente
2. Sommare i mintermini ottenuti
Quindi abbiamo che:
• Per ogni funzione logica possiamo costruire una rete logica che la realizza (e viceversa)
• Ogni funzione logica può essere espressa in termini soltanto di AND OR NOT.
Sintesi di una rete: dalla funzione alla rete
Dalla tavola di verità alla SOP: esempio 1Supponiamo di avere una funzione f data tramite la sua tavola di verità
Espressione SOP
Dalla tavola di verità alla SOP: esempio 2
Dalla tavola di verità all’espressioneSOP
Espressione SOP
Dall’espressioneSOP alla rete a due livelli: un livello varie porte AND, un secondo livello solo una porta OR
• Lo vedremo nelle prossime lezioni
Riferimenti
Appendice B di [PH] «The Basic of Logic Design»: Gates, Truth tables, and Logic Equations: B.1, B.2
Nella III edizione è l’Appendice C
Oppure [P] cap. 3, parr. 4.1, 4.2
Esercizio (maggioranza)
Sia f(x,y,z) la funzione che vale 1 se (e solo se) la maggioranza delle variabili vale 1.
Effettuare la sintesi di f:1. Da f alla tavola di verità2. Dalla tavola di verità all’espressione SOP3. Dall’espressione SOP ad una rete a due stadi: il
primo di porte AND, il secondo con una sola porta OR
Esercizi
• Disegnare una rete logica che realizza lo XOR fra due variabili
• L’operazione di NAND di 2 variabili è la negazione dell’AND, mentre quella di NOR è la negazione dell’OR.