método de quine–mccluskey
TRANSCRIPT
-
8/12/2019 Mtodo de QuineMcCluskey
1/7
Mtodo Quine-McCluskey
Desarrollo
El mtodo de Quine-McCluskey es un mtodo tabular de simplificacin de funciones
booleanas, que facilita mucho la minimizacin de funciones de ms de cuatro variables.
El mtodo de Quine-McCluskey parte de una funcin booleana expresada como una
suma de productos en forma cannica.
Adems, este mtodo es muy sistemtico y no se requiere de una gran habilidad para
reconocer patrones dentro de un mapa (lo que ya lo vuelve an ms accesible).
Podemos encontrarnos con diversas variantes de este mtodo, implementadas en
software computacional para el diseo de circuitos.
Procedimiento
1. El primer paso del mtodo consiste en obtener todos los trminos producto quepueden formar parte de la nueva expresin simplificada.
2. El segundo paso consiste en generar la expresin minimizada, es decir, identificar lacombinacin mnima de trminos que representa la funcin que estamos
simplificando.
Algoritmo deQuineMcCluskey
1. Obtencinde los trminos
producto
2. Generar laexpresin
minimizada
-
8/12/2019 Mtodo de QuineMcCluskey
2/7
Obtencin de los trminos producto
Comenzamos obteniendo todas las parejas de trminos producto cuyo valor difiera en
una sola variable:
Se agrupan todos los trminos producto que valgan 1 y que tengan el mismonmero de variables con valor 1.
Se ordenan los grupos, en orden ascendente, segn el nmero de variables convalor 1.
Para formar las parejas, solo es necesario comparar los trminos producto de ungrupo con los del siguiente.
Una vez hecho esto, se repite el proceso con los grupos resultantes hasta que no sea
posible obtener ms parejas.
En primer lugar hay que agrupar los trminos y ordenarlos segn el nmero de variables
con valor 1.
Fig. 1
-
8/12/2019 Mtodo de QuineMcCluskey
3/7
A continuacin se forman parejas entre grupos que difieran en el valor de una nica
variable.
Fig. 2
Si repetimos el proceso una vez ms, llegamos a un punto en el que no es posible
simplificar ms.
Fig. 3
-
8/12/2019 Mtodo de QuineMcCluskey
4/7
A partir de las combinaciones obtenidas podemos deducir los trminos producto.
Fig. 4
Seleccin de los trminos producto
Hay que tener en cuenta todos los grupos tales que no haya uno mayor que los
contenga, aunque no todos ellos aparecern necesariamente en la expresin
minimizada.
Slo es necesario elegir un conjunto de trminos producto que cubran todas las
combinaciones en las que la salida de la funcin deba valer 1:
Se genera una tabla de seleccin marcando qu trminos producto cubrencada combinacin.
Se seleccionan aquellos trminos que son los nicos que cubren unacombinacin y, por tanto, son esenciales.
Se eligen los trminos para cubrir las otras combinaciones.
La tabla de seleccin nos indica la relacin entre los trminos producto y las
combinaciones cubiertas por cada uno de ellos.
-
8/12/2019 Mtodo de QuineMcCluskey
5/7
Fig. 5
Una vez tenemos la tabla debemos identificar los trminos esenciales, o sea, aquellos
que sean los nicos en cubrir una determinada combinacin.
Fig. 6
-
8/12/2019 Mtodo de QuineMcCluskey
6/7
Para cubrir las combinaciones restantes, has dos posibles trminos, es decir, existen dos
funciones mnimas posibles.
Fig. 7
Para cubrir las combinaciones restantes, has dos posibles trminos, es decir, existen dos
funciones mnimas posibles.
Fig. 8
-
8/12/2019 Mtodo de QuineMcCluskey
7/7
Seleccin de los trminos no esenciales
En el ejemplo anterior, los trminos producto esenciales cubran ocho de las diez
combinaciones, con lo que era sencillo obtener la cobertura mnima de las otras dos. Sin
embargo, es posible que sea necesario escoger entre un gran nmero de trminos
producto para generar la cobertura de las combinaciones restantes.
Una forma metdica de realizar esta seleccin es generando un producto de sumas en
el que cada suma representa el conjunto de trminos producto que cubren una
determinada combinacin.
Una vez obtenida el producto de sumas, se aplica la propiedad distributiva para
multiplicarlos entre ellos y obtener una expresin en forma de suma de productos. Cada
trmino de la suma de productos simplificada representa una posible combinacin de
trminos que cubre todas las combinaciones restantes. De entre todas las posibles
coberturas, se debe elegir aquella que requiera el menor nmero de trminos.