Regístrate | Conectar
El Tamiz Libros Recursos Series Únete 10 Users Online
Skip to content

Minimización de Funciones Lógicas. El algoritmo de Quine–McClusky explicado y mejorado. El documento completo.

Durante los últimos días he publicado una serie de cinco artículos sobre el problema de la minimización de funciones lógicas, y en concreto sobre el algoritmo de Quine-McClusky, reputado en la profesión como el procedimiento de referencia para resolver este tipo de problemas: dada una expresión lógica, encontrar la expresión equivalente, o sea, con su misma tabla de verdad, que sea mínima, es decir, que contenga el menor número posible de variables individuales.

Tratándose de un algoritmo publicado en 1956, ha sido estudiado y utilizado profusamente durante sus casi setenta años de vida. Y sin embargo, todavía es posible encontrar formas de mejorar este algoritmo para reducir los recursos informáticos que requiere o simplemente para que efectivamente encuentre la función lógica mínima equivalente a una dada, lo que no siempre hace.

En esos artículos fui paulatinamente describiendo el algoritmo en su diferentes pasos, alguno de ellos nuevo en el sentido de que no he encontrado referencias sobre ellos en la Red, otros idénticos a lo expresado en la literatura, y otros, por fin, con modificaciones sobre lo expresado en dicha literatura sobre el algoritmo.

En este artículo final de la serie presento un único documento con el compendio de los cinco artículos; he retocado algunas frases para eliminar el estilo derivado de estar publicados en una serie de artículos en la web, pero el documento sigue las mismas pautas y el mismo orden de exposición seguido en los artículos de la serie.

He aquí el documento completo.

Espero que os sirva.

Disfrutad de la vida mientras podáis.

 

Minimización de Funciones Lógicas. El algoritmo de Quine–McClusky explicado y mejorado-V

Éste de hoy es el quinto y último artículo de esta serie sobre el algoritmo de Quine-McClusky.

En el anterior artículo de esta serie sobre minimización de funciones lógicas, el cuarto, dedicado a definir el Paso 7 del algoritmo, describí cómo son las alternativas que se citan habitualmente en la literatura sobre Quine-McClusky, sobre todo el método de Petrik, que procuré definir con la máxima precisión debido a que, aunque es sencillo de implementar, no es tarea tan sencilla comprender en qué se basa y cómo funciona.

En este quinto y definitivo artículo describiré una alternativa viable y muy interesante a dicho método de Petrik, una alternativa que proviene de un área distinta de la informática, pero perfectamente aplicable a nuestro problema de minimizar expresiones lógicas.

Aquí podéis encontrar el PDF del quinto y último artículo.

Y con él acaba la serie. Yo no alcanzo para llegar más allá.

Espero que toda la información que he vertido en estos artículos os haya sido de utilidad y que, quizás, os haya picado el gusanillo de mirar con otros ojos a algoritmos que están establecidos en nuestra profesión como si fueran el Santo Grial, pero que, quién sabe, quizás sean susceptibles de mejorarse, como hemos visto que le ocurre al venerable algoritmo de Quine-McClusky.

Disfrutad de la vida mientras podáis.

Minimización de Funciones Lógicas. El algoritmo de Quine–McClusky explicado y mejorado-IV

En el anterior artículo de esta serie discutí la razón por la que el algoritmo de Quine-McClusky no siempre devuelve la expresión mínima correspondiente a la forma canónica original, que es la información de entrada para el algoritmo.

Efectivamente, en un importante porcentaje de casos, que puede acercarse hasta el 50% en cuanto la forma canónica tiene un cierto y relativamente modesto tamaño, el algoritmo tal como se define en la literatura no encuentra la expresión mínima solicitada. Y además, en dicho artículo he demostrado que de hecho hay tantas formas canónicas de una cierta longitud en las que el algoritmo tradicional encuentra la expresión mínima, como aquellas en las que no la encuentra y es preciso ejecutar el método alternativo para hallar dicha solución mínima absoluta.

En ese tercer artículo había indicado el modo de solventar esta engorrosa circunstancia para obtener siempre, siempre la expresión mínima correspondiente a la función original.

Pero algo faltaba: la definición del algoritmo no estaba aún completa, pues por motivos didácticos había postergado la definición del penúltimo paso del algoritmo, el Paso 7, que es el que de verdad consume cantidades ingentes de recursos informáticos para su resolución.

En los dos artículos que faltan de la serie, el de hoy, cuarto de los cinco de que se compone, y en el siguiente y último, definiré con toda la precisión de que sea capaz las diferentes alternativas para ejecutar este penúltimo paso, alternativas que, obviamente, tienen cada una de ellas sus ventajas e inconvenientes.

Aquí podéis encontrar el PDF del cuarto artículo.

Hasta el próximo, que será el último de la serie.

Disfrutad de la vida mientras podáis.

Minimización de Funciones Lógicas. El algoritmo de Quine–McClusky explicado y mejorado-III

