El Cedazo

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.

The Minimización de Funciones Lógicas. El algoritmo de Quine–McClusky explicado y mejorado-I by , unless otherwise expressly stated, is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 2.5 Spain License.