Implicantes Primos: McCluskey – Quine Vs. Karnaugh

por Violeta León

     El estudio del método de McCluskey – Quine es funcionalmente idéntico al mapa de Karnaugh pero con una forma tabular que hace mas accesible su implementación en programas de computadoras. El mapa de Karnaugh por ser un método más visual no se presta para la elaboración de un programa de computadoras que busque el diseño óptimo sin intervención humana. En este sentido, el método de Quine siempre garantiza la obtención del diseño más económico posible. Por otra parte, el método de Quine nos lleva a definir de manera más práctica lo que es un implicante primo; esta es, obtenido un implicante primario no es posible remover ninguna de las variables en dicho implicante sin que pierda su relevancia; el hecho de que un implicante no sea un implicante primario tiene que ver directamente con una simplificación booleana realizada en estudios anteriores.

     Desde mi punto de vista, el método de Quine nos proporciona mayor seguridad en el resultado dado, puesto que no tiene formas en que el método falle, si es implementado como un algoritmo en un programa de computación. Y, si es utilizado por humanos, el método nos ofrece una herramienta de verificación por el cual, se puede corregir cualquier falla humana al aplicar el método; quien es nuestra mejor herramienta una vez comparado con el método de Karnaugh.

Definición del Método de McCluskey - Quine


     El método de Quine McCluskey o método tabular consta de dos partes. La primera parte consiste en hacer una búsqueda exhaustiva y comparativa en todos los términos para seleccionar aquellos que son candidatos para la función simplificada. Estos términos candidatos se denominan implicantes primos. La siguiente parte consiste en discriminar los implicantes primos encontrados para formar la expresión de la función con el menor número de literales o variables.


Terminología Para la Simplificación (Desde el punto de vista de Karnaugh) 

     A continuación definimos algunos términos comúnmente utilizados en los procesos de simplificación de funciones lógicas. 

1) Implicante: conjuntos de unos en un mapa de Karnaugh que representa un término producto de variables. Se denomina implicante porque cuando este término toma el valor de 1, implica que también la función toma el valor de 1. Un minitérmino solo es un implicante.

2) Implicante Primo: implicante que no está incluido completamente dentro de otro implicante. No puede combinarse con otro implicante para eliminar un literal. Debe aparecer necesariamente en el resultado final.

3) Implicante Primo Esencial: implicante primo que contiene uno o más minitérminos que no están incluidos en cualquier otro implicante primo.

Observemos en el siguiente mapa de Karnaugh quiénes son implicantes, implicantes primos e implicantes primos esenciales. Los términos I, II, III son implicantes primos. El término IV no es implicante primo. El término II no es un implicante primo esencial. La función se obtiene con los términos I y III.
Pasos Para Encontrar Los Implicantes Primos (desde el Punto de Vista de McCluskey - Quine) 

Paso 1.- Escribir cada conjunción fundamental de Ef en notación binaria.

Paso 2.- Clasificar las conjunciones de Ef según la cantidad de componentes iguales a 1 y colocar estas clases resultantes en una columna, ordenada de menor cantidad de componentes iguales a 1 mayor cantidad.

Paso 3.- Al eliminar una letra se coloca – en su lugar. Los elementos resultantes se colocan en otra columna, en el orden en que son obtenidos, sin repeticiones y conservando las clases según las componentes iguales a 1.

Paso 4.- Continuar el proceso hasta que no se pueda simplificar mas.

Paso 5.- Todos los Elementos o términos no simplificados son implicantes primos de f.


Pasos Para Verificar que el Resultado son Los Implicantes Primos de F. (desde el Punto de Vista de McCluskey - Quine)

Paso 1.- Se realiza la tabla de la función en sus n – letras, con su resultado.

Paso 2.- Se nombra ai a cada uno de sus implicantes primos.

Paso 3.- Eliminamos una letra del implicante ai y observamos si el valor que toma sigue implicando a F.

Paso 4.- Si el “implicante primo” sin la letra dejó de implicar a f entonces sí es un implicante primo de la función.

Paso 5.- Si el “implicante primo” sigue implicando a f, entonces en el proceso anterior (pasos para encontrar un implicante primo) hubo un error al simplificar.

Paso 6.- Repetir este proceso con todos los implicantes primos de la función.




Anuncio

Comentarios