El anterior artículo de esta serie sobre minimización de  funciones lógicas terminaba con una afirmación cuanto menos sorprendente: el algoritmo de Quine-McClusky no siempre devuelve la expresión mínima correspondiente a la forma canónica original, que es la única entrada para el algoritmo.

En éste de hoy, el tercero de los cinco de que se compone la serie, se explica por qué en ocasiones (en muchas ocasiones) el algoritmo tal como está definido en la literatura no encuentra la expresión mínima, y qué se puede hacer para efectivamente encontrarla siempre.

Aquí podéis encontrar el PDF de este tercer artículo.

Hasta el próximo.

Disfrutad de la vida mientras podáis.

Minimización de Funciones Lógicas. El algoritmo de Quine–McClusky explicado y mejorado-II

Tal como avancé en el artículo anterior de esta serie, en este artículo de hoy, el segundo, voy a definir con el máximo detalle que pueda y sepa los intríngulis de algoritmo de Quine-McClusky, excepto su penúltimo paso, que por sus características especiales describiré más adelante.

He aquí el PDF de este segundo artículo.

El último párrafo del artículo es, cuanto menos, intrigante… en el tercer artículo de la serie se resolverá el misterio. Y las conclusiones serán, seguramente, sorprendentes.

Hasta entonces, en el próximo artículo.

Disfrutad de la vida mientras podáis.

Minimización de Funciones Lógicas. El algoritmo de Quine–McClusky explicado y mejorado-I

Este artículo es el primero de una serie de cinco que versará sobre el algoritmo de Quine-McClusky.

Se trata del algoritmo de referencia utilizado para minimizar expresiones lógicas. Se conoce desde hace cerca de 70 años y está firmemente establecido en la profesión informática como la solución definitiva para realizar esa importante función, a saber, determinar cuál es la expresión booleana que, siendo idéntica a otra dada, es decir, que tiene su misma tabla de verdad, es mínima, tiene el menor número posible de términos.

Averiguar tal expresión para sustituirla en el programa donde se encuentre reduce el tiempo de ejecución de ese programa, pues para determinar el flujo del programa habrá que valorar un menor número de condiciones que en la expresión original. Y lo mismo podemos decir del diseño de circuitos: cuantas menos puertas lógicas tenga dicho circuito, más rápido será en ejecución y más barato de fabricar.

El caso es que yo he dedicado muchos meses, años, al estudio, programación y, por qué no, crítica del famoso algoritmo de Quine-McClusky, y he encontrado diferentes aspectos que podrían mejorar en algo, o quizás en bastante dicho algoritmo. De hecho, como veremos, en un importante porcentaje de casos el algoritmo no proporciona la expresión mínima absoluta correspondiente a la función dada. De ahí esta serie, donde expondré estos hallazgos para darlos a conocer a aquellos de vosotros que estéis interesados.

Si tenéis dudas sobre expresiones lógicas, álgebra de Boole y demás zarandajas que los informáticos usamos continuamente, podéis informaros en la serie sobre Eso que llamamos Lógica que escribí hace un tiempo, donde podéis encontrar los relativamente pocos conceptos lógicos que aparecerán en los artículos.

Y ahora, una información previa en cuanto al formato que tienen los artículos.

Me ha sido muy difícil transferir los artículos tal como estaban escritos en mi procesador de textos favorito al formato HTML de las páginas web de ElCedazo, pues el resultado sufría de efectos impredecibles y dejaba un formato desastroso, así que esta vez he optado por una solución completamente novedosa en ElCedazo: construir un PDF para cada artículo, que enlazaré en las diferentes entradas. No es lo normal en este sitio, ya lo sabéis, pero creedme que aquí y ahora es lo mejor para mí y para vosotros, lo más sencillo para que los cinco artículos de la serie queden razonablemente legibles.

Bien, he aquí el PDF del primer artículo, que servirá como introducción a los demás.

Hasta el próximo artículo.

Disfrutad de la vida mientras podáis.

Biografía del Universo 33 (pdf 2.0)

Hola amigos, llevo ya mucho tiempo trabajando con la serie “Biografía del Universo“. Cuando la acabé de publicar en el blog El Cedazo quede satisfecho. No acabó aquí mi interés ya que con el paso del tiempo, y las sucesivas lecturas sobre ese apasionante tema, me di cuenta que a veces el entusiasmo me había superado a la hora de escribir las entradas de la serie, no sólo “Biografía del Universo” sino también “El destino del Universo“. Había temas que se quedaron a medio camino, había grandes lagunas, había temas confusos, había algunos errores y desde entonces hay novedades y descubrimientos emocionantes. Reconozco que también había otra forma de escribir, como digo, menos entusiasta y más entendible. Con posterioridad, con “El destino del Universo”, me adentré en saber cómo podía ser su futuro. Al acabarla vi que me apetecía verla encajada en la serie Biografía. Y ya que me metía en faena consideré la necesidad de redondear la actualización del libro con alguna temática que no incorporé en el primero porque se solapaban con entradas de otros colegas en el propio El Cedazo o del blog El Tamiz, a través del cual Pedro ya nos había informado, por ejemplo, con las estrellas.

