Download Álgebra de Conmutación

Á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