stringtranslate.com

Forma canónica de Blake

Mapa de Karnaugh de A B + BC + AC , una suma de todos los implicantes primos (cada uno representado en un color diferente). Eliminar AC da como resultado una suma mínima.
Función booleana con dos formas mínimas diferentes. La forma canónica de Blake es la suma de las dos.

En lógica booleana , una fórmula para una función booleana f está en la forma canónica de Blake ( BCF ), [1] también llamada suma completa de implicantes primos , [2] suma completa , [3] o forma prima disyuntiva , [4 ] cuando es una disyunción de todos los implicantes primos de f . [1]

Relación con otras formas

La forma canónica de Blake es un caso especial de forma normal disyuntiva .

La forma canónica de Blake no es necesariamente mínima (diagrama superior), sin embargo, todos los términos de una suma mínima están contenidos en la forma canónica de Blake. [3] Por otro lado, la forma canónica de Blake es una forma canónica , es decir, es única hasta el reordenamiento, mientras que puede haber múltiples formas mínimas (diagrama inferior). Seleccionar una suma mínima de una forma canónica de Blake equivale en general a resolver el problema de cobertura de conjuntos , [5] al igual que NP-hard . [6] [7]

Historia

Archie Blake presentó su forma canónica en una reunión de la Sociedad Matemática Estadounidense en 1932, [8] y en su disertación de 1937. La llamó "forma canónica simplificada"; [9] [10] [11] [12] Frank Markham Brown  [d] y Sergiu Rudeanu  [d] la denominaron "forma canónica de Blake" en 1986-1990. [13] [1] Junto con el trabajo de Platon Poretsky [14] también se le conoce como "leyes de Blake-Poretsky". [15] [ se necesita aclaración ]

Métodos de cálculo

Blake analizó tres métodos para calcular la forma canónica: agotamiento de implicantes, consenso iterado y multiplicación. El método de consenso iterado fue redescubierto [1] por Edward W. Samson y Burton E. Mills, [16] Willard Quine , [17] y Kurt Bing. [18] [19] En 2022, Milan Mossé, Harry Sha y Li-Yang Tan descubrieron un algoritmo casi óptimo para calcular la forma canónica de Blake de una fórmula en forma normal conjuntiva . [20]

Ver también

