Quine-mcklausky
Páginas: 4 (954 palabras)
Publicado: 12 de diciembre de 2011
Método de Quine-McCluskey
El Algoritmo Quine–McCluskey es un método de simplificación de funciones booleanas desarrollado por Willard Van Orman Quine y Edward J. McCluskey. Es funcionalmenteidéntico a la utilización del mapa de Karnaugh, pero su forma tabular lo hace más eficiente para su implementación en lenguajes computacionales, y provee un método determinantico de conseguir la mínimaexpresión de una función booleana.
Aunque es más práctico que el mapa de Karnaugh, cuando se trata de trabajar con más de cuatro variables, el tiempo de resolución del algoritmo Quine-McCluskey crecede forma exponencial con el aumento del número de variables. Se puede demostrar que para una función de n variables el límite superior del número de implicantes primos es 3n/n. Si n = 32 habrá más de6.5 * 1015 implicantes primos. Funciones con un número grande de variables tienen que ser minimizadas con otros métodos heurísticos.
PASO 1
Encontrando implicantes primos
Un implicante es unminitérmino o un grupo de éstos que formen un sub-cubo.
Una expresió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 dela siguiente forma:
X * f
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 aX. En un mapa de f, si X corresponde a un grupo de minitérminos, g corresponderá al resto de los minitérminos de f, no considerados en X.
Se desea ahora definir las componentes de f que sean másprimitivas.
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 (producto deliterales) 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...
El Algoritmo Quine–McCluskey es un método de simplificación de funciones booleanas desarrollado por Willard Van Orman Quine y Edward J. McCluskey. Es funcionalmenteidéntico a la utilización del mapa de Karnaugh, pero su forma tabular lo hace más eficiente para su implementación en lenguajes computacionales, y provee un método determinantico de conseguir la mínimaexpresión de una función booleana.
Aunque es más práctico que el mapa de Karnaugh, cuando se trata de trabajar con más de cuatro variables, el tiempo de resolución del algoritmo Quine-McCluskey crecede forma exponencial con el aumento del número de variables. Se puede demostrar que para una función de n variables el límite superior del número de implicantes primos es 3n/n. Si n = 32 habrá más de6.5 * 1015 implicantes primos. Funciones con un número grande de variables tienen que ser minimizadas con otros métodos heurísticos.
PASO 1
Encontrando implicantes primos
Un implicante es unminitérmino o un grupo de éstos que formen un sub-cubo.
Una expresió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 dela siguiente forma:
X * f
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 aX. En un mapa de f, si X corresponde a un grupo de minitérminos, g corresponderá al resto de los minitérminos de f, no considerados en X.
Se desea ahora definir las componentes de f que sean másprimitivas.
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 (producto deliterales) 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...
Leer documento completo
Regístrate para leer el documento completo.