Algoritmo de Quine-McCluskey

Algoritmo para la minimización de funciones booleanas

Diagrama de Hasse del gráfico de búsqueda del algoritmo para 3 variables. Dado, por ejemplo, el subconjunto de los nodos de nivel inferior (verde claro), el algoritmo calcula un conjunto mínimo de nodos (aquí: , verde oscuro) que cubre exactamente . ${\displaystyle S=\{abc,a{\overline {b}}c,{\overline {a}}bc,{\overline {a}}b{\overline {c}},{\overline {a}}{\overline {b}}c\}}$ ${\displaystyle \{{\overline {a}}b,c\}}$ ${\displaystyle S}$

El algoritmo de Quine-McCluskey ( QMC ), también conocido como el método de implicantes primos , es un método utilizado para la minimización de funciones booleanas que fue desarrollado por Willard V. Quine en 1952 ^{[1] [2]} y ampliado por Edward J. McCluskey en 1956. ^[3] Como principio general, este enfoque ya había sido demostrado por el lógico Hugh McColl en 1878, ^{[4] [5] [6]} fue probado por Archie Blake en 1937, ^{[7] [8] [9] [6]} y fue redescubierto por Edward W. Samson y Burton E. Mills en 1954 ^{[10] [6]} y por Raymond J. Nelson en 1955. ^{[11] [6]} También en 1955, Paul W. Abrahams y John G. Nordahl ^[12] así como Albert A. Mullin y Wayne G. Kellner ^{[13] [14] [15] [16]} propusieron una variante decimal del método. ^{[17] [14] [15] [16] [18] [19] [20] [21]}

El algoritmo de Quine-McCluskey es funcionalmente idéntico al mapeo de Karnaugh , pero la forma tabular lo hace más eficiente para su uso en algoritmos informáticos y también proporciona una forma determinista de verificar que se ha alcanzado la forma mínima de un booleano F. A veces se lo denomina método de tabulación.

El algoritmo de Quine-McCluskey funciona de la siguiente manera:

1. Encontrar todos los implicantes primos de la función.
2. Utilice esos implicantes primos en una tabla de implicantes primos para encontrar los implicantes primos esenciales de la función, así como otros implicantes primos que son necesarios para cubrir la función.

Complejidad

Aunque es más práctico que el mapeo de Karnaugh cuando se trabaja con más de cuatro variables, el algoritmo de Quine-McCluskey también tiene un rango de uso limitado ya que el problema que resuelve es NP-completo . ^{[22] [23] [24]} El tiempo de ejecución del algoritmo de Quine-McCluskey crece exponencialmente con el número de variables. Para una función de n variables el número de implicantes primos puede ser tan grande como , ^[25] por ejemplo para 32 variables puede haber más de 534 × 10 ¹² implicantes primos. Las funciones con un gran número de variables deben minimizarse con métodos heurísticos potencialmente no óptimos , de los cuales el minimizador lógico heurístico Espresso fue el estándar de facto en 1995. ^{[ necesita actualización ] [26]} Para una clase natural de funciones , la complejidad precisa de encontrar todos los implicantes primos se entiende mejor: Milan Mossé, Harry Sha y Li-Yang Tan descubrieron un algoritmo casi óptimo para encontrar todos los implicantes primos de una fórmula en forma normal conjuntiva . ^[27] ${\displaystyle 3^{n}/{\sqrt {n}}}$ ${\displaystyle f}$

El segundo paso del algoritmo consiste en resolver el problema de cobertura de conjuntos ; ^{[28] Pueden ocurrir instancias} NP-duras de este problema en este paso del algoritmo. ^{[29] [30]}

Ejemplo

Aporte

