Trabajo Final de Lógica y Semánticas Formales (página 2)

4. Minimización De Funciones Booleanas

El primer problema, al minimizar una función dada, es decir, al encontrar la expresión "más simple" que representa esta función, es el de definir exactamente cuáles son los criterios para determinar hasta qué punto una expresión es simple. Llegar a esta definición no siempre es sencillo, pues se pueden tener dos expresiones que representen la misma función booleana, con el mismo número de ocurrencias de cada variable y el mismo número de operaciones, con lo cual ¿quién puede decir cual de las dos es la más simple? El problema se hace aún más complicado cuando se incrementa el número de operaciones básicas, como es a menudo el caso, cuando queremos hallar los valores de alguna función. Supondremos aquí que la "forma más simple" significa la "forma más simple en forma normal disyuntiva", y discutiremos la técnica de los mapas o diagramas de Karnaugh. Como estamos trabajando en un álgebra booleana, se podría realizar en teoría una simplificación enteramente algebraica, utilizando las leyes de absorción y relaciones análogas. Pero la dificultad estriba en estar seguro de que se han tomado en cuenta todas las formas posibles de aplicar las reglas simplificadoras. Las técnicas que se han desarrollado para ayudar a la simplificación son métodos de ordenar la información sobre la función que permita ver todas estas posibilidades.

Un diagrama de Karnaugh es en realidad un diagrama de Venn con las distintas regiones arregladas como cuadrados dentro de un rectángulo. Como tales, tienen los mismos defectos que tienen los diagramas de Venn: para más de seis variables los mapas de Karnaugh se hacen demasiado complicados para que puedan ser útiles, e incluso para cinco o seis variables pierden ya mucha de su utilidad. Los mapas de Karnaugh para de una a cuatro variables se presentan en las figuras 1.1 a 1.4. Cada cuadrado representa el producto de las coordenadas dadas sobre los bordes del rectángulo. Por ejemplo, el cuadrado rotulado "a" en la figura 1.3 representa al término x’yz y el rotulado con "b" en la figura 1.4 representa el término wx’y’z’. De acuerdo con el axioma de conmutatividad, el orden de las letras de variables no es importante.

Se conviene en que cada cuadrado, en un mapeo de Karnaugh, contenga un "1", si el término representado por ese cuadrado se requiere que esté presente en una representación como suma de productos de la función, o un "0" si el término ha de estar ausente, o una "d" (de la expresión inglesa "don´t care", "da lo mismo"), si la presencia o ausencia del término es indiferente. Es frecuente no escribir explícitamente los ceros. El método para el uso de un mapa tal, consiste en intentar cubrir todos los 1 con el menor número posible de rectángulos que representan productos de elementos.

Por ejemplo, en la figura 1.5 (donde se usa un sistema simplificado de coordenadas) los dos cuadrados marcados con "a" representan el término wxy’z’ + wxyz’, que pueden simplificarse a wxz’ por el uso de las leyes distributivas. Análogamente, los cuadrados marcados con "b" representan al término w’xy’, y los cuatro cuadrados marcados con "c"corresponden al término yz. Sin embargo, los dos cuadrados marcados con "d"corresponden a wx’yz’ + w’x’y’z’, que no pueden ser simplificados más. Y, en general, un grupo de tres cuadrados, por ejemplo, no tiene ningún significado. Los agrupamientos significativos siempre consisten en cuadrados contiguos, con tal que consideremos los lados opuestos de los mapas como continuos. Así, en la figura 1.6, los

Cuadrados marcados "a", "b" y "c" representan, respectivamente, los términos x’y’z, yz’ y y’z’. Dentro de éstas regiones cada cuadrado debe contener o un 1 o una d. Ningún cuadrado puede contener un 0, puesto que éstos representan términos explícitamente excluidos; no todos los d deben cubrirse, puesto que nos es indiferente que los términos correspondientes estén o no presentes Ejemplo A: Consideremos la función cuyo mapa K viene dado en la figura 1.7. Hemos dibujado sobre este mapa tres rectángulos que cubren los 1 y representan los términos wxz’, xy y w’x’z. Nótese que el cuadrado marcado "a" podría haberse usado por sí mismo, pero, al combinarlo con el cuadrado que está debajo de él, obtenemos el término más simple wxz’ en lugar del wxy’z’. Este cuadrado de más abajo del "a" está incluido en los dos términos; pero no importa, por el axioma de idempotencia. Los dos cuadrados marcados "b" representan el producto w’yz, pero no es necesario incluir este término ya que los cuadrados están cubiertos por otros términos. Ejemplo B: Examinamos ahora una situación con términos "indiferentes", que representamos en la figura 1.8. Tales términos pueden surgir porque, en una aplicación particular, sabemos que ciertos productos nunca aparecerán. Hemos mostrado aquí una cubierta de los 1, que representa la función por la expresión xz + yz’. Nótese que tres de las d están tratadas unos y las otras dos como ceros.

