View
213
Download
0
Category
Preview:
Citation preview
N AD
ARQUITECTURA DE COMPUTADORES
TEMA 4
IntegrantesIntegrantes
Samuel J. EstepaSamuel J. EstepaCódigo: 80’928.117Código: 80’928.117
Diana AvellanedaDiana AvellanedaCódigo: Código:
Norberto DíazNorberto DíazCódigo: 79’292.995Código: 79’292.995
TemasTemas
INTRODUCCION ALGEBRA BOLEANAINTRODUCCION ALGEBRA BOLEANA
SIMPLIFICACION DE CIRCUITOSSIMPLIFICACION DE CIRCUITOS
MAPAS DE KARNAUGHMAPAS DE KARNAUGH
REPRESENTACION DE CIRCUITOSREPRESENTACION DE CIRCUITOS
Introducción Introducción Algebra BooleanaAlgebra Booleana
Desarrollado por el matemático británico Desarrollado por el matemático británico
GEORGE BOOLEGEORGE BOOLE
Su teoría se basa en proposiciones lógicas Su teoría se basa en proposiciones lógicas mediante símbolos y pueden relacionarse por mediante símbolos y pueden relacionarse por medio de operadores matemáticos abstractos medio de operadores matemáticos abstractos
que corresponden a las leyes de la lógicaque corresponden a las leyes de la lógica
Todas las variables y constantes admiten sólo uno Todas las variables y constantes admiten sólo uno de dos valores en sus entradas y salidas: FALSO de dos valores en sus entradas y salidas: FALSO
O VERDADERO. O VERDADERO.
Estos valores bivalentes y opuestos Estos valores bivalentes y opuestos pueden ser representados por números pueden ser representados por números binarios de un dígito (bits), por lo cual el binarios de un dígito (bits), por lo cual el
Álgebra booleana se puede entender Álgebra booleana se puede entender cómo el Álgebra del Sistema Binario cómo el Álgebra del Sistema Binario
Al igual que en álgebra tradicional, Al igual que en álgebra tradicional, también se trabaja con letras del alfabeto también se trabaja con letras del alfabeto
para denominar variables y formar para denominar variables y formar ecuaciones para obtener el resultado de ecuaciones para obtener el resultado de
ciertas operaciones mediante una ciertas operaciones mediante una ecuación o expresión booleana. ecuación o expresión booleana.
Evidentemente los resultados de las Evidentemente los resultados de las correspondientes operaciones también correspondientes operaciones también
serán binarios.serán binarios.
Expresión BooleanaExpresión Booleana
Una expresión booleana también llamada función booleana o función lógica es un
conjunto finito de símbolos representados en constantes o variables combinados
mediante la operación suma, producto o complementación.
EquivalenciasEquivalencias
Axiomas de HuntingtonAxiomas de HuntingtonCada una de las operaciones Cada una de las operaciones y y es: es:
Asociativa: Asociativa: (x (x y) y) z = x z = x (y (y z) z) (x (x y) y) z = x z = x (y (y z) z)
Conmutativa: Conmutativa: x x y = y y = y x xx x y = y y = y x x
Distributiva:Distributiva: x x (y (y z) = (x z) = (x y) y) (x (x z) z)x x (y (y z) = (x z) = (x y) y) (x (x z) z)
Elemento neutro:Elemento neutro: 0 0 x = x x = x 1 1 x = x x = x
Complemento: Complemento: x x x′ = 0 x′ = 0x x x′ = 1 x′ = 1
Identidad: Identidad: x x 0 = x 0 = xx x 1 = x 1 = x
LeyesLeyes
Idempotente Idempotente x + x = x x + x = x x x = x x x = x
Inmersión Inmersión x + (xy) = x x + (xy) = x x (x + y) = xx (x + y) = x
Morgan: Morgan: (x + y)' = x‘ y‘ (x + y)' = x‘ y‘ (x y)' = x' + y' (x y)' = x' + y'
Absorción:Absorción: x + x y = xx + x y = x x (x + y) = xx (x + y) = x
Maximalidad del 1:Maximalidad del 1: x + 1 = 1x + 1 = 1
Minimalidad del 0: Minimalidad del 0: x 0 = 0x 0 = 0
Involución:Involución: x'' = xx'' = x
Convertir tabla de verdad en Convertir tabla de verdad en expresión lógica Iexpresión lógica I
1.1. Tomese cada convinacion que Tomese cada convinacion que de uno (1) a la salida y fórmese de uno (1) a la salida y fórmese
un producto de variables, de un producto de variables, de forma que si una variable vale forma que si una variable vale
cero (0) en aquella fila se coloca cero (0) en aquella fila se coloca su complemento y si vale uno su complemento y si vale uno (1) se coloca la variable sin (1) se coloca la variable sin
complementarcomplementar
2.2. Escribase la funcion que resulta Escribase la funcion que resulta de sumar todos sus productosde sumar todos sus productos
Convertir tabla de verdad en Convertir tabla de verdad en expresión lógica IIexpresión lógica II
1.1. Tomese cada convinacion que Tomese cada convinacion que de cero (0) a la salida y fórmese de cero (0) a la salida y fórmese
un producto de variables, de un producto de variables, de forma que si una variable vale forma que si una variable vale
cero (0) en aquella fila se coloca cero (0) en aquella fila se coloca su complemento y si vale uno su complemento y si vale uno (1) se coloca la variable sin (1) se coloca la variable sin
complementarcomplementar
2.2. Escribase la funcion que resulta Escribase la funcion que resulta de sumar todos sus productos, de sumar todos sus productos, negando el valor de la funcionnegando el valor de la funcion
Simplificación de Simplificación de Circuitos LógicosCircuitos Lógicos
Una vez se obtiene la función Una vez se obtiene la función booleana para un circuito lógico, booleana para un circuito lógico, podemos encontrar una expresión podemos encontrar una expresión que permite implementar el que permite implementar el circuito usando un número menor circuito usando un número menor de compuertas. de compuertas.
• Simplificación Algebraica
• Mapas de Karnaugh
F = ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD
Simplificando, F = AC + AB + BCD + AD
• Simplificación programada: Algoritmo de Quine McCluskey
Formas de SimplificaciónFormas de Simplificación
Se aplican los teoremas del álgebra de Se aplican los teoremas del álgebra de Boole para llegar a la expresión más Boole para llegar a la expresión más simple de la ecuación, que se simple de la ecuación, que se presentará en forma de sumatoria de presentará en forma de sumatoria de productos o en productos de sumasproductos o en productos de sumas
Simplificación AlgebraicaSimplificación Algebraica
F = AC + AB + BCD + AD
F = (A+B).(A+C).(B+C+D).(A+D)
EjemplosEjemplos
Considerar la expresión booleana Y = A·Considerar la expresión booleana Y = A·BB + + AA·B + A·B ·B + A·B
Simplificar aplicando los teoremas del álgebra de boole:Simplificar aplicando los teoremas del álgebra de boole:
Y = A·Y = A·BB + + AA·B + A·B ·B + A·B
= A·= A·BB + ( + (AA·B + A·B)·B + A·B) , Propiedad asociativa , Propiedad asociativa
= A·= A·BB + B·( + B·(AA+A)+A) , [A·(B + C) = A·B + A·C] ; P. , [A·(B + C) = A·B + A·C] ; P. distributivadistributiva
= A·= A·BB + B·1 + B·1 , [A + , [A + AA = 1] = 1]
= A·= A·BB + B + B , [B·1 = B] , [B·1 = B]
= B + A·= B + A·BB , Propiedad conmutativa , Propiedad conmutativa
= (B + A)·(B + = (B + A)·(B + BB)) , [A+(B·C) = (A+B)·(A+C)], [A+(B·C) = (A+B)·(A+C)]; P. ; P. distributivadistributiva
= (B + A)·1= (B + A)·1 , [A + , [A + AA = 1] = 1]
YY = B + A= B + A , [A * 1 = A] , [A * 1 = A]
Observar que deben utilizarse seis compuertas para implementar el circuito lógico no simplificado, para luego concluir que una sola compuerta OR de dos entradas realiza la misma función, como nos muestra la tabla de verdad.
EjemplosEjemplos
ENTRADASENTRADAS SALIDASALIDA
BB AA YY
00 00 00
00 11 11
11 00 11
11 11 11
Y = B + A
Simplificar la expresión booleana Simplificar la expresión booleana
F = F = ABCABC + + AABBCC + + AABC + ABC + ABCBC
Usando el álgebra de boole, tenemos:Usando el álgebra de boole, tenemos:
FF = = ABCABC + + AABBCC + + AABC + ABC + ABCBC
FF = = BCBC((A A + A) + + A) + AAB(B(CC + C) + C) ;(;(AA+A) = 1, (+A) = 1, (CC+C) = +C) = 11
FF = = BCBC + + AABB ;(A*1) = A;(A*1) = A
EjemplosEjemplos
Es un método gráfico usado para la simplificación Es un método gráfico usado para la simplificación de circuitos lógicos en un proceso simple y de circuitos lógicos en un proceso simple y ordenadoordenado
Propuesto por Maurice Karnaugh en 1953.Propuesto por Maurice Karnaugh en 1953.
Se elabora con un diagrama rectangular, que Se elabora con un diagrama rectangular, que tienen 2tienen 2n n casillas, donde n es el número de casillas, donde n es el número de variables lógicas de la expresión booleana.variables lógicas de la expresión booleana.
Mapas de Karnaugh Mapas de Karnaugh
La construcción de un mapa K se hace con base a la tabla de verdad asociada con la función booleana que se quiere representar, ya sea en forma de suma de productos o de producto de sumas.
X’X’ XX
Y’Y’
YY
X’ Y’
X’ Y
F(X,Y) = X’
XX YY f (X,Y)f (X,Y)
11 11 00
11 00 00
00 11 11
00 00 11
X’Y’X’YX’ Y + X’ Y’
1
1
X’
XX YY ZZ f (X,Y,Z)f (X,Y,Z)
11 11 11 00
11 11 00 00
11 00 11 11
11 00 00 00
00 11 11 11
00 11 00 00
00 00 11 11
00 00 00 00
X’ Y’ Z
X’ Y Z
X Y’ Z
X Y’ Z + X’ Y Z + X’ Y’ Z
EjemplosEjemplos
X’Y’X’Y’ XY’XY’ XYXY XY’XY’
Z’Z’
ZZ
X’Y’Z X’Y Z
X’ Z
X’Y’ZX Y’Z
Y’ Z+
F(X,Y,Z) = Z (X’+Y’)
X Y’ Z + X’ Y Z + X’ Y’ Z
1 11
X’ Z + Y’ Z
EjemplosEjemplos
XX YY ZZ WW f (X,Y,Z,W)f (X,Y,Z,W)
11 11 11 11 00
11 11 11 00 00
11 11 00 11 00
11 11 00 00 00
11 00 11 11 00
11 00 11 00 11
11 00 00 11 00
11 00 00 00 11
00 11 11 11 11
00 11 11 00 00
00 11 00 11 11
00 11 00 00 00
00 00 11 11 11
00 00 11 00 00
00 00 00 11 11
00 00 00 00 00
X’Y’Z’W
X’Y’Z W
X’Y Z’W
X’Y Z W
X Y’Z’W’
X Y’Z W’
X Y’Z W’ + X Y’Z’W’ + X’Y Z W + X’Y Z’W + X’Y’Z W + X’Y’Z’W
EjemplosEjemplos
X’Y’X’Y’ X’YX’Y XYXY XY’XY’
Z’W’Z’W’
Z’WZ’W
ZWZW
ZW’ZW’
X’Y’Z’WX’Y’Z WX’Y Z’WX’Y Z W
X’ W
X Y’Z’W’X Y’Z W’
X Y’W’+
F(X,Y,Z,W)=X’W+XY’W’
X Y’Z W’ + X Y’Z’W’ + X’Y Z W + X’Y Z’W + X’Y’Z W + X’Y’Z’W
1
1
11
11
EjemplosEjemplos
XX YY ZZ f (X,Y,Z)f (X,Y,Z)
11 11 11 11
11 11 00 11
11 00 11 00
11 00 00 00
00 11 11 11
00 11 00 11
00 00 11 00
00 00 00 00 X+Y+Z
X+Y+Z’
X’+Y+Z
X’+Y+Z’
(X’+Y+Z’) (X’+Y+Z) (X+Y+Z’) (X+Y+Z)
EjemplosEjemplos
X+YX+Y X+Y’X+Y’ X’+Y’X’+Y’ X’+YX’+Y
ZZ
Z’Z’
X+Y+ZX+Y+Z’
F(X,Y,Z) = Y
X’+Y+ZX’+Y+Z’
Y
0
(X’+Y+Z’) (X’+Y+Z) (X+Y+Z’) (X+Y+Z)
0
0
0
EjemplosEjemplos
XX YY ZZ WW f (X,Y,Z,W)f (X,Y,Z,W)
11 11 11 11 00
11 11 11 00 11
11 11 00 11 11
11 11 00 00 11
11 00 11 11 11
11 00 11 00 00
11 00 00 11 11
11 00 00 00 00
00 11 11 11 00
00 11 11 00 11
00 11 00 11 11
00 11 00 00 11
00 00 11 11 11
00 00 11 00 00
00 00 00 11 11
00 00 00 00 00 X+Y+Z+W
X+Y+Z’+W
X’+Y+Z+W
X’+Y+Z’+W
X+Y’+Z’+W’
X’+Y’+Z’+W’
(X’+Y’+Z’+W’)(X’+Y+Z’+W)(X’+Y+Z+W)(X+Y’+Z’+W’)(X+Y+Z’+W)(X+Y+Z+W)
X+YX+Y X+Y’X+Y’ X’+Y’X’+Y’ X’+YX’+Y
Z+WZ+W
Z+W’Z+W’
Z’+W’Z’+W’
Z’+WZ’+W
X+Y+Z+WX+Y+Z’+WX’+Y+Z+WX’+Y+Z’+W
Y+W
X+Y’+Z’+W’
X’+Y’+Z’+W’
Y’+Z’+W’*
F(X,Y,Z,W) = (Y+W)(Y’+Z’+W’)
X+Y+Z+W
X+Y+Z’+W
X’+Y+Z+W
X’+Y+Z’+W
X+Y’+Z’+W’
X’+Y’+Z’+W’
0
0
0
0
0
0
(X’+Y’+Z’+W’)(X’+Y+Z’+W)(X’+Y+Z+W)(X+Y’+Z’+W’)(X+Y+Z’+W)(X+Y+Z+W)
Recommended