1 Álgebra de Boole Tema 5

2 ¿Qué sabrás al final del capítulo?Leyes y propiedades del Algebra de Boole Simplificar funciones utilizando el Algebra de Boole Analizar circuitos mediante Algebra de Boole y simplificarlos Pasar de una tabla de verdad a Suma de Productos y Producto de Sumas Utilizar Mapas de Karnaugh para simplificar funciones lógicas

3 Algebra de Boole En Algebra habéis aprendido leyes y propiedades. Por ejemplo, la propiedad Conmutativa de la Suma A + B = B + A (A y B son números enteros o reales) En 1860 George Boole desarrolló un Algebra en la que los valores de A y B sólo podían ser “verdadero” o “falso” (1 ó 0). Se llama Algebra de Boole y se utiliza en Electrónica Digital

4 Operaciones del Algebra de BooleSuma Booleana es la función lógica OR X=A + B Multiplicación Booleana es la función lógica AND X = AB

5 Commutativa de la suma A+B = B+A El orden en la OR no importa

6 Commutativa del productoAB = BA El orden en la AND no importa

7 Asociativa de la suma A + (B + C) = (A + B) + CAgrupar variables en la OR no importa

8 Asociativa del productoA (B C) = (A B) C Agrupar variables en la AND no importa

9 Distributiva A(B + C) = AB + AC A B C X Y X=Y

10 Distributiva (A+B)(C+D) = AC + AD + BC + BD A B C D X Y X=Y

11 A+0=A Hacer una operación OR con 0 no cambia nada. A X X=A

12 A+1=1 Hacer una operación OR con 1 da siempre 1. A X X=1

13 A•0=0 Hacer una operación AND con 0 siempre da 0 A X X=0

14 A•1 =A Hacer una operación AND con 1 no cambia nada A X X=A

15 A+A = A Hacer una operación OR consigo mismo da el mismo resultado AX A=A

16 A+A=1 O bien A o A serán 1, luego la salida será 1 A X X=1

17 A•A = A Hacer una operación AND consigo mismo da el mismo resultado AX A=A

18 A•A =0 Bien A o A son 0 luego la salida será 0. A X X=0

19 A = A Si negamos algo dos veces volvemos al principio A X X=A

20 A + AB = A A B X

21 A + AB = A + B (absorción) Si A es 1 la salida es Si A es 0 la salida es B A B X Y X=Y

22 (A + B)(A + C) = A + BC A B C X Y

23 Tres leyes y doce propiedades en Algebra de Boole

24 Leyes de De Morgan De Morgan ayuda a simplificar circuitos digitales usando NORs y NANDs. A • B = A + B y A + B = A • B Igual para más de 2 variables.

25 Ambos circuitos tienen la misma salida: De Morgan funciona

26 A +B +C + D = A • B • C • D

27 Cálculo de la expresión algebraica de salida (ejemplo 1)

28 (A + B)(CD) = (A + B) + (CD)X e Y son iguales

29 Cálculo de la expresión algebraica de salida (ejemplo 2)

30 X = (A+B) C + CD + B = (A+B) C CD + B = (A+B) C (CD + B) = A B C (C +D +B) = A B C C + A B C D +A B B C = A B C D

31 Los circuitos son iguales

32 Análisis Booleano de Funciones LógicasEl propósito de este apartado es obtener expresiones booleanas simplificadas a partir de un circuito Se examina puerta a puerta a partir de sus entradas Se simplifica usando las leyes y propiedades booleanas.

33 Puerta a puerta a partir de sus entradasEjemplo 1 Puerta a puerta a partir de sus entradas X= AB+(C+D) X= AB + C+ D

34 Ejemplo 2 X = (AB)(CD) X = ABCD

35 Ejemplo 3

36 X = ABCD +A Simplificando: X = A + BCD

37 Ejemplo 4

38 En la siguiente transparencia se ve cómo las dos cosas son lo mismoX = (AB+B)BC Usando la propiedad distributiva: X = ABBC +BBC X = ABC + BBC X = ABC + 0•C X = ABC + 0 X = ABC En la siguiente transparencia se ve cómo las dos cosas son lo mismo

39

40 Ejemplo 5

41

42 X = (A +AB) +(B(C+D)) X = (A + B) + (B(C + D)) X = (A + B) + (BC + BD) X = A + B + BC + BD X = A + B + C + BD (sigue en la próxima transparencia)

43 X = A + B + C + BD X = A + B + C + D Los circuitos son iguales

44 Expresiones booleanas desde tablas de verdadProducto de sumas Y=(A+B+C)·(D+C)·(E+F) Suma de productos Y= A·B·C+B·C·D+A·C·D o directamente Y= ABC+BCD+ACD

