Le Reti Logiche

Reti Logiche Reti Logiche Corso di Architetture degli Elaboratori Struttura del corso Struttura del corso Introduzione alle reti logiche Implementazione di porte logiche Sintesi di reti combinatorie Reti sequenziali Sintesi di reti sequenziali RETI LOGICHE 2 Algebra booleana Algebra booleana Insieme S = a,b,c. Operatori binari + e è un'algebra booleana se valgono le proprietà: a,b S: a+bS, abS 0,1 S: a S a+0=a, a1=a a+b=b+a, ab=ba (a+bc=ab+c), (ab)c=a(bc) a+bca+ba+c), a(b+cabac) aS ( a) S aa1, a(a0 n0: S=2n RETI LOGICHE chiusura elementi neutri commutatività associatività distributività inverso dimensione 3 Proprietà derivate di un'algebra booleana Proprietà derivate di un'algebra booleana Gli elementi 0,1 sono unici a+a =a, aa = a a+1=1, a0 = 0 a+ab = a, a(a+ba aa)b = a+b, aabab Per ogni a S, l'elemento a è unico (a+b) = (ab), (ab) = (ab) (a) = a idempotenza assorbimento De Morgan involuzione RETI LOGICHE 4 Esempio di algebra booleana 1 Esempio di algebra booleana Dato un insieme I, indichiamo con P(I) l'insieme di tutti i sottoinsiemi di I (insieme potenza), allora è un'algebra booleana, con: S = P(I) += = a = I/a 0= 1=I RETI LOGICHE 5 Esempio di algebra booleana 2 Infatti: S1, S2 I, S1 S2 I, S1 S2 I S1 I, S1 =S1, S1 I =S1 S1 S2 = S2 S1 S1 S2 = S2 S1 (S1 S2) S3 = S1 (S2 S3) (S1 S2) S3 = S1 (S2 S3) S1 (S2 S3S1 S2) (S1 S3) S1 (S2 S3S1 S2) (S1 S3) S1 (I/S1I, S1 (I/S1)= P(I2I RETI LOGICHE 6 Variabili e funzioni di commutazione 1 Variabili e funzioni di commutazione Una variabile di commutazione (o booleana) x è una variabile che assume valori nel dominio 0,1 (o T,F). Una funzione di commutazione (o funzione booleana) f : 0,1n 0,1 su n variabili di commutazione è una qualunque corrispondenza (mapping) y = f (x1, x2, xn) da 0,1n a 0,1. Una funzione di commutazione n-aria è definita su un dominio di 2n valori diversi, detti anche assegnamenti di verità. RETI LOGICHE 7 Variabili e funzioni di commutazione 2 Esempio: Una funzione di commutazione 3-aria y = f (x1, x2, x3) è definita sull'insieme di 23=8 assegnamenti di verità: x1=0, x2=0, x3=0 x1=0, x2=0, x3=1 x1=0, x2=1, x3=0 x1=0, x2=1, x3=1 x1=1, x2=0, x3=0 x1=1, x2=0, x3=1 x1=1, x2=1, x3=0 x1=1, x2=1, x3=1 o, più sinteticamente, sui valori 000, 001, 010, 011, 100, 101, 110, 111, ed associa ad ognuno di essi un valore 0 o 1 RETI LOGICHE 8 Tabelle di verità 1 Tabelle di verità Una funzione di commutazione può essere rappresentata utilizzando una tabella di verità. n variabili funzione 2n assegnazioni di verità RETI LOGICHE 9 Tabelle di verità 2 Esempio di funzione di commutazione 3-aria Possiamo definire una particolare funzione di commutazione 3-aria utilizzando una matrice 8x4. x3 0 0 0 0 1 1 1 1 x2 0 0 1 1 0 0 1 1 x1 0 1 0 1 0 1 0 1 y 0 0 1 0 1 1 0 1 Nota: esistono diverse funzioni di commutazione n-arie 22 n RETI LOGICHE 10 Funzioni di commutazione elementari 1 Funzioni di commutazione elementari Funzioni 1-arie x 0 1 y1 0 1 y2 1 0 y3 0 0 y4 1 1 y1 : identità y2 : negazione (NOT) RETI LOGICHE 11 Fu Continua »