Me lancé a la tarea de mejorar lo escrito aprovechando que durante estos meses de impasse he podido leer a grandes físicos que me abrieron la amplitud de conocimiento y comprensión acerca de algunos viejos y nuevos temas.  También he añadido bloques de información complementaria que para que no interfirieran con el hilo de la biografía los he resaltado en fondo verde. Espero que no sólo haya ampliado la información sino que también le haya dado un vuelco a la calidad de la misma. El resultado es el pdf que os presento ahora, un 2.0, que sustituye al anterior, con la recomendación de que, para aquellos que quizás os descargasteis la primera hornada, lo sustituyáis también en vuestros archivos. Comento también que voy a modificar las entradas de la serie de acuerdo al texto del libro… aunque alguna entrada quede kilométrica. Ello me lleva a prescindir de los bloques temáticos que complementan el desarrollo de la biografía en el libro.

El formato sigue siendo el original, aunque ahora a crecido 224 páginas, con bloques de explicaciones complementarias, mejoras en las figuras, alguna foto espectacular de nuestros telescopios y sobre todo, espero, unas explicaciones más asequibles para los legos. Sé que esto del Universo es un mundo muy complejo por el que moverse con garantía de tener una base un tanto profunda, exige algún dolor de cabeza intelectual. No he encontrado una mejor tecla que la que os expongo, sabiendo que no llega ni a la altura de los zapatos de los grandes comunicadores de ciencia. Quizás mi objetivo (y mis virtudes) no era alcanzar precisamente eso, la divulgación, sino mi conocimiento. Pero creo que lo que yo he aprendido puede ser útil para los demás, que espero perdonen mis pocas habilidades.

Y ahí va el pdf.

El destino del Universo 8: Muerte térmica

Llegan los últimos compases en la biografía de nuestro Universo. En la entrada anterior de esta miniserie nos habíamos despedido de lo que parecía ser el receptáculo final de la materia/energía: los agujeros negros. Aunque también esos monstruos de la gravedad se nos fueron de las manos. En esta entrada continuamos con lo que pueda ser el eterno final en donde quizás solo coexistan electrones, positrones, gravitones, fotones y neutrinos de bajísima energía. Una nada cuántica.

Sigue leyendo ›

El destino del Universo 7: Hacia el infinito

La entrada anterior de esta miniserie la acabamos con esta frase: “Volvamos al año 1025 tras el Big Bang, era en la que parece que el mundo da un giro, de la construcción en las galaxias y estrellas al inicio de la degeneración de la materia oscura al que se va a unir la de los protones (si es que esos se desintegran, que está por ver). En adelante… es lo que queda. Evaporación hacia la entropía“. La función continúa.

Acto IV. La destrucción vence en el juego

Empecemos por los protones. Una de las consecuencias de la teoría de evaporación de la materia con la que filosofábamos en la entrada anterior pudiera ser que el mundo se desintegrara en radiación a través del decaimiento de los protones en su obligada búsqueda de un mínimo de energía como sistema físico. Aunque a día de hoy no se tiene ninguna constancia de ese fenómeno. Quizás sea porque no ha habido tiempo suficiente para experimentarlo: hay cálculos que plantean un amplio margen para ello, desde los 1030 a los 1037 años tras el inicio del Universo. Estamos hablando de la vida media de tan longevas partículas. Hoy estamos algo así como en el cumpleaños 1010.

Se teoriza con diversos fenómenos que expliquen el decaimiento del protón. Quizás el más típico ejemplo puede ser el que el protón se transforma en un positrón de menor masa -en el fondo se parece a un protón pequeño (de menor energía) aunque realmente es la antipartícula del electrón- más un par de energéticos fotones. Ello exige incumplir el mantenimiento del número bariónico, cosa de la que ya hablamos en la serieBiografía del Universo“, donde se hacía la misma advertencia. Sigue leyendo ›

El destino del Universo 6: ¿Inevitable?

La entrada anterior de esta miniserie  acaba con una frase lapidaria: “Nos abocamos a momentos de una total e inevitable descomposición.” Quizás la inevitabilidad sea una mera conclusión extraída de un conocimiento parcial e incompleto del mundo, quizás el mundo sea de otra manera distinta a como lo percibimos. Quizás solo percibamos lo que realmente haya sido preciso para una evolución biológica exitosa que, cual engañosa caverna de Platón, nos sugiere que el tiempo tiene una dirección preferente fijada por el desorden. Esa parece ser la irrefutablemente útil realidad. Aunque me gustaría matizarla. Este capítulo va de reflexiones.

La eterna inquietud ante el misterio de qué es lo que hay afuera. El pie de la ilustración reza: “Un misionero medieval cuenta que había encontrado el lugar en el que el cielo y la Tierra se tocan”. El grabado Flammarion es una famosa ilustración aparecida en el libro de Camille Flammarion “L’Atmosphere: Météorologie Populaire” (París, 1888) en su página 163 (Imagen: dominio público)

Sigue leyendo ›