45 Sumas de productos La función es 1 cuando ABCD=1111 o cuando ABCD=1110 o cuando ABCD=1011 o cuando ABCD=0011 y en ningún otro caso Cuando ABCD=1111, el producto ABCD y sólo ése es 1. Cuando ABCD=1110, el producto ABCD’ y sólo ése es 1,… …y así sucesivamente… resultando que ABCD + ABCD’ + AB’CD + A’B’CD

46 Productos de sumas La función es 0 cuando ABCD=0010 o cuando ABCD=0100 o cuando ABCD=0111 o cuando ABCD=1010 o cuando ABCD=1101 y en ningún otro caso Cuando ABCD=0010, la suma A+B+C’+D y sólo ésa es 0. Cuando ABCD=0100, la suma A+B’+C+D y sólo ésa es 0, … …y así sucesivamente… resultando que (A+B+C’+D)(A+B’+C+D)(A+B’+C’+D’)(A’+B+C’+D)(A’+B’+C+D’)

47 Minimización de funciones lógicasMapas de Karnaugh: se usan para minimizar el número de puertas requeridas en un circuito digital Es adecuado en vez de usar leyes y propiedades cuando el circuito es grande Se consigue, aplicando adecuadamente el método, el circuito más simplificado posible

48 Mapa de Karnaugh El mapa se hace con una tabla con tantas celdas como Sumas de Productos posibles, teniendo en cuenta el número de variables que se utilice. 2 variables, entonces mapa 2x2 3 variables, entonces mapa 4x2 4 variables, entonces mapa 4x4 5 variables, entonces mapa 8x4

49 Mapa de Karnaugh Lo interesante del mapa es moverse de una celda a otra contigua con el cambio de una sola variable. Los movimientos son arriba-abajo o derecha-izquierda (nunca en diagonal). El mapa también se dobla sobre sí mismo con la misma regla: solo una variable cambia de la última columna a la derecha a la primera a la izquierda, o de la fila de abajo a la de arriba. Emplearemos un código Gray, que se caracteriza porque entre dos códigos consecutivos (incluidos los extremos) sólo hay un bit de diferencia.

50 Esto muestra que F = 1 cuando A=0 y B=0B B 1 El mapa va de Falso a Verdadero, de izquierda a derecha y de arriba abajo La celda de arriba a la izquierda es A B. Si F= A B, entonces hay que poner 1 en esa celda A B B 1 1 1 Esto muestra que F = 1 cuando A=0 y B=0

51 A B B 1 Si F=AB + AB entonces hay que poner 1 en las dos celdas Sabemos por el Algebra de Boole que A B + A B = B A B B 1 En el mapa de Karnaugh podemos agrupar celdas adyacentes y ver que F = B

52 Mapas de 3 variables Código Gray A B C C 1 00 01 11 10

53 X = A B C + A B C + A B C + A B C Código Gray A B C CCada término de 3 variables es una celda en un mapa de Karnaugh 4 X 2 1 00 01 11 10 1 1 1 1

54 X = A B C + A B C + A B C + A B C Código Gray A B C CUna simplificación podría ser: X = A B + A B 1 00 01 11 10 1 1 1 1

55 X = A B C + A B C + A B C + A B C Código Gray A B C COtra simplificación podría ser: X = B C + B C El mapa de Karnaugh se dobla circularmente 1 00 01 11 10 1 1 1 1

56 X = A B C + A B C + A B C + A B C Código Gray 00 A B 01 A B 11 A BLa mejor simplificación sería X = B 1 00 01 11 10 1 1 1 1

57 En un mapa de 3 variables Una celda a 1 implica a 3 variablesDos celdas adyacentes a 1 implican a 2 variables Cuatro celdas adyacentes a 1 implican a 1 variable Ocho celdas adyacentes a 1 constituyen función de valor 1

58 Mapa de Karnaugh de 4 variablesCódigo Gray A B C D C D C D C D 00 01 11 10 00 01 11 10

59 Simplificar X = A B C D + A B C D + A B C D + A B C D + A B C D + A B C DCódigo Gray A B C D C D C D C D 00 01 11 10 00 01 11 10 Intentar con reducciones booleanas 1 1 1 1 1 1 X = ABD + ABC + CD

60 En un mapa de 4 variables Una celda a 1 implica a 4 variablesDos celdas adyacentes a 1 implican a 3 variables Cuatro celdas adyacentes a 1 implican a 2 variables Ocho celdas adyacentes a 1 implican a 1 variable Dieciséis celdas adyacentes a 1 constituyen función de valor 1

61 Simplificar Z = B C D + B C D + C D + B C D + A B CC D C D C D C D 00 01 11 10 00 01 11 10 1 1 1 1 1 1 1 1 1 1 1 1 X = C + A B + B D

