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)