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

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

Esta serie versa sobre el algoritmo de Quine-McClusky.

Se trata del algoritmo de referencia utilizado para minimizar expresiones lógicas. Enunciado en 1952 Willard V. Quine, quien publicó un artículo sobre “El problema de simplificar funciones de verdad” que fue perfeccionado en 1956 por Edward J. McClusky cuando publicó su tesis “Minimización de funciones lógicas”, en la que definió el algoritmo definitivo de minimización de funciones lógicas.

Se conoce, pues, 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 en el sentido de que tiene el menor número posible de términos.

Sustituir la expresión original en el programa donde se encuentra por la equivalente mínima reduce el tiempo de ejecución de ese programa, pues para determinar cuál es el flujo del programa será preciso valorar un menor número de condiciones que en dicha expresión original. Y la misma afirmación puede hacerse sobre el 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, en realidad, al estudio, programación y crítica del famoso algoritmo de Quine-McClusky, y he encontrado diferentes aspectos que mejoran en algo, o quizás en mucho dicho algoritmo. 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.

La serie consta de cinco artículos, en cada uno de los cuales, y tras una breve introducción, se enlaza con un PDF en el que se encuentra físicamente dicho artículo, y un artículo final con el documento completo, es decir, con los cinco artículos unificados en un único documento.

Primer artículo.  Introducción.

Segundo artículo. El algoritmo de Quine McClusky, explicado.

Tercer artículo. Procedimiento alternativo usando maxterms.

Cuarto artículo. El método de Petrick.

Quinto artículo. El algoritmo Voraz.

Sexto artículo: El documento completo, compendio de los cinco documentos publicados en cada uno de los cinco artículos precedentes.

=============================================