Quine-McCluskey

Introducción

En matemáticas las expresiones booleanas se simplifican por numerosas

razones:

Una expresión más simple es más fácil de entender y tiene menos

posibilidades de error a la hora de su interpretación.

Una expresión simplificada suelen ser más eficiente y efectiva cuando se implementan en la práctica, como en el caso de circuitos eléctricos o en determinados algoritmos.

El método de Quine-McCluskey es particularmente útil cuando se tienen funciones con un gran número de variables, no es el caso del método de Karnaugh, que se hace impracticable con más de cinco variables. En nuestro caso, como el máximo número de variables será cuatro podremos utili zar conjuntamente ambos métodos.

Una expresión booleana se compone de variables y términos. Para este método las variables sólo podrán tener un valor numérico de cero (el correspondiente al valor de verdad false) o uno (el correspondiente al valor de verdad true) y se designarán mediante una letra.

Como notación se designará x si la variable contiene el valor uno, x’ en caso

de que contenga el valor cero.

Por otra parte, las variables se relacionarán entre sí únicamente mediante operaciones lógicas and para formar términos y mediante or para relacionarse con otros términos constituyendo una suma de productos. Ésta debe de ser canónica, es decir:

Cada variable se usa una vez en cada término. A dichos términos se les llama

términos canónicos.

Ejemplo

f(x,y,j) = x’y z +x y’z

x’y z se representa con 011, donde x = 0, y = 1, z = 1

x y’z se representa con 101, donde x = 1, y = 0, z = 1

Pasos

La cualidad de este método es que es un método tabular y gráfico, ideal para programarlo y obtener así un algoritmo que permita la obtención de expresiones algebraicas minimizadas del circuito en cuestión.

Paso 1. Identificar cada uno de los minitérminos implicados en la expresión algebraica, o bien en la tabla de verdad.

En caso de que la expresión algebraica no se muestre como suma de productos, deberá ser manipulada algebraicamente de tal forma que se obtenga.

Por ejemplo:

Paso 2. Listar como números binarios cada uno de los términos implicados en la expresión algebraica para posteriormente agruparlos en base al número de bits que tiene cada uno de ellos.

Por ejemplo:

Paso 3.-Una vez identificados los grupos, se deben combinar los términos entre grupos contiguos. Es decir, el grupo 0 con el grupo 1, el grupo 1 con el grupo 2, etc. De tal forma que se marque con un guion tan solo el bit que difiera de 1 a 0 o viceversa.

Paso 3.Por ejemplo:

Nótese que los grupos han cambiado en la cantidad de elementos que cada uno contiene en base a los 1’s que permanecen tras la primer iteración. Se deben marcar los términos que fueron combinados.

Paso 4. Se repite el paso 3 hasta que no se pueda combinar ningún elemento de cada grupo contiguo.

Paso 5.una vez que ya no se tiene elementos que al combinar se obtiene los implicantes primos que surgen de los términos no marcados.

Paso 5. Por ejemplo:

Los guiones indican la ausencia de la variable, por lo tanto no se lista. Nótese que la expresión no es la mínima, por lo tanto se recurre a la parte gráfica del método.

Paso 6. Se listan los implicantes primos obtenidos en forma de filas en una tabla y cuyas columnas corresponden a cada uno de los productos de

...