– Para a ?K: a) a + a = 1 b) a . a = 0
V.1 Principio de Dualidad
Establece que si una expresión es válida en el álgebra de boole, entonces su expresión dual también lo es.
Determinamos la expresión dual remplazando los operadores + por · y viceversa y todos los elementos 0 por 1 y viceversa.
Ejemplo:
a + (b · c) = 1, expresión su dual es a · (b + c) = 0
V.2 Teoremas
Teorema 1: Idempotencia: Tanto la suma como el producto de una variable booleana consigo misma da como resultado la misma variable.
a) a + a = a
b) a · a = a ?
? Demostración:
a+a=
(a + a) · 1 =
(a + a) · (a + a) =
a + a · a =
a+0=a
Teorema 2: Elemento neutro para + y · a) a + 1 = 1 b) a · 0 = 0
? Demostración: a+1= (a + 1) · 1 = 1 · (a + 1) = (a + a) · (a + 1) = a + a · 1 = a + a = 1
Teorema 3: Involución: Una variable booleana negada dos veces, da como resultado la misma variable: ?
a = a
? Demostración: a+1= a · 1 + 0 = a · (a + a) + a · a = a · a + a · a + a · a = a · (a + a) = a
? Teorema 4 : Absorción
a) a + a · b = a
b) a · (a + b) = a
? Demostración:
a+a·b=
a·1+a·b=
a · (1 + b) =
a·1=a ? Teorema 5: a) a + a · b = a + b
b) a · ( a + b) = a · b
? ? Demostración :
a + a · b =
(a + a) · (a + b) =
1 · (a + b) =
(a + b) · 1 = a + b
? Teorema 7: a) a · b + a · b · c = a · b + a · c
b) (a + b) · (a + b + c) = (a + b) ·(a + c)
? Demostración:
a·b+a·b·c=
a · (b + b · c) =
a · (b + c) = a · b + a · c
? ? Teorema 8: Teorema de Morgan: a) a + b = a · b b) a · b = a + b
? En general:
a + b + … + z = a · b · c · … · z a · b · c · … · z = a + b + c + … + z
Demostración del Teorema de Morgan x+y= (a + b) + a · b = (b + a) + a · b = b + (a + a .b) = b + (a + b) = (a + b) + b = a + (b + b) = a+l=l entonces : x+y=1 resulta : x = y => a + b = a + b x·y= (a + b) · (a · b) = (a · b) · (a + b) = (a · b) · a + (a · b) · b = a · ( a · b) + b · (a · b ) = (a · a) · b + a · (b · b) = 0 · b + a · 0 = b · 0 + a · 0 = 0+0=0 entonces: x·y=0 ? Teorema 6 : a) a · b + a · b = a
b) (a + b) · (a + b) = a
? Demostración:
a·b+a·b=
a · (b + b) =
a·1=a
x = a + b => x = a + b sabemos: x·x=o x+x=l asumimos : x·y=O x+y=l entonces: y=x asumimos : y = a · b
? Teorema 9: Consenso a) a · b + a · c + b · c = a · b + a · c b) (a + b) · (a + c) · (b + c) = (a + b) · (a + c)
? Demostración:
a · b + a · c + b · c = a · b + a · c + 1 · b · c = a · b + a · c + (a + a) · b · c = a · b + a · c + a · b · c + a · b · c = a · b + a · c VI Funciones de Conmutación
Sean x1, x2, … , xn símbolos llamados variables, cada uno representa un 0 o un 1, definiremos f(x1, x2, … , xn) como una función de conmutación de x1, x2, … , xn f puede tomar el valor de 0 ó 1 según los valores para x1, x2, … , xn; si existen n variables (xi), entonces existe 2n formas de asignar los valores para x1, x2, … , xn y como f tiene dos posibles valores, existen 22n diferentes funciones para n variables.
Ejemplos:
? n=0 f()=0,1 ? n=1 f(x)=0 1,x,x
? n=2 f(x,y)= 0 , x.y , x.y , x x.y , x.y , x, y , x.y+x.y, x+y , x.y+x.y, y, x+y, x+y x+y 1 Representación de una función de Conmutación
? Tabla de Verdad: Evaluamos todos los posibles valores de entrada de la función y los colocamos en una forma ordenada de acuerdo al orden decimal. Ejemplo:
a b f(x, y) = x+y
a+b a b f(x, y) = x.y
a+b
0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 0 1 Tabla de Verdad
? Describa una función de conmutación con 3 entradas a, b y c una salida z, que es verdadera (1)cuando al menos 2 de sus entradas son verdaderas (1) a b c f 0 0 0 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 VI.1 Representación de una función de Conmutación
? Formas Algebraicas – SOP (Suma de Productos):se construye al sumar(or)términos productos (and). Ejm: f(a, b, c, d) = a · b · c + b · d + a · c · d
– POS(Producto de sumas):se construye con el producto (and)de términos suma (or).
*Ejemplo: f(a, b, c, d) = (a + b + c) · (a + d)
Formas Algebraicas: a b c f 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 Representación de una función de Conmutación
? Formas Canónicas: Son formas SOP y POS con características especiales. Existe una única forma canónica para cada función de conmutación. – Minitérmino: es un término producto(and) para una función de n variables, en donde cada una aparece bien sea complementada o sin complementar. * ejm: f(a,b,c) m = a· b · c, a · b · c, a · b · c – Maxtérmino: es un término suma (or) para una
? Las variables que tiene 0 ? Las variables que tiene 1 función de n variables, en donde cada una aparece bien sea complementada o sin complementar.
* ejemplo: f(a, b, c) M = (a + b + c), (a + b + c )
Formas Canónicas SOP
f (a,b,c) = a ·b ·c + a · b · c + a · b ·c a · b · c
a·b·c a 0 0 0 0 1 1 1 1 b 0 0 1 1 0 0 1 1 c 0 1 0 1 0 1 0 1 f 1 0 1 0 0 0 0 1 a+b+c
a+b+c
a+b+c a 0 0 0 0 1 1 1 1 b 0 0 1 1 0 0 1 1 c 0 1 0 1 0 1 0 1 f 0 1 1 0 1 1 0 1 Representación de una función de Conmutación
? Especificación decimal:
-SOP: f(a, b, c) = a · b · c + a · b · c + a · b · c + a · b · c f(a, b, c) = m2 · m3 · m6 · m7 f(a, b, c) = m(2,3, 6, 7) – POS: aparecen complementadas
Formas Canónicas POS
f (a, b, c) = (a + b + c) · (a + b + c) · (a + b + c) Relación con la tabla de verdad: Cada mintérmino está asociado con la línea de la que: ? Las variables que tiene 1 no están complementadas aparecen complementadas Relación con la tabla de verdad: Cada maxtérmino está asociado con la línea de la que: ? Las variables que tiene 0 no están complementadas ? f(a, b, c) = (a + b + c) · (a + b + c) · (a + b + c) · (a + b + c) f(a, b, c) = M1 · M3 · M5 · M7 f(a, b, c) = M (1, 3, 5, 7)
? Relación Mintérminos Maxtérminos
? ? ? mi = Mi
Mi = mi
F(a, b, c) = m(2, 3, 6, 7) = M(0, 1, 4, 5) En Deducción de Formas Canónicas
? Teorema 10: Teorema de desarrollo de Shannon.
a) f(x1, x2,…, xn) = x1 · f(1, x2,…, xn) + x1 · f(0, x2,…, xn) b) f(x1, x2,…, xn) = [x1 + f(0,x2,…,xn)]·[x1 + f(1,x2,…,xn)]
Convertir a SOP Canónica
f(a, b, c) = a · b + a · c + a · c = a · f(l, b, c) + a · f(0, b, c) = a · (b + c) + a · c = b · f(a, l, c) + b · (a, 0, c) = b · (a + a · c) + b · (a · c + a · c) = a · b + a · b · c + a · b · c + a · b ·c = c · f(a, b, l) + c · (a, b, 0) = c · (a · b + a · b + a · b) + c · (a · b + a · b) = a · b · c + a · b · c + a · b · c + a · b · c + a · b ·c = L m(1, 3, 4, 6, 7)
Convertir a SOP Canónica
T6: a · b + a · b = a f(a, b, c) = a · b + a · c + a · c a · b = a · b · c + a · b · c = m7+ m6 a · c = a · b · c + a · b · c = m6+ m4 a · c = a · b · c + a · b · c = m3+ m1 f(a, b, c) = m(1, 3, 4, 6, 7)
Convertir a POS Canónica
f(a, b, c) = a · (a + c) = (a + b · b + c · c) · (a + b · b + c) = ((a + b) · (a + b ) + c · c) · ((a + b) · (a + b ) + c) = (a + b + c · c) · (a + b + c · c) · (a + b + c) · (a + b + c) = (a + b + c) · (a + b + c) · (a + b + c)(a + b + ·c) · (a + b + c) · (a + b + c) = M(0, 1, 2, 3) VII Minimización ? ?general al minimizar un sistema digital para su implementación con compuertas ofrece: ? Menor costo, consumo de potencia, espacio físico, tiempo de respuesta. ? Técnicas: ? Minimización Algebraica ? Minimización a través de Mapas de Karnuagh, ? Minimización Tabular ~
~ ~
Implementac ión minimizada: Minimización Algebraica
? Usa los teoremas del álgebra de Boole, para minimizar la función. ? No existe una técnica o método que indique cuales teoremas usar, en general se recomienda: – Expresar la función en forma de SOP o POS. – Utilizar el teorema 6, para eliminar variables, duplicando términos que puedan agruparse, -Aplicar la ley distributiva
Minimización Algebraica
Ejemplo: z = a · b · c + a · b · (a · c) Paso1: Z = a · b · c + a · b ·(a + c) Z=a·b·c+a·b+a·b·c Paso 2: Z=a·b·c+a·b·c+a·b·c Z=a·b·c+a·b+a·b·c Z = a · c · (b + b) + a · b · (1 + c) Z=a·c+·a·b Paso 3: Z = a · (c + b)
Minimización Algebraica
Implementación original:
A B C A B Z A C
A B C
Minimización por Mapas de Karnaugh
? Un mapa de Karnaugh es una representación gráfica de la tabla de verdad de una función de conmutación.
? Para 2 variables: Z
? Para 3 variables ? Para 4 variables Minimización por mapas de Karnaugh
? Coloque 1’s en las celdas correspondientes a los mintérminos de la función. ? Agrupe en un elipse lo mas grande posible, en conjuntos rectangulares de 1’s, – # de 1’s en cada conjuntos debe ser potencia de 2, – Se permite cursar elipses. ? El térmico producto resultante tendrá: -Si la variable es 1 => incluya la variable, – Si la variable es 0 => incluya la variable complementada – Si la variable es tanto 0 y 1 => no incluya la variable.
? Las elipses correspondientes a los términos productos se llaman “implicantes primos”. ? Ejemplos Minimización por mapas de Karnaugh
Minimización por mapas de Karnaugh Minimización por mapas de Karnaug
Suma total: Suma de los implicantes primos Minimización por mapas de Karnaugh
? Celdas 1 distinguidas: celdas 1 que están cubiertas por un único implicante primo. ? Implicante primo esencial (IPE): implicante que contenga al menos una celda 1 distinguida.
? Suma mínima: Suma de los IPE. f(w,x,y,z) = x·y·z + x·z + w·x +w·z f(w,x,y,z) = w + x · z F = X·Y + X·Z + W·X
Minimización por mapas de Karnaugh 2,3,4,5,6,7,11,13,15)
Minimización por mapas de Karnaugh
? Implicantes primos esenciales secundarios (IPES), ? Suma Mínima = IPE + IPES W·Y + W·X + X·Z + Y·Z) 0,1,2,3,4,5,7,14,15) Minimización por mapas de Karnaugh
2,6,7,9,13,15) W·Y·Z + W·Y·Z + X·Y·Z)
Minimizaciones por mapas de Karnaugh Expansión con Multiplexores Funciones con Multiplexores X·Y·Z
W·Y·Z
W·X·Z W·Y·Z
W·X·Z X·Y·Z
| Página siguiente |