Download Álgebra de Conmutación
Document related concepts
no text concepts found
Transcript
Álgebra de Conmutación Circuitos Digitales I ! Es un álgebra definida en un campo numérico de dos elementos: 0 y 1 (campo finito binario), que sirve para analizar y describir el comportamiento de sistemas lógicos binarios. ! También se conoce como Álgebra de Boole ! Convención de lógica positiva. Tema II Álgebra de Conmutación – Valores de voltaje analógicos, BAJO (L)=0, ALTO (H)=1. ! Convención de lógica negativa - Usada muy rara vez. ! Valores de las señales denotados por variables: (X, Y, ALARMA, JUAN, MEM_WR, etc) Luis Tarazona, UNEXPO Barquisimeto EL-3213 – Circuitos Digitales I - 2004 62 Luis Tarazona, UNEXPO Barquisimeto Operadores Booleanos EL-3213 – Circuitos Digitales I - 2004 63 Axiomas del álgrebra de Boole ! Complemento: X′ (el opuesto de X) Operadores binarios, descritos ! AND: X⋅Y funcionalmente por una tabla de ! OR: X+Y verdad (A1) (A2) (A3) (A4) (A5) X=0 si X≠ ≠1 si X=0, luego X’=1 0·0=0 1·1=1 0·1=1·0=0 (A1’) (A2’) (A3’) (A4’) (A5’) X=1 si X≠ ≠0 si X=1, luego X’ = 0 1+1=1 0+0=0 1+0=0+1=1 ! Definición axiomática: axiomas A1-A5, A1′-A5′ Luis Tarazona, UNEXPO Barquisimeto EL-3213 – Circuitos Digitales I - 2004 64 Luis Tarazona, UNEXPO Barquisimeto EL-3213 – Circuitos Digitales I - 2004 65 Símbolos Lógicos Definiciones ! Literal: una variable o su complemento X, X′, JUAN′, CS_L ! Expresión: literales combinados mediante AND, OR, paréntesis, complementación X+Y P⋅Q⋅R A+B⋅C ((JUAN ⋅ Z′) + CS_L ⋅ A ⋅ B′ ⋅ C + Q5) ⋅ RESET′ ! Ecuación: Variable = expresión P = ((JUAN ⋅ Z′) + CS_L ⋅ A ⋅ B′ ⋅ C + Q5) ⋅ RESET′ Luis Tarazona, UNEXPO Barquisimeto EL-3213 – Circuitos Digitales I - 2004 66 Luis Tarazona, UNEXPO Barquisimeto Teoremas (T1) (T2) (T3) (T4) (T5) X+0=X X+1=1 X+X=X (X’)’ = X X + X’= 1 67 Más Teoremas (T1’) X ⋅ 1 = X (Identidades) (T2’) X ⋅ 0 = 0 (Elementos nulos) (T3’) X ⋅ X = X (Idempotencia) (Involución) (T5’) X ⋅ X’= 0 (Complementos) EL-3213 – Circuitos Digitales I - 2004 (T6) X + Y = Y + X (T6’) X ⋅ Y = Y ⋅ X (Conmutatividad) (T7) (X + Y) + Z = X + (Y + Z) (T7’) (X ⋅ Y) ⋅ Z = X ⋅ (Y ⋅ Z) (Asociatividad) (T8) X · Y + X · Z = X · (Y + Z) (T8’) (X + Y)⋅( X + Z) = X + Y ⋅ Z (Distributividad) (T9) X + X· Y = X (T9’) X ⋅ (X + Y) = X (Cobertura) (T10) X· Y + X· Y’ = X (T10’) (X + Y) ⋅ ( X + Y’) = X (Combinación) (T11) X· Y + X’· Z + Y· Z = X· Y + X’· Z (Consenso) (T11’) (X + Y) ⋅ ( X’ + Z) (Y + Z) = ( X + Y) (X’ + Z) ! Atención T8, T10, T11 ! Se prueban por Inducción Perfecta ! Probarlos! Luis Tarazona, UNEXPO Barquisimeto EL-3213 – Circuitos Digitales I - 2004 68 Luis Tarazona, UNEXPO Barquisimeto EL-3213 – Circuitos Digitales I - 2004 69 Dualidad Teoremas de n variables (T12) X + X + X + . . . + X = X (Idempotencia generalizado) (T12’) X ⋅ X ⋅ X ⋅ . . . ⋅ X = X (Teoremas de DeMorgan) (T13) (X1 + X2 + . . . + Xn)’ = X1’ · X2’ · . . . · Xn’ (T13’) (X1 · X2 · . . . · Xn)’ = X1’ + X2’+ . . . + Xn’ (T14) [F(X1, X2, ... , Xn ,+ , · )]’ = F(X1’ , X2’, ... , Xn’, · , +) (T. de DeMorgan generalizado) Teoremas de expansión de Shannon: (T15) F(X1, X2, ... , Xn ) = X1 · F (1, X2, ... , Xn ) + X1’ · F (0, X2, ... , Xn ) (T15’) F(X1, X2, ... , Xn ) = [X1 + F (0, X2, ... , Xn )] · [ X1’ + F (1, X2, ... , Xn )] ! Intercambiar 0 y 1, AND y OR – Resultado: Los teoremas aún son verdaderos ! ¿Porqué? – Cada axioma (A1-A5) tiene un dual (A1′-A5′) ! Contraejemplo: X + X ⋅ Y = X (T9) X ⋅ X + Y = X (dual) X + Y = X (T3′) ???????????? Luis Tarazona, UNEXPO Barquisimeto X + (X ⋅ Y) = X (T9) X ⋅ (X + Y) = X (dual) (X ⋅ X) + (X ⋅ Y) = X (T8) X + (X ⋅ Y) = X (T3′) ! Probar usando usando inducción finita ! Los más importantes: Teoremas de DeMorgan paréntesis, precedencia de operadores! EL-3213 – Circuitos Digitales I - 2004 70 EL-3213 – Circuitos Digitales I - 2004 EL-3213 – Circuitos Digitales I - 2004 71 Similar para OR Equivalencia de Símbolos por DeMorgan Luis Tarazona, UNEXPO Barquisimeto Luis Tarazona, UNEXPO Barquisimeto 72 Luis Tarazona, UNEXPO Barquisimeto EL-3213 – Circuitos Digitales I - 2004 73 Símbolos y equiv. DeMorgan Luis Tarazona, UNEXPO Barquisimeto EL-3213 – Circuitos Digitales I - 2004 74