62 Dado un circuito encontrar otro más sencillo usando Mapas de KarnaughPrimero lo pasamos a Suma de Productos

63 Y= A + B + B C + ( A + B ) ( C + D) Y = A B + B C + A B ( C + D ) Y = A B + B C + A B C + A B D Y = A B + B C + A B C A B D Y = A B + B C + (A + B + C ) ( A + B + D) Y = A B + B C + A + A B + A D + B + B D + A C + C D Y = A B + B C + A + B + C D = A + B + B + C D = 1

64 A B C D C D C D C D 00 01 11 10 00 01 11 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Z = 1

65

66 SIMPLIFICACIÓN POR KARNAUGH1) Realizar agrupaciones de 1's, con sus adyacentes, lo mayor posibles, pero siempre en cantidades potencias de 2. 2) No dejar ningún 1 sin agrupar. Puede ocurrir que un 1 pertenezca a más de una agrupación. No se pueden coger agrupaciones dentro de agrupaciones. 3) Por cada agrupación de 1's resulta un producto de variables. Cuanto más 1's se agrupen, más sencilla resultará la expresión de esa agrupación. En MK de 5 variables, las agrupaciones que tomen 1’s de las dos porciones deben ser simétricas respecto al eje central. 4) En cada agrupación, cada una de las variables puede aparecer en alguno de los siguientes casos: a) Si siempre vale > Se pone afirmada. b) Si siempre vale > Se pone negada. c) Si cambia de valor (50% de los casos un valor y el otro 50% otro valor) -----> No se pone. 5) La expresión de la función booleana será la suma lógica de todos los productos que hayan salido.

67 Diseñar un sistema de alarmaSensores disponibles 1. V = Ventana (V=0 CERRADA, V=1 ABIERTA) 2. P = Puerta (P=0 CERRADA, P=1 ABIERTA) C = Calefacción (C=0 APAGADA, C=1 ENCENDIDA) 4. A = Aire acondicionado (A=0 APAGADO, A=1 ENCENDIDO) 5. I = Alarma de proximidad de intruso (I=0 NO HAY INTRUSO, I=1 SI HAY INTRUSO)

68 El sistema de alarma debe activarse cuando:1. La puerta está abierta y la calefacción encendida (P=1, C=1) La puerta está abierta y el aire acondicionado encendido (P=1, A=1) La puerta está abierta con una alarma de proximidad de intruso (P=1, I=1) La ventana está abierta y la calefacción encendida. (V=1, C=1) La ventana está abierta y el aire acondicionado encendido (V=1, A=1) 6. La ventana está abierta con una alarma de proximidad de intruso (V=1, I=1)

69 Rellenando el mapa…(P=1, C=1)C A I C A I C A I C A I C A I C A I C A I C A I 000 001 011 010 110 111 101 100 V P 00 01 11 10 1

70 Rellenando el mapa…(P=1, A=1)C A I C A I C A I C A I C A I C A I C A I C A I 000 001 011 010 110 111 101 100 V P 00 01 11 10 1

71 Rellenando el mapa…(P=1, I=1)C A I C A I C A I C A I C A I C A I C A I C A I 000 001 011 010 110 111 101 100 V P 00 01 11 10 1

72 Rellenando el mapa…(V=1, C=1)C A I C A I C A I C A I C A I C A I C A I C A I 000 001 011 010 110 111 101 100 V P 00 01 11 10 1

73 Rellenando el mapa…(V=1, A=1)C A I C A I C A I C A I C A I C A I C A I C A I 000 001 011 010 110 111 101 100 V P 00 01 11 10 1

74 Rellenando el mapa…(V=1, I=1)C A I C A I C A I C A I C A I C A I C A I C A I 000 001 011 010 110 111 101 100 V P 00 01 11 10 1

75 Podemos agrupar así… C A I C A I C A I C A I C A I C A I C A I C A I000 001 011 010 110 111 101 100 V P 00 01 11 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 X = P A + V A + P C + V C + P I + V I ¿Cuántos chips necesito para esto?

76 O usando los ceros… C A I C A I C A I C A I C A I C A I C A I C A I000 001 011 010 110 111 101 100 V P 00 01 11 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 X = C A I + V P Sólo dos chips

77 Patillaje de los circuitos 7404 y 7454

78 Conexionado físico

79 Circuito diseñado

80 Ya sabes… Leyes y propiedades del Algebra de BooleSimplificar funciones utilizando el Algebra de Boole Analizar circuitos mediante Algebra de Boole y simplificarlos Pasar de una tabla de verdad a Suma de Productos y Producto de Sumas Utilizar Mapas de Karnaugh para simplificar funciones lógicas

81 Final del Tema 5