Fundamentos de la metodología La metodología de simplificación de funciones a través de los diagramas de Karnaugh, a pesar de ser cuasi intuitiva, está fundamentada a través del álgebra de Boole, en la lógica de proposiciones. Como se ha visto anteriormente, se puede hacer una correlación entre el álgebra de Boole, y la lógica proposicional. En la lógica, cada término de una forma plena, representa una combinación de todas las posibles de las variables. Del mismo modo, se puede trasladar este concepto a los mapas K, entendiendo que cada cuadrado interior, está claramente identificado y al mismo tiempo se diferencia de los otros, con una única combinación de las variables (sin repetición) que contempla el mapa. De este modo, el diagrama de n variables está contemplando todas los posibles mintérminos de una forma plena de n variables. En otras palabras, cada cuadrado interior de un diagrama K de n variables representa una fila de una tabla de verdad de una forma enunciativa de n variables. El método hace una asignación de valores a cada celda del diagrama, según se necesite esté presente o no en la fórmula a simplificar. En la lógica, se puede interpretar este paso como la selección de aquellos mintérminos que podrían resultar verdaderos o falsos para alguna de todas las asignaciones posibles. Se continúa agrupando todos aquellos cuadrados que hallan quedado marcados con un 1, y que estén en posiciones contiguas o en los lados opuestos de un mapa, de tal forma que se constituyan grupos de una cantidad igual a una potencia de dos. Esto debe ser así, ya que dos celdas con un lado en común o dos celdas que se encuentran en lados opuestos de un mapa, tienen como coordenadas las mismas variables, excepto una. La variable en que se diferencia, aparece complementada en una celda y sin complementar en la otra. Así, se puede hacer uso de los axiomas de complementación, del elemento neutro y de idempotencia; logrando como resultado la simplificación de las dos celdas en cuestión a una sola. Se puede realizar una interpretación similar para el caso en que se trabaja con dos grupos de celdas. Éstos grupos de celdas, deben contener un número de celdas igual a una potencia de dos, en forma similar a la estructura de las columnas de una tabla de verdad, de manera que se pueda aplicar el axioma de complementación. En las tablas de verdad, una variable cambia el valor de su asignación cada n veces, siendo n una potencia de dos. En un grupo de n celdas, la variable que se simplifica debe haber cambiado 2n-1 o menos veces su asignación, es decir, debe poder ser ubicada a la derecha de alguna/s otra/s en una tabla de verdad; lo cual no sucedería si se eligieran grupos de celdas de una cantidad distinta a la establecida. El uso de asignaciones "don´t care" responde a un hecho electrónico. Como la simplificación de funciones booleanas se utiliza para el diseño de circuitos, se aclara que cada uno de estos circuitos tiene una salida que se interpreta como un valor de verdad igual a la salida de la función que calcula. Hay ocasiones en que esta salida no importa para ciertas condiciones, es decir para ciertas asignaciones para las variables, sea la que fuere. En ese caso, es necesario tener una asignación que permita sacar provecho de esta condición, para lo cual se usa "d".

5. Conclusión

La semejanza existente entre el álgebra booleana y la lógica proposicional, nos permite realizar una relación entre las funciones existentes en una y en otra. Así, se pueden realizar métodos para trabajar con funciones de boole, que resulten en una ayuda, por ejemplo, para la etapa de diseño del hardware de una computadora los cuales se basan en conceptos que se obtienen a partir del desarrollo de las dos áreas. El método presentado es de mucha utilidad cuando se trabaja con pocas variables, pero deja de serlo cuando este número crece. Se deja como sugerencia para algún otro trabajo, el análisis de técnicas alternativas para un número mayor de variables, como podría ser el desarrollado por W. V. Quine y E. J. McCluskey Jr.; o en todo caso, la creación de algoritmos con esta finalidad.

6. Bibliografía

• Libros:
• • Naishtat, Francisco S.

"Lógica para Computación" – Editorial Eudeba, Buenos Aires. ã 1986 Páginas: 99 – 100

• Korfhage, Robert

"Lógica y Algoritmos" – Editorial Limusa Wesley – D.F. México. ã 1970 Páginas: 31 – 43

• Trejo, César A.

"Matemática Elemental Moderna" – Editorial Eudeba, Buenos Aires. ã 1968 Páginas: 189 – 193

• Grassmann, Winfried Karl,

Tremblay, Jean-Paul "Matemática Discreta y Lógica" – Editorial Prentice Hall, Madrid. ã 1996 Páginas: 34 – 38, 110 – 112

• Hamilton, A. G.

"Lógica para matemáticos" – Editorial Paraninfo, Madrid. ã 1981 Páginas: 9 – 28

• Internet:
• • http://www.mat.usach.cl/histmat/html/bool.html.

Autor:

Leonardo Arias Paz Santiago del Estero, Argentina