Baixe simplificacion de funciones booleanas e outras Notas de estudo em PDF para Engenharia Industrial, somente na Docsity! Simplificación de funciones booleanas. Circuitos lógicos mínimos. Sistemas electrónicos digitales Material de apoyo didactico Los procedimientos de simplificación de funciones booleanas se desarollan con el propósito de obtener una expresión booleana mínima que permita construir un circuito con el menor número posible de puertas lógicas. El criterio que vamos a utilizar es el de obtener un circuito mínimo en dos niveles. Esto se consigue a partir de una expresión booleana normalizada, bien como suma de productos, bien como producto de sumas, que sea mínima en cuanto al número de términos utilizados, (producto o suma) y mínima en cuanto al nº de literales de los mismos. Este criterio no es único y, a veces, conduce a circuitos que presentan problemas de implementación práctica, (riesgos) que tienen solución introduciendo cierta redundancia en la expresión mínima. Además, objetivos de diseño como son fiabilidad y testabilidad, de especial importancia en el diseño de circuitos integrados, implican modificar el Los métodos que vamos a estudiar son: - Reducción Algebraica: Usa los teoremas y axiomas del álgebra de Boole para reducir una expresión dada. - Mapas de Karnaugh: Método gráfico. Útil para simplificar manualmente funciones de hasta 6 variables. - Método tabular de Quine-McCluskey. Algoritmo para la simplificación de cualquier función booleana, apropiado para ser programado. Especialmente útil para funciones de muchas variables y simplificación simultánea de varias funciones booleanas. Simplificación de funciones booleanas criterio anterior. De todas formas, un circuito en dos niveles es un punto de partida adecuado para el diseño de sistemas digitales. Simplificación de funciones booleanas. Metodo algebraico. Sistemas electrónicos digitales Material de apoyo didáctico Método Agebraico Se basa en el siguiente teorema del Álgebra de Boole: x1x2…xN x1x2…xN+ x2…xN= x1 x2 … xN+ + +( ) x1 x2 … xN+ + +( )⋅ x2 … xN+ +( )= a) b) a) La suma de dos términos producto adyacentes es igual a un término producto que posee un literal menos, aquel en el que se diferencian. Los términos producto de la expresión a) se dice que son adyacentes por coincidir en todos sus literales menos en uno, x1 . El teorema puede leerse así: b) El producto de dos términos suma adyacentes es igual a un término suma que posee un literal menos, aquel en el que se diferencean. Para aplicar este método de simplificación: 1º. Se obtiene una expresión canónica, bien suma de productos, bien producto de sumas. 2º. Se buscan términos adyacentes y se sustituyen por términos más simples. 3º. El paso 2º se repite hasta encontrar una expresión irreducible. Ej: F x y z, ,( ) 0 2 3 6 7, , , ,( ) 3 ∑= xyz xyz xyz xyz xyz+ + + +( )= (0,2) (2,3) (2,6)adyacencias (3,7) (6,7) F x y z, ,( ) xyz xyz xyz xyz xyz xyz xyz xyz xyz xyz+ + + + + + + + += F x y z, ,( ) xz xy yz yz xy+ + + + xz y y+ + xz y+= = = adyacencias de 2º orden Los términos suma de la expresión b) se dice que son adyacentes por coincidir en todos sus literales menos en uno, x1. Simplificación de funciones booleanas. Metodo algebraico. Sistemas electrónicos digitales Material de apoyo didáctico Definiciones: Sean F(x1,...xn) y G(x1,...xn) dos funciones booleanas. Si F cubre a G, se dice que G implica a F, o que G es implicante de F. Se dice que F cubre a G si siempre que G toma el valor 1, F tambien lo toma. F G⊇( ) Si se cumple G F⊇( )F G⊇( ) y , se dice que F y G son equivalentes Ej: F x y z, ,( ) 0 1 3 4, , ,( ) 3 ∑= G x y z, ,( ) 0 3,( ) 3 ∑= F G⊇ Ej: F w x y z, , ,( ) wx yz+= H w x y z, , ,( ) wxy= F H⊇ F w x y z, , ,( ) wxy wxy yz+ += Un producto de literales p se dice que es implicante primo de una función booleana F, sii implica a F y además, cualquier subproducto (producto con menos literales) obtenido de p, no es implicante de F. Vamos a llamar PF al conjunto de los implicantes primos de F. Ej: F w x y z, , ,( ) wxy wxy yz+ += a) No son implicantes primos porque existe el subproducto wx que es b) Si es implicante primo porque implica a F y ni y,ni z son implicantes a) b) implicante de F. wx si es implicante primo porque implica a F y ni w , ni x son implicantes de F. PF = {wx , yz } de F. Simplificación de funciones booleanas. Metodo algebraico. Sistemas electrónicos digitales Material de apoyo didáctico Tabla 1: Procedimiento sistemático para la obtención de una expresión mínima en forma de suma de productos de una función booleana. 1º Obtener el conjunto de implicantes primos. 2º Seleccionar, de entre éstos, los implicantes primos esenciales, y formar una expresión mínima. 3º Eliminar del conjunto de implicantes primos aquellos que cubran minitérminos que ya estén cubietos por los implicantes primos esenciales. 4º Verificar que todos los minitérminos que hacen uno a la función dada están cubiertos por la expresión mínima obtenida, y si no es así, añadir a ésta los implicantes primos necesarios para conseguirlo. Teorema: Cualquier expresión irreducible en forma suma de productos de una función booleana F resulta de la unión de implicantes primos de F. Definición: Un implicante primo de una función F se dice que es esencial si cubre al menos a un minitérmino de la función que no puede ser cubierto por ningún otro implicante primo de la misma. Ej: F x y z t, , ,( ) 0 2 6 7 8 10 14 15, , , , , , ,( ) 4 ∑= PF = { yt , zt , yz } yt yz zt cubre a los minitérminos {0,2,8,10} cubre a los minitérminos {2,6,10,14} cubre a los minitérminos {6,7,14,15} yt yz son implicantes primos esenciales, Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico x yz 00 01 11 10 0 1 3 2 4 5 67 0 1 Ejemplo 2: Mapa de Karnaugh de tres variables F x y z, ,( ) xy xz xy yz yz+ + + += 1 1 1 1 1 0 0 0 x yz 00 01 11 10 0 1 3 2 4 5 67 0 1 1 1 1 1 1 0 0 0 xy yz xzxy yz Vamos a obtener una expresión mínima y xz PF = { y xz }, F x y z, ,( ) y xz+=La expresión mínima resulta Todos los implicantes primos son esenciales. Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico Mapa de Karnaugh de cuatro variables x y z t 00 01 11 10 00 01 11 10 0 1 3 2 4 5 67 8 9 1011 12 13 1415 Ejemplo 1: x y z t 00 01 11 10 00 01 11 10 0 1 3 2 4 5 67 8 9 1011 12 13 1415 F x y z t, , ,( ) 0 2 4 5 6 7 8 10 13, , , , , , , ,( ) 4 ∑= 1 1 1 1 1 1 1 1 1 0 0 00 0 00 xt yt xy yzt xt yt xy yztPF = { }, , , Todos los implicantes primos son esenciales excepto xt La expresión mínima resulta: F x y z t, , ,( ) xy yt yzt+ += Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico Mapa de Karnaugh de cuatro variables Ejemplo 2: F x y z t, , ,( ) x y⊕ xyt+= F x y z t, , ,( ) xy xy+ xyt+ x y+( ) x y+( )⋅[ ] xyt+ xy xy xyt+ += = = x y z t 00 01 11 10 00 01 11 10 0 1 3 2 4 5 67 8 9 1011 12 13 1415 x y z t 00 01 11 10 00 01 11 10 0 1 3 2 4 5 67 8 9 1011 12 13 1415 1 1 1 1 1 10 0 0000 1 1 1 1 xy xy xyt 1 1 1 1 1 10 0 0000 1 1 1 1 Vamos a encontrar una expresión mínima: xy yt xt PF = { xy xt yt xy,,, } xy xy xy, xt yt, son implicantes primos esenciales, pero entre ambos no cubren a todos los miniterminos que hacen uno a F. Para obtener la expresión mínima es necesario añadir uno de los implicantes primos no esenciales Se tienen pues dos expresiones mínimas: F x y z t, , ,( ) xy xy yt+ += F x y z t, , ,( ) xy xy xt+ +=o bien Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico xy ztu 00 01 11 10 000 001 011 010 0 1 3 2 110 111 101 100 16 17 19 18 24 25 27 26 8 9 11 10 6 7 5 4 22 23 21 20 30 31 29 28 14 15 13 12 Mapa de Karnaugh de cinco variables Mapa de Karnaugh de seis variables xyz tuv 000 001 011 010 000 001 011 010 0 1 3 2 110 111 101 100 16 17 19 18 24 25 27 26 8 9 11 10 6 7 5 4 22 23 21 20 30 31 29 28 14 15 13 12 110 111 101 100 48 49 51 50 32 33 35 34 40 41 43 42 56 57 59 58 54 55 53 52 38 39 37 36 46 47 45 44 63 63 61 60 Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico Mapa de Karnaugh de cinco variables Ejemplo: F x y z t u, , , ,( ) = 1 3 5 9 10 11 12 13 14 15 18 19 21 23 25 26 27 28 29 30 31, , , , , , , , , , , , , , , , , , , ,( ) 5 ∑ xy ztu 00 01 11 10 000 001 011 010 0 1 3 2 110 111 101 100 16 17 19 18 24 25 27 26 8 9 11 10 6 7 5 4 22 23 21 20 30 31 29 28 14 15 13 12 0 1 1 00 0 1 1 1 1 1 10 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 xy ztu 00 01 11 10 000 001 011 010 0 1 3 2 110 111 101 100 16 17 19 18 24 25 27 26 8 9 11 10 6 7 5 4 22 23 21 20 30 31 29 28 14 15 13 12 0 1 1 00 0 1 1 1 1 1 10 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 Adyacencias de orden 3 yt yzyu Adyacencias de orden 2 no cubiertas por adycencias de orden 3. xtu ztu ztu xzu xzuxzt xtu ztu xzu xzt xzu xtu xtu ztu Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico Mapa de Karnaugh de cinco variables Ejemplo (continuación) PF = { ztu xzu xzt xzu xtu xtu ztu yt yz yu yt yu yz xzu xzt xzu xtu xtu ztu ztu,,,,,,,,, } Vamos a ver cuales son esenciales y cuales no. minterm de F PF 1 3 5 9 10 11 12 13 14 15 18 19 21 23 25 26 27 28 29 30 31 x x x x x x x x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x yt yz xzt yu yz Tomando los implicantes primos esenciales quedan sin cubrir los miniterminos xy ztu 00 01 11 10 000 001 011 010 0 1 3 2 110 111 101 100 16 17 19 18 24 25 27 26 8 9 11 10 6 7 5 4 22 23 21 20 30 31 29 28 14 15 13 12 0 1 1 00 0 1 1 1 1 1 10 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 m1,m3,m5,m21,m23 a) b) c) d) e) f) g) h) i) j) Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico Fsp A3A0 A2A1A0 A2A1A0 A2A3A1A0+ + += Fps A2 A0+( ) A2 A1+( ) A3 A0+( ) A3 A1 A0+ +( ) A2 A1 A0+ +( )⋅ ⋅ ⋅ ⋅= Ambas son expresiones mínimas, equivalentes a F Veamos si Fsp y Fps son equivalentes entre si. Para ello construiremos sus respectivas funciones canónicas. Fsp A3 A2 A1 A0,,,( ) 0 3 6 9 11 13 14 15, , , , , , ,( ) 4 ∑= Fps A3 A2 A1 A0,,,( ) 0 3 6 9 11, , , ,( ) 4 ∑= F A3 A2 A1 A0, , ,( ) 0 3 6 9, , ,( ) 4 ∑ 10 11 12 13 14 15, , , , ,( ) ∅ ∑+= Vemos que Fsp y Fps no son equivalentes entre si, tan solo podemos decir que Fsp cubre a Fps. Vemos que tanto Fsp, como Fps son equivalentes a F porque coinciden para todos los minitérminos que están definidos. Ej: (continuación) Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico Para obtener funciones booleanas mínimas utilizando los mapas de Karnaugh se siguen los siguientes pasos: 1º Se construye el mapa de Karnaugh adecuado según el número de variables de la función dada. 2º Se representan sobre él los miniterminos (maxiterminos) que hacen uno (cero) a la función para la simplificación mediante suma de productos (producto de sumas). 3º Se representan las posibles indiferencias de la función (si las hay). 4º Se obtienen los implicantes (implicados) primos de la función, buscando minitérminos (maxitérminos) adyacentes, empezando por las de mayor orden . En esta operación las indiferencias se toman como unos o ceros según convenga. 5º De todos los implicantes (implicados) primos se selecciona un conjunto mínimo que cubra todos los minitérminos (maxitérmi- nos) para formar la expresión mínima en forma suma de productos (producto de sumas): - En primer lugar se escogen aquellos implicantes (implicados) primos que sean esenciales, esto es, aquellos que son los únicos que cubren a algún minitérmino (maxitérmino). - Se verifica si con estos se cubren todos los minitérminos (max- itérminos) de la función. Si es así, ya se tiene la función mínima. - En caso contrario se añaden implicantes primos no esenciales hasta conseguir la cobertura. En esta elección se escogen en primer lugar aquellos implicantes (implicados) primos que cubran a más minitérminos (maxitérminos) y que contengan el menor número de literales. Un método sistemático es el Método de Petri. Simplificación de funciones booleanas. Método tabular. Método de Quine-McCluskey Sistemas electrónicos digitales Material de apoyo didáctico Método de Quine-McCluskey • Es un método sistemático que permite obtener una solucion exacta al problema de la minimización de funciones booleanas. • Se aplica principalmente a problemas con mayor número de varia- bles de entrada que los tratados con los mapas de Karnaugh. • Define un procedimiento adecuado para ser programado y ejecutado por ordenador. • El método consta de dos pasos: A.- Busqueda exahustiva de todos los implicantes primos de la fun- ción dada. 1.-Se obtiene una lista de todos los minterm que hacen uno a la fun- ción y se ordenan por grupos de acuerdo con el número de unos que posee su representación binaria. 2.- Se compara sistemáticamente cada minitermino de la lista perteneciente a un grupo con todos los demás pertenecientes al grupo siguiente, para buscar adyacencias de primer orden. 3.- Se crea una lista con grupos de adyacencias. Los minterms que formen adyacencias son borrados de la lista de minterm. 4.- Se comparan sistemáticamente cada adyacencia de primer orden de un grupo, con todas las demás de la lista del siguiente grupo, para buscar adyacencias de 2º orden. 5.- Las nuevas adyacencias encontradas se anotan en una nueva lista y se borran de la de primer orden. 6.- El proceso se repite con las nuevas listas de adyacencias de orden superior hasta que llegado un orden de adyacencias, no se pueden encontrar adyacencias de orden superior. Los elementos de cada lista que queden sin eliminar constituiran el conjunto de impli- cantes primos de la función. Simplificación de funciones booleanas. Método tabular. Método de Quine-McCluskey Sistemas electrónicos digitales Material de apoyo didáctico B.- Elección de un conjunto mínimo de implicantes primos que proporcione una expresión mínima, con el menor número de literales. Esta selección se realiza a partir de la tabla de implicantes primos. En esta tabla cada implicante primo ocupa una fila y cada miterm una columna. La tabla se rellena marcando con una X la celda que corresponde a columna de minterm cubierto por el implicante fila. El procedimiento de busqueda de la expresión minima es el siguiente: 1.- Se buscan las columnas que tengan una sola X. Los implicantes primos que cubre a estos minterm son esenciales y por tanto deben ser seleccionados para la expresión mínima. 2.- Se tachan todas las columnas correspondientes a minterm cubier- tos por los implicantes primos esenciales. 3.- Se mira en la tabla si quedan columnas sin tachar. Si es así hay que escoger algún implicante primo no esencial para cubrirlas, siguiendo el criterio de usar el menor número de ellos y el menor número de literales. Un método para realizar esta selección puede ser el de Petrick. Veamos un ejemplo: F w x y z, , ,( ) 1 3 4 6 7 8 9 10 11 14 15, , , , , , , , , ,( ) 4 ∑= Simplificación de funciones booleanas. Método tabular. Método de Quine-McCluskey Sistemas electrónicos digitales Material de apoyo didáctico En primer lugar realizaremos la búsqueda sistemática de todos los implicantes primos de la función, para ello contruimos la sguiente tabla, en la que se ordenan los minitérminos de la función según el número de unos de su representación binaria: Tabla 3: Busqueda de implicantes primos, Paso A Paso B Paso C Indice del minterm wxyz Indices de los minterms wxyz Indices de los minterms wxyz 1 0001 1,3 1,9 00-1 -001 1,3,9,11 1,9,3,11 -0-1 -0-1 4 0100 4,6 01-0 8 1000 8,9 8,10 100- 10-0 8,9,10,11 8,10,9,11 10-- 10-- 3 0011 3,7 3,11 0-11 -011 3,7,11,15 3,11,7,15 --11 --11 6 0110 6,7 6,14 011- -110 6,7,14,15 6,14,7,15 -11- -11- 9 1001 9,11 10-1 10 1010 10,11 10,14 101- 1-10 10,11,14,15 10,14,11,15 1-1- 1-1- 7 0111 7,15 -111 11 1011 11,15 1-11 14 1110 14,15 111- 15 1111 PF = { }xz wx yz xy wy wxz,,,,, Simplificación de funciones booleanas. Método tabular. Método de Quine-McCluskey Sistemas electrónicos digitales Material de apoyo didáctico Construiremos la tabla de implicantes primos para buscar los esen- ciales y obtener la función mínima. Vemos que con los implicantes primos esenciales no se cubren los minitérmi- nos m7, m14, m15. Por tanto para obtener la función mínima hay que añadir a los implicantes primos esenciales, aquellos implicantes primos necesarios para cubrir estos minitérminos rstantes. La solución optima es escoger el implicante primo xy que por si solo cubre a los tres minterm. La función minima resulta: Tabla 4: Tabla de implicantes primos Implicantes primos Miniterminos que hacen uno la funcion F Expresión Indices 1 3 4 6 7 8 9 10 11 14 15 1,3,9,11 E X X X X 8,9,10,11 E X X X X 3,7,11,15 X X X X 6,7,14,15 X X X X 10,11,14,15 X X X X 4,6 E X X Esenciales E E E Columnas cubiertas C C C C C C C C xz wx yz xy wy wxz F w x y z, , ,( ) xz wx xy wxz+ + += Simplificación de funciones booleanas. Metodo algebraico. Sistemas electrónicos digitales Material de apoyo didáctico Definiciones: Sean F(x1,...xn) y G(x1,...xn) dos funciones booleanas. Si F cubre a G, se dice que G implica a F, o que G es implicante de F. Se dice que F cubre a G si siempre que G toma el valor 1, F tambien lo toma. F G⊇( ) Si se cumple G F⊇( )F G⊇( ) y , se dice que F y G son equivalentes Ej: F x y z, ,( ) 0 1 3 4, , ,( ) 3 ∑= G x y z, ,( ) 0 3,( ) 3 ∑= F G⊇ Ej: F w x y z, , ,( ) wx yz+= H w x y z, , ,( ) wxy= F H⊇ F w x y z, , ,( ) wxy wxy yz+ += Un producto de literales p se dice que es implicante primo de una función booleana F, sii implica a F y además, cualquier subproducto (producto con menos literales) obtenido de p, no es implicante de F. Vamos a llamar PF al conjunto de los implicantes primos de F. Ej: F w x y z, , ,( ) wxy wxy yz+ += a) No son implicantes primos porque existe el subproducto wx que es b) Si es implicante primo porque implica a F y ni y,ni z son implicantes a) b) implicante de F. wx si es implicante primo porque implica a F y ni w , ni x son implicantes de F. PF = {wx , yz } de F. Simplificación de funciones booleanas. Metodo algebraico. Sistemas electrónicos digitales Material de apoyo didáctico Tabla 1: Procedimiento sistemático para la obtención de una expresión mínima en forma de suma de productos de una función booleana. 1º Obtener el conjunto de implicantes primos. 2º Seleccionar, de entre éstos, los implicantes primos esenciales, y formar una expresión mínima. 3º Eliminar del conjunto de implicantes primos aquellos que cubran minitérminos que ya estén cubietos por los implicantes primos esenciales. 4º Verificar que todos los minitérminos que hacen uno a la función dada están cubiertos por la expresión mínima obtenida, y si no es así, añadir a ésta los implicantes primos necesarios para conseguirlo. Teorema: Cualquier expresión irreducible en forma suma de productos de una función booleana F resulta de la unión de implicantes primos de F. Definición: Un implicante primo de una función F se dice que es esencial si cubre al menos a un minitérmino de la función que no puede ser cubierto por ningún otro implicante primo de la misma. Ej: F x y z t, , ,( ) 0 2 6 7 8 10 14 15, , , , , , ,( ) 4 ∑= PF = { yt , zt , yz } yt yz zt cubre a los minitérminos {0,2,8,10} cubre a los minitérminos {2,6,10,14} cubre a los minitérminos {6,7,14,15} yt yz son implicantes primos esenciales, Simplificación de funciones booleanas. Metodo algebraico. Sistemas electrónicos digitales Material de apoyo didáctico Definiciones: Se dice que G es implicado por F, si simpre que G toma el valor 0, F Ej: F w x y z, , ,( ) w x+( ) y z+( )⋅= H w x y z, , ,( ) w x y+ += F w x y z, , ,( ) w x y+ +( ) w x y+ +( ) y z+( )⋅ ⋅= Una suma de literales s se dice que es implicado primo de una función booleana F, sii es implicado de F y además, cualquier subsuma (suma con menos literales) obtenida de s, no es implicado de F. Vamos a llamar SF al conjunto de los implicados primos de F. Ej: F w x y z, , ,( ) w x y+ +( ) w x y+ +( ) y z+( )⋅ ⋅= a) No son implicados primos porque existe la subsuma w+x que es b) Si es implicado primo, porque es implicado por F, y además, ni y, a) b) implicado de F. w+x si es implicado primo porque es implicado por F y además, ni w , ni x son implicados de F. SF = {w+x , y+z } ni z son implicados de F. tambien lo toma. H es implicado por F Simplificación de funciones booleanas. Metodo algebraico. Sistemas electrónicos digitales Material de apoyo didáctico Tabla 2: Procedimiento sistemático para la obtención de una expresión mínima en forma de producto de sumas de una función booleana. 1º Obtener el conjunto de implicados primos. 2º Seleccionar, de entre éstos, los implicados primos esenciales, y formar una expresión mínima. 3º Eliminar del conjunto de implicados primos aquellos que estén implicados por maxitérminos que ya lo estén por los implicados primos esenciales. 4º Verificar que todos los maxitérminos que hacen cero a la función dada están implicados por la expresión mínima obtenida, y si no es así, añadir a ésta los implicados primos necesarios para conseguirlo. Teorema: Cualquier expresión irreducible en forma producto de sumas de una función booleana F resulta del producto de implicados primos de F. Definición: Un implicado primo de una función F se dice que es esencial, si es implicado por un maxitermino de la función, que no puede implicar a ningún otro implicado primo de la misma. Ej: F x y z t, , ,( ) 1 3 4 5 9 11 12 13, , , , , , ,( ) 4 ∏= SF = { y+z , y+t , z+t } y+z z+t y+t implicado por los maxitérminos {4,5,12,13} son implicados primos esenciales, implicado por los maxitérminos {1,5,9,13} implicado por los maxitérminos {1,3,9,11} y+z y+t Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico • Los Mapas de Karnaugh son tablas de verdad construidas de tal manera que minitérminos (o maxitérminos) adyacentes ocupan una posición adyacente en la tabla. • Son especialmente útiles para la simplificación manual de funciones booleanas de hasta seis variables, porque permiten encontrar los implicantes primos, e identificar los esenciales, por simple inspección ocular. • Vamos a estudiar los distintos casos: x y 0 1 0 1 2 3 0 1 Mapa de Karnaugh de dos variables mo m1 m2 m3 xy= xy= xy= xy= Adyacencias LógicaFísica x y 0 1 0 1 2 3 0 1 x y 0 1 0 1 2 3 0 1 Ej: XOR(x,y) 0 1 1 0 0 1 1 1 OR(x,y) XOR x y,( ) xy xy+= OR x y,( ) y x+= POR = {x , y } Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico Mapa de Karnaugh de tres variables x yz 00 01 11 10 0 1 3 2 4 5 67 0 1 Ejemplo1: x yz 00 01 11 10 0 1 3 2 4 5 67 0 1 F xyz( ) 0 2 3 6, , ,( ) 3 ∑= 1 11 1 0 0 0 0 xz yz xy PF = { xzyz xy }, , Todos los implicantes primos son esenciales. La expresión mínima será: F xyz( ) yz xy xz+ += Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico Mapa de Karnaugh de cinco variables Ejemplo: F x y z t u, , , ,( ) = 1 3 5 9 10 11 12 13 14 15 18 19 21 23 25 26 27 28 29 30 31, , , , , , , , , , , , , , , , , , , ,( ) 5 ∑ xy ztu 00 01 11 10 000 001 011 010 0 1 3 2 110 111 101 100 16 17 19 18 24 25 27 26 8 9 11 10 6 7 5 4 22 23 21 20 30 31 29 28 14 15 13 12 0 1 1 00 0 1 1 1 1 1 10 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 xy ztu 00 01 11 10 000 001 011 010 0 1 3 2 110 111 101 100 16 17 19 18 24 25 27 26 8 9 11 10 6 7 5 4 22 23 21 20 30 31 29 28 14 15 13 12 0 1 1 00 0 1 1 1 1 1 10 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 Adyacencias de orden 3 yt yzyu Adyacencias de orden 2 no cubiertas por adycencias de orden 3. xtu ztu ztu xzu xzuxzt xtu ztu xzu xzt xzu xtu xtu ztu Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico Mapa de Karnaugh de cinco variables Ejemplo (continuación) PF = { ztu xzu xzt xzu xtu xtu ztu yt yz yu yt yu yz xzu xzt xzu xtu xtu ztu ztu,,,,,,,,, } Vamos a ver cuales son esenciales y cuales no. minterm de F PF 1 3 5 9 10 11 12 13 14 15 18 19 21 23 25 26 27 28 29 30 31 x x x x x x x x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x yt yz xzt yu yz Tomando los implicantes primos esenciales quedan sin cubrir los miniterminos xy ztu 00 01 11 10 000 001 011 010 0 1 3 2 110 111 101 100 16 17 19 18 24 25 27 26 8 9 11 10 6 7 5 4 22 23 21 20 30 31 29 28 14 15 13 12 0 1 1 00 0 1 1 1 1 1 10 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 m1,m3,m5,m21,m23 a) b) c) d) e) f) g) h) i) j) Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico Mapa de Karnaugh de cinco variables Ejemplo (continuación) Vamos a ver las posibilidades que hay de cubrir los minitérminos restantes. - m1 puede ser cubierto por los implicantes primos d) y h) - m3 puede ser cubierto por los implicantes primos d) y j) - m5 puede ser cubierto por los implicantes primos h) y i) - m21 puede ser cubierto por los implicantes primos f) y i) - m23 puede ser cubierto por los implicantes primos f) y g) Se pueden dar los siguientes casos: (d,f,h) , (d,f,i) , (f,h,j) , (d,i,g). Método de Petrick. C d f g h i j, , , , ,( ) d h+( ) d j+( ) h i+( ) f i+( ) f g+( )⋅ ⋅ ⋅ ⋅= C d f g h i j, , , , ,( ) d dj dh hj+ + +( ) hf hi fi i+ + +( ) f g+( )⋅ ⋅= C d f g h i j, , , , ,( ) d hj+( ) hf i+( ) f g+( )⋅ ⋅= C d f g h i j, , , , ,( ) dfh di fhj hij+ + +( ) f g+( )⋅= C d f g h i j, , , , ,( ) dfh dfi fhj fhij dfgh dgi fghi ghij+ + + + + + +( )= C(d,f,g,h,i,j) muestra todas las posiblidades de escoger los implicantes primos para que se cubran todos los minitérminos que faltan. De todas las posibilidades se escoge la que necesite menor número de implicantes primos, y menor número de literales. Estas son las elegidas arriba. Como todas contienen el mismo número de literales existen cuatro expresiones que cumplen el criterio de minimización: F x y z t u, , , ,( ) yz yt yu xzt xzu xzu xtu+ + + + + += F x y z t u, , , ,( ) yz yt yu xzt xzu xtu ztu+ + + + + += F x y z t u, , , ,( ) yz yt yu xzt xzu xtu ztu+ + + + + += F x y z t u, , , ,( ) yz yt yu xzt xzu xzu ztu+ + + + + += C d f g h i j, , , , ,( ) dfh dfi fhj dgi fghi ghij+ + + + +( )= Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico Expresiones mínimas en forma producto de sumas y mapas de Karnaugh. Ejemplo: F x y z t, , ,( ) 0 2 4 6 7 8 16 17 20 22 24, , , , , , , , , ,( ) 5 ∏= xy ztu 00 01 11 10 000 001 011 010 0 1 3 2 110 111 101 100 16 17 19 18 24 25 27 26 8 9 11 10 6 7 5 4 22 23 21 20 30 31 29 28 14 15 13 12 0 1 1 00 0 1 1 1 1 1 10 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 x y u+ +( ) y z u+ +( )z t u+ +( ) y t u+ +( )x y z t+ + +( ) x y z t+ + +( ) SF = { x y u+ +( ) y z u+ +( ) y t u+ +( ) z t u+ +( ), , ,x y z t+ + +( ) x y z t+ + +( ), } a) b) c) d) e)f) Los implicados primos esenciales son a, b, d, e, f , y entre todos cubren todos los maxitérminos de la función. La expresión mínima resulta: F x y z t u, , , ,( ) = x y u+ +( ) y z u+ +( ) z t u+ +( ) x y z t+ + +( ) x y z t+ + +( )⋅ ⋅ ⋅ ⋅= Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico Funciones incompletamente definidas. • Se llama así a las funciones booleanas que no están definidas para todas las combinaciones de entrada, ésto es, su dominio es un subconjunto de todas las posibles combinaciones de las variables de entrada. • En su tabla de verdad solo aparecen las combinaciones que están definidas. • En los mapas de Karnaugh, las combinaciones no definidas suelen represen- tarse mediante en simbolo X, (indiferencia o indeterminación) y será utili- zado como 1 o 0 , según convenga, a la hora de buscar los implicantes o implicados primos de la función, durante el proceso de simplificación de fun- ciones. • En la representación en forma canónica, se indica que minterms (o maxterm) no están especificados, como se muestra en el siguiente ejemplo. Ej: - Se indica que la función toma el valor 1 para los minterm de tres variables m1, m2, m3. Además la función no está especificada para los minterm m4 y m5. Ej: - Se indica que la función toma el valor 0 para los maxterm de tres variables M2, M4, M5. Además la función no está especificada para los maxterm M0 y M3. • Dos funciones booleana incompletamente especificadas son equivalentes si, o bien en su tabla de verdad, o bien en su forma canónica, coinciden para aquellas combinaciones de entrada especificadas en ambas. • Dos expresiones algebraicas mínimas, obtenidas a partir de una función incompletamente especificada, no tienen por que ser equivalentes entre sí, y solo está garantizado que coinciden para aquellas combinaciones de entrada que están especificadas en la función de partida. F x y z, ,( ) 1 2 3, ,( ) 3 ∑ 4 5,( ) ∅ ∑+= F x y z, ,( ) 2 4 5, ,( ) 3 ∏ 0 3,( ) ∅ ∏⋅= Simplificación de funciones booleanas. Mapas de Karnaugh. Sistemas electrónicos digitales Material de apoyo didactico Ej: Obtener una expresión booleana mínima para un circuito que detecte si un dígito BCD natural es multiplo de 3. La salida del circuito no está especi- ficada para los casos en que la combinación de entrada no corresponda con un dígito BCD. Sea la entrada un nº BCD N=A3A2A1A0. La forma canónica de la función pedida es: Usamos un mapa de Karnaugh de cuatro variables para obtener una expresión mínima. F A3 A2 A1 A0, , ,( ) 0 3 6 9, , ,( ) 4 ∑ 10 11 12 13 14 15, , , , ,( ) ∅ ∑+= A3A2 A1A0 00 01 11 10 00 01 11 10 0 1 3 2 4 5 67 8 9 1011 12 13 1415 1 1 1 1 x x x x x x 0 0 0 0 0 0 A3A2 A1A0 00 01 11 10 00 01 11 10 0 1 3 2 4 5 67 8 9 1011 12 13 1415 1 1 1 1 x x x x x x 0 0 0 0 0 0 Minimización por unos. Obtener expresion SDP. Minimización por ceros. Obtener expresion PDS. a) b) c)d) a)b)c) d) e) a) b) c) d) A3A0 A2A1A0 A2A1A0 A2A3A1A0 PF ={ } a) b)c) d)A2 A0+ A2 A1+A3 A0+ A3 A1 A0+ +SF ={ }e) A2 A1 A0+ + Todos los implicantes primos son esenciales. Todos los implicados primos son esenciales. Simplificación de funciones booleanas. Método tabular. Método de Quine-McCluskey Sistemas electrónicos digitales Material de apoyo didáctico En primer lugar realizaremos la búsqueda sistemática de todos los implicantes primos de la función, para ello contruimos la sguiente tabla, en la que se ordenan los minitérminos de la función según el número de unos de su representación binaria: Tabla 3: Busqueda de implicantes primos, Paso A Paso B Paso C Indice del minterm wxyz Indices de los minterms wxyz Indices de los minterms wxyz 1 0001 1,3 1,9 00-1 -001 1,3,9,11 1,9,3,11 -0-1 -0-1 4 0100 4,6 01-0 8 1000 8,9 8,10 100- 10-0 8,9,10,11 8,10,9,11 10-- 10-- 3 0011 3,7 3,11 0-11 -011 3,7,11,15 3,11,7,15 --11 --11 6 0110 6,7 6,14 011- -110 6,7,14,15 6,14,7,15 -11- -11- 9 1001 9,11 10-1 10 1010 10,11 10,14 101- 1-10 10,11,14,15 10,14,11,15 1-1- 1-1- 7 0111 7,15 -111 11 1011 11,15 1-11 14 1110 14,15 111- 15 1111 PF = { }xz wx yz xy wy wxz,,,,, Simplificación de funciones booleanas. Método tabular. Método de Quine-McCluskey Sistemas electrónicos digitales Material de apoyo didáctico Construiremos la tabla de implicantes primos para buscar los esen- ciales y obtener la función mínima. Vemos que con los implicantes primos esenciales no se cubren los minitérmi- nos m7, m14, m15. Por tanto para obtener la función mínima hay que añadir a los implicantes primos esenciales, aquellos implicantes primos necesarios para cubrir estos minitérminos rstantes. La solución optima es escoger el implicante primo xy que por si solo cubre a los tres minterm. La función minima resulta: Tabla 4: Tabla de implicantes primos Implicantes primos Miniterminos que hacen uno la funcion F Expresión Indices 1 3 4 6 7 8 9 10 11 14 15 1,3,9,11 E X X X X 8,9,10,11 E X X X X 3,7,11,15 X X X X 6,7,14,15 X X X X 10,11,14,15 X X X X 4,6 E X X Esenciales E E E Columnas cubiertas C C C C C C C C xz wx yz xy wy wxz F w x y z, , ,( ) xz wx xy wxz+ + += Simplificación de funciones booleanas. Método tabular. Método de Quine-McCluskey Sistemas electrónicos digitales Material de apoyo didáctico