Metodo De Quine - Mccluskey

METODO DE QUINE-MC CLUSKEY
(Abril de 2012)

Wendy Patricia Hernández Acosta Código: 261910. Francisco González Buitrago. Código: 261869.
Universidad Nacional De Colombia. Sede Bogotá. Electrónica Digital I



Abstract- In this paper will explain the Quine –Mc Cluskey algorytthm, this method is used as a type of minimization in truth tables and Boolean algebra.

Index Terms: Implicants,Boolean algebra, Miniterms, Maxiterms


I. INTRODUCCION

Las expresiones booleanas se simplifican por numerosas razones:

- Se simplifica para que sea mas facil de entender y menos posibilidades de error a la hora de su interpretación.
- Es más eficiente y efectiva cuando se implementa en la práctica, disminuyendo los circuitos eléctricos o usando determinados algoritmos.

El métodode 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 utilizar conjuntamente ambos métodos.

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

A continuación se explicarán algunos conceptos para entender mejor el algoritmo de Quine-McCluskey

II. IMPLICANTES


Un implicante es un mintérmino o un grupo de éstos que formen un sub-cubo.


Unaexpresión X implica la función f, si y solamente si f=1 para cualquier combinación de valores para los cuales X=1.


Se anota la implicación de la siguiente forma:



X f





FIG.1. Implicación


Puede verse que si X f, con g una función booleana, puede anotarse: f = X + g .


Es decir, X es un término o parte de f. También suele decirse que f cubre a X.En una mapa de f, si X corresponde a un grupo de mintérminos, g corresponderá al resto de los mintérminos de f, no considerados en X.


Se desea ahora definir las componentes de f que sean más primitivas.




A. Implicantes primos

Un implicante primo es un implicante que no puede ser agrupado con otros implicantes, para formar un sub-cubo de mayor dimensión.

Se dice que X (productode literales) es un “implicante primo” de f si y sólo si:
X f
No existe y tal que X y f, donde el número de literales de y es menor que el número de literales de X.
No puede encontrarse un grupo mayor que X. Si existe y; entonces y es un implicante primo.
Básicamente, es un producto de literales que no puede ser combinado con otros para obtener un término con menos literales. Se diceprimo o primitivo en el sentido de ser componente básica o elemental de una función.
Algunas propiedades de un implicante primo:
No contiene literales repetidos.
No contiene a una variable y a su complemento.
No contiene variables redundantes. Es decir, si se descarta un literal del implicante, el resto no será implicante.
Si x e y son implicantes primos de f, entonces: x no cubre ay; y viceversa.

Encontrar los implicantes primos es determinar los grupos de mintérminos que pueden escribirse con menos literales. Pasar de un implicante a un implicante primo está asociado a un proceso de crecimiento; es decir, a encontrar un grupo de mintérminos que forman el sub-cubo mayor posible.

B. Implicante primo esencial

Es aquél que cubre a lo menos un mintérmino de lafunción que no es cubierto por otros implicantes primos. Deben estar presentes en la forma mínima.

Los mintérminos superfluos pueden emplearse para formar implicantes primos; pero no deben considerarse para los implicantes primos esenciales.

Ejemplo: Para una función de 4 variables se tienen los siguientes implicantes primos:

A'B'D, BC', AC, A'C'D, AB, B'CD

De los 6 implicantes primos,...