1 ALGEBRA DE BOOLE SISTEMAS DIGITALES

2 Introducción El álgebra booleana define constantes y funciones para describir sistemas binarios. Luego describe cierto número de teoremas que se pueden usar para manipular expresiones lógicas. CONSTANTES BOOLEANAS: consisten en "0" y "1". El primero representa el estado falso y el segundo el estado verdadero. SISTEMAS DIGITALES

3 VARIABLES BOOLEANAS: Son magnitudes que pueden tomar diferentes valores en diferentes momentos. Pueden representar señales de entrada, de salida o intermedias y reciben nombres que de ordinario consisten en caracteres alfabéticos como "A", "B", "X" o "Y". Las variables sólo pueden tomar los valores "0" ó "1". SISTEMAS DIGITALES

4 FUNCIONES BOOLEANAS: Cada una de las funciones lógicas elementales está representada dentro del álgebra booleana mediante un símbolo único, como se muestra en la siguiente tabla: Función Símbolo Ejemplo AND Punto OR Más (+) NOT Barra SISTEMAS DIGITALES

5 Postulados Básicos Los postulados básicos utilizados en el álgebra booleana son los siguientes: Postulado 1: Postulado 2: SISTEMAS DIGITALES

6 Postulado 3: Postulado 4: Postulado 5: SISTEMAS DIGITALES

7 A B 1 SISTEMAS DIGITALES

8 Teoremas Booleanos El álgebra booleana define varios teoremas que se pueden usar para cambiar la forma de una expresión. Estos teoremas son los siguientes: SISTEMAS DIGITALES

9 Teorema 1: Dual: Teorema 2: Dual: SISTEMAS DIGITALES

10 Teorema 3: Dual: Teorema 4: Dual: Teorema 5: Dual: SISTEMAS DIGITALES

11 Teorema 6: Dual: Teorema 7: Dual: Teorema 8: SISTEMAS DIGITALES

12 Teoremas SimplificatoriosDual: Teorema 10: Dual: Teorema 11: Dual: Teorema 12: Dual: SISTEMAS DIGITALES

13 Ejemplo: Simplificar la siguiente expresiónTeorema 13: Dual: Ejemplo: Simplificar la siguiente expresión SISTEMAS DIGITALES

14 Desarrollo SISTEMAS DIGITALES

15 Formas Especiales de Expresiones BooleanasSISTEMAS DIGITALES

16 Formas Canónicas SUMA EXPANDIDA DE PRODUCTOS: En este caso para aplicar la expansión se aplica el teorema 10 Cada uno de los términos en forma canónica expresado en suma (OR de AND) se llama Mintérmino y se puede expresar en forma simplificada. Si en este caso a la variable natural se le asigna el valor lógico uno y la variable complementada el valor lógico cero. SISTEMAS DIGITALES

17 Ejemplo: SISTEMAS DIGITALES

18 Formas Canónicas PRODUCTO EXPANDIDO DE SUMAS: Esta forma de expresar una función booleana se basa en el dual del teorema 10 Cada uno de los términos en forma canónica expresado en producto (AND de OR) se llama Máxtermino y se puede expresar en forma simplificada. Si en este caso a la variable natural se le asigna el valor lógico cero y la variable complementada el valor lógico uno. SISTEMAS DIGITALES

19 Ejemplo: SISTEMAS DIGITALES

20 Formas Mínimas Mínima Suma Productos Mínima Productos de SumasEn este caso interesa que la función booleana sea lo más pequeña posible, es decir que si está expresada en la forma OR de AND el número de sumandos y el tamaño de cada sumando debe ser mínimo. Si la función está expresada en la forma AND de OR entonces el tamaño y el número de factores debe ser mínimo. SISTEMAS DIGITALES

21 Métodos de Simplificación de Expresiones BooleanasSISTEMAS DIGITALES

22 Formas Canónicas MÉTODO ALGEBRAICO:Corresponde a los casos analizados anteriormente. MAPAS DE KARNAUGH: Los mapas o diagramas de Karnaugh representan una técnica gráfica para simplificar las ecuaciones de Boole. Es uno de los métodos más usuales para ecuaciones de hasta 4 ó 5 variables y se basa en el teorema 10: SISTEMAS DIGITALES

23 Introducción Mapa de KarnaughLos Mapas de Karnaugh, como se dijo anteriormente, se utilizan para simplificar funciones booleanas. El número de casilleros que tendrá el mapa dependerá de la cantidad de variables que tenga la función. SISTEMAS DIGITALES

24 Ejemplo: Nº de variables: 2 Nº Casilleros: 2n=22=4 SISTEMAS DIGITALES

25 Dentro de cada casillero del mapa se debe poner un uno (1) o un cero(0) lógico dependiendo si la función está expresada como OR de AND o AND de OR. Para el caso de los mintérminos corresponde un “1” en el casillero, por el contrario, para cada maxtérmino corresponde un “0” al casillero SISTEMAS DIGITALES

26 Mapa para 3 Variables SISTEMAS DIGITALES

27 Mapa para 4 Variables SISTEMAS DIGITALES

28 Representación de Variables en Mapa de KarnaughSISTEMAS DIGITALES

29 Hay que hacer notar que antes de realizar la representación de las variables de una función en el Mapa de Karnaugh se debe definir las variables más significativas (MSB) y la menos significativa (LSB) SISTEMAS DIGITALES

30 Ejemplo: Representar en mapa de KarnaughSISTEMAS DIGITALES

31 Existen algunos casos en que el valor lógico que se debe asignar a los casilleros del mapa no está definido y nosotros podemos asignar el valor lógico “1” ó “0” según la conveniencia para la simplificación. Estás condiciones reciben el nombre de “Superfluas” o “No Importa” y se designan con los simbolos f o x SISTEMAS DIGITALES

32 Ejemplo: Representar en Mapa la siguiente funciónSISTEMAS DIGITALES

33 Definición e Interpretación Mapas de KarnaughB C Z 1 Un diagrama de Karnaugh representa una ecuación de Boole de una forma bastante similar a una tabla de verdad. Ejemplo 1: SISTEMAS DIGITALES

34 SISTEMAS DIGITALES

35 Del ejemplo anterior se deduce que para una función booleana de 3 variables se necesita un mapa de 8 casilleros. En cada casillero se representa un "1" lógico para cada mintérmino y un "0" lógico para cada máxtermino. Debe notarse que la asignación de las variables en los casilleros tanto en el sentido vertical como horizontal corresponden al código Gray. SISTEMAS DIGITALES

36 Método de SimplificaciónPara simplificar una expresión booleana mediante el Mapa de Karnaugh se deben agrupar los casilleros que contienen 1 adyacente y en un número tal que sea potencia de 2 como agrupación de mintérminos, de lo que resulta un factor simplificado. Es posible representar esquemáticamente la cantidad de variables eliminadas producto de la agrupación: SISTEMAS DIGITALES

37 20 variables eliminadas = 0 21 variables eliminadas = 1 SISTEMAS DIGITALES

38 Criterios de Agrupación: La agrupación debe ser lo más grande posible Se debe tener el mínimo de agrupaciones Se agrupan los adyacentes en un número que sea potencia de 2 Criterios de Adyacencia: Casilleros con un lado común Reflexión de acuerdo al Código Gray SISTEMAS DIGITALES

39 Simplificar el mapa: SISTEMAS DIGITALES

40 Solución 1: SISTEMAS DIGITALES

41 Solución 2: SISTEMAS DIGITALES

42 El ejemplo anterior demuestra que al no hacer agrupaciones lo más grande posible se obtiene una función correcta pero que no es la forma mínima SISTEMAS DIGITALES