En este ejemplo, la entrada es una función booleana en cuatro variables, que evalúa como en los valores y , evalúa como un valor desconocido en y , y como en cualquier otro lugar (donde estos números enteros se interpretan en su forma binaria para la entrada como para la concisión de la notación). Las entradas que evalúan como se denominan "minterms". Codificamos toda esta información escribiendo ${\displaystyle f:\{0,1\}^{4}\to \{0,1\}}$ ${\displaystyle 1}$ ${\displaystyle 4,8,10,11,12}$ ${\displaystyle 15}$ ${\displaystyle 9}$ ${\displaystyle 14}$ ${\displaystyle 0}$ ${\displaystyle f}$ ${\displaystyle 1}$

${\displaystyle f(A,B,C,D)=\sum m(4,8,10,11,12,15)+d(9,14).\,}$

Esta expresión indica que la función de salida f será 1 para los mintérminos y (indicados por el término 'm') y que no nos importa la salida para las combinaciones y (indicadas por el término 'd'). El símbolo de suma indica la suma lógica (OR lógico o disyunción) de todos los términos que se suman. ${\displaystyle 4,8,10,11,12}$ ${\displaystyle 15}$ ${\displaystyle 9}$ ${\displaystyle 14}$ ${\displaystyle \sum }$

Paso 1: encontrar implicantes primos

Primero, escribimos la función como una tabla (donde 'x' significa no importa):

La expresión de suma canónica de productos se puede formar fácilmente a partir de esta tabla, simplemente sumando los mintérminos (omitiendo los términos que no importan ) donde la función evalúa uno:

f _{A, B, C, D} = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD.

que no es mínimo. Por lo tanto, para optimizar, todos los minterms que evalúan a uno se colocan primero en una tabla de minterms. Los términos que no importan también se agregan a esta tabla (nombres entre paréntesis), de modo que se puedan combinar con los minterms:

En este punto, se pueden empezar a combinar los mintérminos con otros mintérminos en grupos adyacentes. Si dos términos difieren en un solo dígito, ese dígito se puede reemplazar con un guión que indica que el dígito no importa. Los términos que ya no se pueden combinar se marcan con un asterisco ( * ). Por ejemplo, 1000y 1001se pueden combinar para dar 100-, lo que indica que ambos mintérminos implican que el primer dígito es 1y los dos siguientes son 0.

Al pasar del tamaño 2 al tamaño 4, trátelo -como un tercer valor de bit. Empareje -primero los '. Los términos representan productos y para combinar dos términos de producto deben tener las mismas variables. Una de las variables debe complementarse en un término y no complementarse en el otro. Las variables restantes presentes deben coincidir. Entonces, para hacer coincidir dos términos, los -' deben alinearse y todos menos uno de los otros dígitos deben ser iguales. Por ejemplo, -110y -100se pueden combinar para dar -1-0, como pueden -110y -010para dar --10, pero -110y 011-no pueden ya que los -' no se alinean. -110corresponde a BCD' mientras que 011-corresponde a A'BC, y BCD' + A'BC no es equivalente a un término de producto.

Nota: En este ejemplo, ninguno de los términos de la tabla de implicantes de tamaño 4 se puede combinar más. En general, este proceso debe continuar (tamaños 8, 16, etc.) hasta que no se puedan combinar más términos.

Paso 2: gráfico de implicantes primos

Ninguno de los términos puede combinarse más allá de esto, por lo que en este punto construimos una tabla de implicantes primos esenciales. A lo largo del lateral van los implicantes primos que se acaban de generar (estos son los que se han marcado con un " * " en el paso anterior), y en la parte superior van los mintérminos especificados anteriormente. Los términos que no importan no se colocan en la parte superior; se omiten de esta sección porque no son entradas necesarias.

Para encontrar los implicantes primos esenciales, buscamos columnas con un solo "✓". Si una columna tiene un solo "✓", esto significa que el mintérmino solo puede ser cubierto por un implicante primo. Este implicante primo es esencial .