Referencias

  1. ^ abcd Brown, Frank Markham [en Wikidata] (2012) [2003, 1990]. "Capítulo 3: La forma canónica de Blake". Razonamiento booleano: la lógica de las ecuaciones booleanas (reedición de la 2ª ed.). Mineola, Nueva York: Dover Publications, Inc. págs. 4, 77 y siguientes, 81. ISBN 978-0-486-42785-0.[1]
  2. ^ Sasao, Tsutomu (1996). "Diagramas de decisión ternarios y sus aplicaciones". En Sasao, Tsutomu; Fujita, Masahira (eds.). Representaciones de funciones discretas . pag. 278. doi :10.1007/978-1-4613-1385-4_12. ISBN 978-0792397205.
  3. ^ ab Kandel, Abraham (1998). Fundamentos del diseño de lógica digital. pag. 177.ISBN​ 978-9-81023110-1.
  4. ^ Knuth, Donald Ervin (2011). Algoritmos combinatorios, parte 1 . El arte de la programación informática . vol. 4A. pag. 54.
  5. ^ Feldman, Vitaly [en Wikidata] (2009). "Dureza de la minimización lógica aproximada de dos niveles y el aprendizaje de 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 .
  6. ^ Gimpel, James F. (1965). "Un método para producir una función booleana que tiene una tabla de implicados primos prescritos arbitrariamente". Transacciones IEEE en computadoras . 14 : 485–488.
  7. ^ 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.
  8. ^ Blake, Archie (noviembre de 1932). "Expresiones canónicas en álgebra de Boole". Boletín de la Sociedad Matemática Estadounidense . Resúmenes de artículos: 805.
  9. ^ Blake, Archie (1937). Expresiones canónicas en álgebra de Boole (Disertación). Departamento de Matemáticas, Universidad de Chicago : Bibliotecas de la Universidad de Chicago .
  10. ^ Blake, Archie (1938). "Expresiones canónicas en álgebra de Boole". La revista de lógica simbólica . 3 (2).
  11. ^ Blake, Archie (septiembre de 1938). "Correcciones a expresiones canónicas en álgebra booleana ". La revista de lógica simbólica . 3 (3): 112-113. doi :10.2307/2267595. JSTOR  2267595. S2CID  5810863.
  12. ^ McKinsey, John Charles Chenoweth , ed. (junio de 1938). "Blake, Archie. Expresiones canónicas en álgebra booleana, Departamento de Matemáticas, Universidad de Chicago, 1937". La revista de lógica simbólica (revisión). 3 (2:93): 93. doi : 10.2307/2267634. JSTOR  2267634. ​​S2CID  122640691.
  13. ^ Marrón, Frank Markham [en Wikidata] ; Rudeanu, Sergiu [en Wikidata] (1986), Un enfoque funcional a la teoría de los implicantes primos , Publication de l'institut mathématique, Nouvelle série, vol. 40, págs. 23-32
  14. ^ Poretsky, Platon Sergeevich (1884). "O sposobach reschenija lopgischeskich rawenstw i ob obrathom spocobe matematischeskoi logiki"О способах решения логических равенств и об об обратном способе[Sobre los métodos de resolución de igualdades lógicas y el método inverso de la lógica matemática. Un ensayo en la construcción de una teoría de deducción sobre formas cualitativas completa y accesible. Informes recopilados de reuniones de la Sección de Ciencias Físicas y Matemáticas de la Sociedad de Naturalistas de la Universidad de Kazán (en ruso) (2).(NB. Esta publicación también se denomina "Sobre métodos de solución de igualdades lógicas y método inverso de lógica matemática".)
  15. ^ Vasyukevich, Vadim O. (2011). "1.10 Propiedades Venjuntivas (Fórmulas Básicas)". Escrito en Riga, Letonia. Operadores asíncronos de lógica secuencial: unión y secuenciación: análisis y diseño de circuitos digitales . Apuntes de conferencias en ingeniería eléctrica (LNEE). vol. 101 (1 ed.). Berlín/Heidelberg, Alemania: Springer-Verlag . pag. 20.doi :10.1007/978-3-642-21611-4 . ISBN 978-3-642-21610-7. ISSN  1876-1100. LCCN  2011929655.(xiii+1+123+7 páginas) (NB. La contraportada de este libro indica erróneamente el volumen 4, cuando en realidad es el volumen 101.)
  16. ^ Sansón, Edward Walter; Mills, Burton E. (abril de 1954). Minimización de circuitos: álgebra y algoritmos para nuevas expresiones canónicas booleanas (Informe técnico). Bedford, Massachusetts, EE.UU.: Centro de Investigación de Cambridge de la Fuerza Aérea . AFCRC TR 54-21.
  17. ^ Quine, Willard Van Orman (noviembre de 1955). "Una forma de simplificar las funciones de verdad". El Mensual Matemático Estadounidense . 62 (9): 627–631. doi :10.2307/2307285. hdl :10338.dmlcz/142789. JSTOR  2307285.
  18. ^ Bing, Kurt (1955). "Sobre la simplificación de fórmulas proposicionales". Boletín de la Sociedad Matemática Estadounidense . 61 : 560.
  19. ^ Bing, Kurt (1956). "Sobre la simplificación de fórmulas funcionales de verdad". La revista de lógica simbólica . 21 (3): 253–254. doi :10.2307/2269097. JSTOR  2269097. S2CID  37877557.
  20. ^ 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/document/10.4230/LIPIcs.SAT.2022.9 . Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi : 10.4230/LIPIcs.SAT.2022.9.