1 ARQUITECTURA DE COMPUTADORESN AD U ARQUITECTURA DE COMPUTADORES TEMA 4 ALGEBRA DE BOOLE Y MAPAS DE KARNAUGH

2 Integrantes Samuel J. Estepa Código: 80’928.117 Diana AvellanedaNorberto Díaz Código: 79’

3 Temas INTRODUCCION ALGEBRA BOLEANA SIMPLIFICACION DE CIRCUITOSMAPAS DE KARNAUGH REPRESENTACION DE CIRCUITOS

4 Introducción Algebra BooleanaDesarrollado por el matemático británico GEORGE BOOLE Su teoría se basa en proposiciones lógicas mediante símbolos y pueden relacionarse por medio de operadores matemáticos abstractos que corresponden a las leyes de la lógica Todas las variables y constantes admiten sólo uno de dos valores en sus entradas y salidas: FALSO O VERDADERO.

5 Estos valores bivalentes y opuestos pueden ser representados por números binarios de un dígito (bits), por lo cual el Álgebra booleana se puede entender cómo el Álgebra del Sistema Binario Al igual que en álgebra tradicional, también se trabaja con letras del alfabeto para denominar variables y formar ecuaciones para obtener el resultado de ciertas operaciones mediante una ecuación o expresión booleana. Evidentemente los resultados de las correspondientes operaciones también serán binarios.

6 Expresió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.

7 Equivalencias

8 Axiomas de Huntington Cada una de las operaciones Å y Ä es:Asociativa: (x Å y) Å z = x Å (y Å z) (x Ä y) Ä z = x Ä (y Ä z) Conmutativa: x Å y = y Å x x Ä y = y Ä x Distributiva: x Å (y Ä z) = (x Å y) Ä (x Å z) x Ä (y Å z) = (x Ä y) Å (x Ä z) Elemento neutro: 0 Å x = x 1 Ä x = x Complemento: x Å x′ = 0 x Ä x′ = 1 Identidad: x Å 0 = x x Ä 1 = x

9 Leyes Idempotente x + x = x x x = xInmersión x + (xy) = x x (x + y) = x Morgan: (x + y)' = x‘ y‘ (x y)' = x' + y' Absorción: x + x y = x x (x + y) = x Maximalidad del 1: x + 1 = 1 Minimalidad del 0: x 0 = 0 Involución: x'' = x

10 Convertir tabla de verdad en expresión lógica ITomese cada convinacion que de uno (1) a la salida y fórmese un producto de variables, de forma que si una variable vale cero (0) en aquella fila se coloca su complemento y si vale uno (1) se coloca la variable sin complementar Escribase la funcion que resulta de sumar todos sus productos f = x'yz' + x'yz + xy'z + xyz' + xyz

11 Convertir tabla de verdad en expresión lógica IITomese cada convinacion que de cero (0) a la salida y fórmese un producto de variables, de forma que si una variable vale cero (0) en aquella fila se coloca su complemento y si vale uno (1) se coloca la variable sin complementar Escribase la funcion que resulta de sumar todos sus productos, negando el valor de la funcion f ' = x'y'z' + x'y'z + xy'z'

12 Simplificación de Circuitos LógicosUna vez se obtiene la función booleana para un circuito lógico, podemos encontrar una expresión que permite implementar el circuito usando un número menor de compuertas.

13 Formas de SimplificaciónSimplificación Algebraica F = ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD Simplificando, F = AC + AB + BCD + AD Mapas de Karnaugh Simplificación programada: Algoritmo de Quine McCluskey

14 Simplificación AlgebraicaSe aplican los teoremas del álgebra de Boole para llegar a la expresión más simple de la ecuación, que se presentará en forma de sumatoria de productos o en productos de sumas F = AC + AB + BCD + AD F = (A+B).(A+C).(B+C+D).(A+D)

15 Ejemplos Considerar la expresión booleana Y = A·B + A·B + A·BSimplificar aplicando los teoremas del álgebra de boole: Y = A·B + A·B + A·B = A·B + (A·B + A·B) , Propiedad asociativa = A·B + B·(A+A) , [A·(B + C) = A·B + A·C] ; P. distributiva = A·B + B·1 , [A + A = 1] = A·B + B , [B·1 = B] = B + A·B , Propiedad conmutativa = (B + A)·(B + B) , [A+(B·C) = (A+B)·(A+C)]; P. distributiva = (B + A)·1 , [A + A = 1] Y = B + A , [A * 1 = A]

16 Ejemplos Y = B + 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. ENTRADAS SALIDA B A Y 1

17 Ejemplos Simplificar la expresión booleana F = ABC + ABC + ABC + ABCUsando el álgebra de boole, tenemos: F = ABC + ABC + ABC + ABC F = BC(A + A) + AB(C + C) ;(A+A) = 1, (C+C) = 1 F = BC + AB ;(A*1) = A

18 Mapas de Karnaugh Es un método gráfico usado para la simplificación de circuitos lógicos en un proceso simple y ordenado Propuesto por Maurice Karnaugh en 1953. Se elabora con un diagrama rectangular, que tienen 2n casillas, donde n es el número de variables lógicas de la expresión booleana.

19 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 Y f (X,Y) 1 X’ Y X’ Y’ X’Y’ X’ X Y’ Y X’Y X’ Y + X’ Y’ 1 X’ 1 F(X,Y) = X’

20 Ejemplos X Y’ Z + X’ Y Z + X’ Y’ Z X Y Z f (X,Y,Z) 1 X Y’ Z X’ Y ZX Y’ Z X’ Y Z X’ Y’ Z X Y’ Z + X’ Y Z + X’ Y’ Z

21 Ejemplos X’Y’ XY’ XY Z’ Z X Y’ Z + X’ Y Z + X’ Y’ Z 1 1 1X’ Z + Y’ Z F(X,Y,Z) = Z (X’+Y’) X’ Z + Y’ Z

22 Ejemplos X Y’Z W’ + X Y’Z’W’ + X’Y Z W + X’Y Z’W + X’Y’Z W + X’Y’Z’Wf (X,Y,Z,W) 1 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

23 Ejemplos X’Y’ X’Y XY XY’ Z’W’ Z’W ZW ZW’ 1 1 1 1 1 1X’ W + X Y’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 F(X,Y,Z,W)=X’W+XY’W’

24 (X’+Y+Z’) (X’+Y+Z) (X+Y+Z’) (X+Y+Z)Ejemplos X Y Z f (X,Y,Z) 1 X’+Y+Z’ X’+Y+Z X+Y+Z’ X+Y+Z (X’+Y+Z’) (X’+Y+Z) (X+Y+Z’) (X+Y+Z)

25 Ejemplos X+Y X+Y’ X’+Y’ X’+Y Z Z’ (X’+Y+Z’) (X’+Y+Z) (X+Y+Z’) (X+Y+Z)(X’+Y+Z’) (X’+Y+Z) (X+Y+Z’) (X+Y+Z) X+Y+Z X+Y+Z’ X’+Y+Z X’+Y+Z’ F(X,Y,Z) = Y Y

26 (X’+Y’+Z’+W’)(X’+Y+Z’+W)(X’+Y+Z+W)(X+Y’+Z’+W’)(X+Y+Z’+W)(X+Y+Z+W)f (X,Y,Z,W) 1 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)

27 (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+Y+Z’+W X+Y’+Z’+W’ X’+Y+Z+W X’+Y+Z’+W X’+Y’+Z’+W’ Y+W * Y’+Z’+W’ F(X,Y,Z,W) = (Y+W)(Y’+Z’+W’)