Por ejemplo: en la primera columna, con el mintérmino 4, solo hay un "✓". Esto significa que m(4,12) es esencial (por lo tanto, se marca con ^# ). El mintérmino 15 también tiene un solo "✓", por lo que m(10,11,14,15) también es esencial. Ahora todas las columnas con un "✓" están cubiertas. Las filas con los mintérminos m(4,12) y m(10,11,14,15) ahora se pueden eliminar, junto con todas las columnas que cubren.

El segundo implicante primo puede ser "cubierto" por el tercero y el cuarto, y el tercer implicante primo puede ser "cubierto" por el segundo y el primero, y por lo tanto ninguno es esencial. Si un implicante primo es esencial, entonces, como sería de esperar, es necesario incluirlo en la ecuación booleana minimizada. En algunos casos, los implicantes primos esenciales no cubren todos los mintérminos, en cuyo caso se pueden emplear procedimientos adicionales para la reducción de gráficos. El "procedimiento adicional" más simple es el de prueba y error, pero una forma más sistemática es el método de Petrick . En el ejemplo actual, los implicantes primos esenciales no manejan todos los mintérminos, por lo que, en este caso, los implicantes esenciales se pueden combinar con uno de los dos no esenciales para producir una ecuación:

f _{A, B, C, D} = BC'D' + AB' + AC ^[31]

o

f _{A, B, C, D} = BC'D' + AD' + AC

Ambas ecuaciones finales son funcionalmente equivalentes a la ecuación original y detallada:

f _{A, B, C, D} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.

Algoritmo

Paso 1: Encontrar los implicantes primos

El pseudocódigo que se muestra a continuación calcula de forma recursiva los implicantes primos dada la lista de mintérminos de una función booleana. Para ello, intenta fusionar todos los mintérminos posibles y filtra los mintérminos que se han fusionado hasta que no se puedan realizar más fusiones de los mintérminos y, por lo tanto, se hayan encontrado los implicantes primos de la función.

// Calcula los implicantes primos de una lista de mintérminos.// cada mintérmino tiene la forma "1001", "1010", etc. y puede representarse con una cadena.La función getPrimeImplicants(lista minterms) es  primeImplicants ← lista vacía fusiona ← nueva matriz booleana de longitud igual al número de minterms, cada uno establecido como falso número de fusiones ← 0 mergedMinterm, minterm1, minterm2 ← cadenas vacías para i = 0 a longitud(minterms) hacer  para c = i + 1 a longitud(minterms) hacer minterm1 ← minterms[i] minterm2 ← mintérminos[c] // Comprobando que dos minterms se pueden fusionar si CheckDashesAlign(minterm1, minterm2) y CheckMintermDifference(minterm1, minterm2) entonces fusionadoMinterm ← MergeMinterms(minterm1, minterm2) Si primeImplicants no contiene mergedMinterm entonces primeImplicants.Add(mergedMinterm) númeroDeFusiones ← númeroDeFusiones + 1 fusiona[i] ← verdadero fusiona[c] ← verdadero // Filtrar todos los minitérminos que no se han fusionado porque son implicantes primos. También eliminar duplicados para j = 0 a length(minterms) hacer  si merges[j] == false && primeImplicants no contiene minterms[j] entonces primeImplicants.Add(minterms[j]) // si no se han producido fusiones, entonces se han encontrado todos los implicantes principales, por lo que se retorna; de lo contrario //seguir fusionando los minterms. si numberOfmerges == 0 entonces  devuelve primeImplicants de lo contrario  devuelve getPrimeImplicants(primeImplicants)

En este ejemplo, las funciones CheckDashesAligny CheckMintermDifferencerealizan las comprobaciones necesarias para determinar si se pueden fusionar dos mintérminos. La función MergeMintermsfusiona los mintérminos y agrega los guiones donde sea necesario. Las funciones de utilidad que se muestran a continuación suponen que cada mintérmino se representará mediante cadenas.

La función MergeMinterms(minterm1, minterm2) es mergedMinterm ← cadena vacía para i = 0 a length(minterm1) hacer  //Si los bits varían, reemplácelos con un guion; de lo contrario, el bit permanece en el minterm fusionado. si minterm[i] != minterm2[i] entonces términoMinterm fusionado ← términoMinterm fusionado + '-' demás términoMinterm fusionado ← términoMinterm fusionado + minterm1[i] Devuelve el término fusionadoLa función CheckDashesAlign(minterm1, minterm2) es  para i = 0 a length(minterm1 )  // Si un minterm tiene guiones y el otro no, entonces los minterms no se pueden fusionar. si minterm1[i] != '-' && minterm2[i] == '-' entonces  devuelve falso devuelve verdaderoLa función CheckMintermDifference(minterm1, minterm2) es  // minterm1 y minterm2 son cadenas que representan todos los implicantes primos encontrados actualmente y fusionados // minitérminos. Algunos ejemplos son '01--' y '10-0' m1, m2 ← representación entera de minterm1 y minterm2 con los guiones eliminados, estos se reemplazan con 0 // ^ aquí hay un XOR bit a bit res ← m1 ^ m2 devuelve res != 0 && (res & res - 1) == 0

Paso 2: Diagrama de implicantes primos

El pseudocódigo a continuación se puede dividir en dos secciones:

1. Creación del gráfico de implicantes primos utilizando los implicantes primos
2. Lectura de la tabla de implicantes primos para encontrar los implicantes primos esenciales.

Creación del diagrama de implicantes primos

El diagrama de implicantes primos se puede representar mediante un diccionario donde cada clave es un implicante primo y el valor correspondiente es una cadena vacía que almacenará una cadena binaria una vez que se complete este paso. Cada bit de la cadena binaria se utiliza para representar los ticks dentro del diagrama de implicantes primos. El diagrama de implicantes primos se puede crear siguiendo los pasos siguientes:

1. Iterar a través de cada clave (implicante principal del diccionario).
2. Reemplace cada guión en el implicante principal con el \dcódigo del carácter. Esto crea una expresión regular que se puede comparar con cada uno de los minitérminos en busca de coincidencias.
3. Recorrer cada término mínimo, comparando la expresión regular con la representación binaria del término mínimo. Si hay una coincidencia, agregar un "1"a la cadena correspondiente en el diccionario. De lo contrario, agregar un "0".
4. Repita este procedimiento para todos los implicantes primos hasta crear el cuadro de implicantes primos completo.

Cuando se escribe en pseudocódigo, el algoritmo descrito anteriormente es:

función CreatePrimeImplicantChart(lista primeImplicants, lista minterms) primeImplicantChart ← nuevo diccionario con clave de tipo cadena y valor de tipo cadena // Creando el gráfico vacío con los implicantes primos como clave y cadenas vacías como valor. para i = 0 a length(primeImplicants) hacer //Añadiendo un nuevo implicante primo al gráfico. primeImplicantChart.Add(primeImplicants[i], "")  para i = 0 a length(primeImplicantChart.Keys) hacer primeImplicant ← primeImplicantChart.Keys[i] // Convierte "-" en "\d", que puede usarse para encontrar la fila de marcas de arriba. expresiónRegular ← Convertir a expresiónRegular(implicante principal) para j = 0 a length(minterms) hacer // Si hay una coincidencia entre la expresión regular y el minterm, agregue un 1, de lo contrario, 0. Si regularExpression.matches(minterms[j]) entonces primeImplicantChart[primeImplicant] += "1" demás  primeImplicantChart[primeImplicant] += "0" // La tabla de implicantes primos está completa, por lo tanto, devuelve la tabla completa. Devolver primeImplicantChart

La función de utilidad, ConvertToRegularExpression, se utiliza para convertir el implicante primo en la expresión regular para verificar coincidencias entre el implicante y los mintérminos.

función ConvertToRegularExpression(cadena primeImplicant) regularExpression ← nueva cadena para i = 0 a length(primeImplicant) hacer  si primeImplicant[i] == "-" entonces //Añade el carácter literal "\d". expresión regular += @"\d" demás expresión regular += primeImplicant[i] devolver expresión regular

Encontrar los implicantes primos esenciales

Utilizando la función, CreatePrimeImplicantChart, definida arriba, podemos encontrar los implicantes primos esenciales simplemente iterando columna por columna de los valores en el diccionario, y donde "1"se encuentra uno solo, entonces se ha encontrado un implicante primo esencial.

Véase también

• Forma canónica de Blake
• Algoritmo de Buchberger : algoritmo análogo para la geometría algebraica
• El método de Petrick
• Análisis comparativo cualitativo (ACC)

Referencias

1. Quine, Willard Van Orman (octubre de 1952). "El problema de simplificar funciones de verdad". The American Mathematical Monthly . 59 (8): 521–531. doi :10.2307/2308219. JSTOR  2308219.
2. Quine, Willard Van Orman (noviembre de 1955). "Una forma de simplificar las funciones de verdad". The American Mathematical Monthly . 62 (9): 627–631. doi :10.2307/2307285. hdl :10338.dmlcz/142789. JSTOR  2307285.
3. McCluskey, Edward Joseph Jr. (noviembre de 1956). "Minimización de funciones booleanas". Bell System Technical Journal . 35 (6): 1417–1444. doi :10.1002/j.1538-7305.1956.tb03835.x. hdl :10338.dmlcz/102933 . Consultado el 24 de agosto de 2014 .
4. McColl, Hugh (14 de noviembre de 1878). "El cálculo de enunciados equivalentes (tercer artículo)". Actas de la London Mathematical Society . s1-10 (1): 16–28. doi :10.1112/plms/s1-10.1.16.
5. Ladd, Christine (1883). "Sobre el álgebra de la lógica". En Peirce, Charles Sanders (ed.). Estudios de lógica . Boston, EE. UU.: Little, Brown & Company . pp. 17–71. p. 23: [...] Si la reducción [de una expresión a la forma más simple] no es evidente, se puede facilitar tomando la expresión negativa, reduciéndola y luego restaurándola a la forma positiva. [...]
6. Brown, Frank Markham (noviembre de 2010) [2010-10-27]. "McColl y la minimización". Historia y filosofía de la lógica . 31 (4). Taylor & Francis : 337–348. doi :10.1080/01445340.2010.517387. ISSN  1464-5149. S2CID  216590641. Archivado desde el original el 2020-04-15 . Consultado el 2020-04-15 .
7. Blake, Archie (1938) [1937]. Canonical Expressions in Boolean Algebra (Disertación) (Ed. litografiada). Chicago, Illinois, EE. UU.: University of Chicago Libraries . p. 36. p. 36: [...] este método era conocido por Peirce y sus estudiantes [...] Se menciona en varios lugares en Studies in Logic, por miembros de la Universidad Johns Hopkins , 1883 [...](ii+60 páginas)
8. Blake, Archie (noviembre de 1932). "Expresiones canónicas en el álgebra de Boole". Boletín de la Sociedad Matemática Americana . Resúmenes de artículos: 805.
9. Blake, Archie (junio de 1938). "Correcciones a expresiones canónicas en álgebra de Boole". The Journal of Symbolic Logic . 3 (2). Association for Symbolic Logic : 112–113. doi :10.2307/2267595. ISSN  0022-4812. JSTOR  2267595. S2CID  5810863.
10. Samson, Edward Walter; Mills, Burton E. (abril de 1954). Minimización de circuitos: álgebra y algoritmos para nuevas expresiones canónicas booleanas . Bedford, Massachusetts, EE. UU.: Centro de investigación de la Fuerza Aérea de Cambridge . Informe técnico AFCRC TR 54-21.
11. Nelson, Raymond J. (junio de 1955). "Funciones de verdad normales más simples". The Journal of Symbolic Logic . 20 (2). Association for Symbolic Logic : 105–108. doi :10.2307/2266893. JSTOR  2266893. S2CID  32920372.(4 páginas)
12. "Bienvenido a la página conmemorativa de John "Jack" G Nordahl 14 de junio de 1933 ~ 20 de noviembre de 2017 (84 años)". Jellison Funeral Home and Cremation Services. Archivado desde el original el 2020-05-05 . Consultado el 2020-05-05 .
13. Mullin, Albert Alkins ; Kellner, Wayne G. (1958). Escrito en la Universidad de Illinois, Urbana, EE. UU. y en el Departamento de Ingeniería Eléctrica, Instituto Tecnológico de Massachusetts , Massachusetts, EE. UU. "Una prueba de residuos para funciones booleanas" (PDF) . Transactions of the Illinois State Academy of Science (Memorando de enseñanza). 51 (3–4). Springfield, Illinois, EE. UU.: 14–19. S2CID  125171479. Archivado (PDF) desde el original el 2020-05-05 . Consultado el 2020-05-05 .[1] (6 páginas) (NB: En su libro, Caldwell fecha esto en noviembre de 1955 como un memorando de enseñanza. Dado que Mullin fecha su trabajo en 1958 en otra obra y el memorando de clase de Abrahams/Nordahl también está fechado en noviembre de 1955, esto podría ser un error de copia).
14. Caldwell, Samuel Hawks (1958-12-01) [febrero de 1958]. "5.8. Operaciones con símbolos decimales". Escrito en Watertown, Massachusetts, EE. UU. Circuitos de conmutación y diseño lógico . Quinta edición, septiembre de 1963 (1.ª ed.). Nueva York, EE. UU.: John Wiley & Sons Inc., págs. 162-169. ISBN 0-47112969-0. LCCN  58-7896. p. 166: [...] Es un placer registrar que este tratamiento se basa en el trabajo de dos estudiantes durante el período en que estudiaban Circuitos de Conmutación en el Instituto Tecnológico de Massachusetts. Discutieron el método de forma independiente y luego colaboraron en la preparación de un memorando de clase: PW Abraham y JG Nordahl [...](xviii+686 páginas) (NB: El primer tratado importante sobre el método decimal que aparece en este libro se conoce a veces, de manera engañosa, como "la tabulación decimal de Caldwell").
15. Mullin, Albert Alkins (1960-03-15) [1959-09-19]. Escrito en la Universidad de Illinois, Urbana, EE. UU. Fisher, Harvey I.; Ekblaw, George E.; Green, FO; Jones, Reece; Kruidenier, Francis; McGregor, John; Silva, Paul; Thompson, Milton (eds.). "Two Applications of Elementary Number Theory" (PDF) . Transactions of the Illinois State Academy of Science . 52 (3–4). Springfield, Illinois, EE. UU.: 102–103. Archivado (PDF) desde el original el 2020-05-05 . Consultado el 2020-05-05 .[2][3][4] (2 páginas)
16. McCluskey, Edward Joseph Jr. (junio de 1960). "Albert A. Mullin y Wayne G. Kellner. Una prueba de residuos para funciones booleanas. Transactions of the Illinois State Academy of Science, vol. 51 nos. 3 y 4, (1958), pp. 14-19". The Journal of Symbolic Logic (Reseña). 25 (2): 185. doi :10.2307/2964263. JSTOR  2964263. S2CID  123530443. p. 185: [...] Los resultados de este artículo se presentan en el libro más disponible de SH Caldwell [...]. En este libro, el autor da crédito a Mullin y Kellner por el desarrollo de las manipulaciones con los números decimales.(1 página)
17. Abrahams, Paul William; Nordahl, John "Jack" G. (noviembre de 1955). El procedimiento de reducción de Quine-McCluskey modificado (memorándum de clase). Departamento de Ingeniería Eléctrica, Instituto Tecnológico de Massachusetts , Massachusetts, EE. UU.{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )(4 páginas) (NB: Algunas fuentes mencionan a los autores como "PW Abraham" e "IG Nordahl", el título también se cita como "Procedimiento de reducción McCluskey-Quine modificado").
18. Fielder, Daniel C. (diciembre de 1966). "Reducción de funciones booleanas en el aula". IEEE Transactions on Education . 9 (4). IEEE : 202–205. Bibcode :1966ITEdu...9..202F. doi :10.1109/TE.1966.4321989. eISSN  1557-9638. ISSN  0018-9359.
19. Kämmerer, Wilhelm [en alemán] (mayo de 1969). "I.12. Teoría: Minimierung Boolescher Funktionen". Escrito en Jena, Alemania. En Frühauf, Hans [en alemán] ; Kämmerer, Wilhelm; Schröder, Kurz; Winkler, Helmut (eds.). Digitale Automaten: teoría, estructura, técnica y programación. Elektronisches Rechnen und Regeln (en alemán). vol. 5 (1 ed.). Berlín, Alemania: Akademie-Verlag GmbH . págs. 98, 103-104. Licencia no. 202-100/416/69. Nro. de pedido. 4666 ES 20 K 3. pág. 98: [...] 1955 wurde das Verfahren auf die bequemere dezimale Schreibweise umgestellt (PW Abraham und IG Nordahl en [Caldwell]). [...](NB. También existe una segunda edición de 1973.)
20. Holdsworth, Brian; Woods, Clive (2002). "3.17 Enfoque decimal para la simplificación de Quine-McCluskey del álgebra de Boole". Digital Logic Design (4.ª ed.). Newnes Books / Elsevier Science . págs. 65–67. ISBN 0-7506-4588-2. Recuperado el 19 de abril de 2020 .{{cite book}}: Mantenimiento de CS1: errores de ISBN ignorados ( enlace )(519 páginas) [5]
21. Majumder, Alak; Chowdhury, Barnali; Mondal, Abir J.; Jain, Kunj (30 de enero de 2015) [9 de enero de 2015]. Investigación sobre el método de Quine McCluskey: un nuevo enfoque basado en la manipulación decimal para la minimización de la función booleana. Conferencia internacional de 2015 sobre diseño electrónico, redes informáticas y verificación automatizada (EDCAV), Shillong, India (artículo de conferencia). Departamento de Electrónica y Comunicación, Instituto Nacional de Ingeniería y Tecnología, Arunachal Pradesh Yupia, India. págs. 18–22. doi :10.1109/EDCAV.2015.7060531. Archivado desde el original el 8 de mayo de 2020. Consultado el 8 de mayo de 2020 .[6] (NB. Este trabajo no cita la técnica anterior sobre métodos decimales.) (5 páginas)
22. Masek, William J. (1979). Algunos problemas de cobertura de conjuntos NP-completos . No publicado.
23. Czort, Sebastian Lukas Arne (1999). La complejidad de minimizar fórmulas de forma normal disyuntiva (tesis de maestría). Universidad de Aarhus.
24. Umans, Christopher ; Villa, Tiziano; Sangiovanni-Vincentelli, Alberto Luigi (5 de junio de 2006). "Complejidad de la minimización de la lógica de dos niveles". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 25 (7): 1230–1246. doi :10.1109/TCAD.2005.855944. S2CID  10187481.
25. Chandra, Ashok K.; Markowsky, George (1978). "Sobre el número de implicantes primos". Matemáticas discretas . 24 (1): 7–11. doi : 10.1016/0012-365X(78)90168-1 .
26. Nelson, Victor P.; Nagle, H. Troy; Carroll, Bill D.; Irwin, J. David (1995). Análisis y diseño de circuitos lógicos digitales (2.ª ed.). Prentice Hall . p. 234. ISBN 978-0-13463894-2. Recuperado el 26 de agosto de 2014 .
27. Mossé, Milán; Sha, Harry; Tan, Li-Yang (2022). "Una generalización del lema de codificación de satisfacibilidad y sus aplicaciones". DROPS-IDN/V2/Documento/10.4230/LIPIcs.SAT.2022.9 . Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi : 10.4230/LIPIcs.SAT.2022.9 .
28. Feldman, Vitaly (2009). "Dureza de la minimización lógica aproximada de dos niveles y aprendizaje PAC con consultas de membresía". Revista de Ciencias de la Computación y de Sistemas . 75 : 13–25 [13–14]. doi : 10.1016/j.jcss.2008.07.007 .
29. Gimpel, James F. (1965). "Un método para producir una función booleana que tiene una tabla de implicantes primos prescrita arbitrariamente". IEEE Transactions on Computers . 14 : 485–488. doi :10.1109/PGEC.1965.264175.
30. Paul, Wolfgang Jakob [en alemán] (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informática (en alemán). 4 (4): 321–336. doi :10.1007/BF00289615. S2CID  35973949.
31. Programa del viernes de lógica

Lectura adicional

• Curtis, Herbert Allen (1962). "Capítulo 2.3. El método de McCluskey". Un nuevo enfoque para el diseño de circuitos de conmutación . The Bell Laboratories Series (1.ª ed.). Princeton, Nueva Jersey, EE. UU.: D. van Nostrand Company, Inc., págs. 90-160. ISBN 0-44201794-4. OCLC  1036797958. S2CID  57068910. ISBN 978-0-44201794-1 . ark:/13960/t56d6st0q. (viii+635 páginas) (NB: Este libro fue reimpreso por Chin Jih en 1969.)
• Coudert, Olivier (octubre de 1994). «Minimización lógica de dos niveles: una visión general» (PDF) . Integration, the VLSI Journal . 17–2 (2): 97–140. doi :10.1016/0167-9260(94)00007-7. ISSN  0167-9260. Archivado (PDF) desde el original el 2020-05-10 . Consultado el 2020-05-10 .(47 páginas)
• Jadhav, Vitthal; Buchade, Amar (8 de marzo de 2012). "Método de Quine-McCluskey modificado". arXiv : 1203.2289 [cs.OH].(4 páginas)
• Crenshaw, Jack (19 de agosto de 2004). "Todo sobre Quine-McClusky". builtin.com . Archivado desde el original el 10 de mayo de 2020 . Consultado el 10 de mayo de 2020 .
• Tomaszewski, Sebastian P.; Celik, Ilgaz U.; Antoniou, George E. (diciembre de 2003) [5 de marzo de 2003, 9 de abril de 2002]. "Minimización de funciones booleanas basada en WWW" (PDF) . Revista internacional de matemáticas aplicadas y ciencias de la computación . 13 (4): 577–584. Archivado (PDF) desde el original el 10 de mayo de 2020 . Consultado el 10 de mayo de 2020 .[7][8] (7 páginas)
• Duşa, Adrian (1 de octubre de 2008) [septiembre de 2007]. "Un enfoque matemático para el problema de minimización booleana". Calidad y cantidad . 44 : 99–113. doi :10.1007/s11135-008-9183-x. S2CID  123042755. Número de artículo: 99 (2010).[9] (22 páginas)
• Duşa, Adrian (2007). "Enhancing Quine-McCluskey" (PDF) . Universidad de Bucarest . Archivado (PDF) desde el original el 2020-05-12 . Consultado el 2020-05-12 .(16 páginas) (NB.

Enlaces externos

• Tutorial Tutorial sobre el método de Quine-McCluskey y Petrick.
• Para ver un ejemplo completamente resuelto, visite: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm