En la lógica booleana , una fórmula para una función booleana f está en Blake forma canónica ( BCF ), [1] también llamado el suma completa de implicantes primos , [2] la suma completa , [3] o la forma prime disyuntivo , [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 la cobertura del conjunto , [5] por lo que es NP-difícil . [6] [7]
Historia
Archie Blake presentó su forma canónica en una reunión de la American Mathematical Society en 1932, [8] y en su disertación de 1937. Lo llamó la "forma canónica simplificada"; [9] [10] [11] fue nombrada la "forma canónica de Blake" por Frank Markham Brown y Sergiu Rudeanu en 1986-1990. [12] [1]
Métodos de cálculo
Blake discutió 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, [13] Willard Quine , [14] y Kurt Bing. [15] [16]
Ver también
Referencias
- ↑ a b c d Brown, Frank Markham (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, 77ff, 81. ISBN 978-0-486-42785-0. [1]
- ^ Sasao, Tsutomu (1996). "Diagramas de decisión ternaria 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.
- ^ a b Kandel, Abraham (1998). Fundamentos del Diseño de Lógica Digital . pag. 177. ISBN 978-9-81023110-1.
- ^ Knuth, Donald Ervin (2011). Algoritmos combinatorios, parte 1 . El arte de la programación informática . 4A . pag. 54.
- ^ 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 Sistemas . 75 : 13-25 [13-14]. doi : 10.1016 / j.jcss.2008.07.007 .
- ^ Gimpel, James F. (1965). "Un método para producir una función booleana que tiene una tabla implícita primaria prescrita arbitraria". Transacciones IEEE en computadoras . 14 : 485–488.
- ^ Paul, Wolfgang Jakob (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informatica (en alemán). 4 (4): 321–336. doi : 10.1007 / BF00289615 . S2CID 35973949 .
- ^ Blake, Archie (noviembre de 1932). "Expresiones canónicas en álgebra de Boole". Boletín de la American Mathematical Society . Resúmenes de artículos: 805.
- ^ 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 .
- ^ Blake, Archie (septiembre de 1938). "Correcciones a expresiones canónicas en álgebra booleana ". El diario de la lógica simbólica . 3 (3): 112-113. doi : 10.2307 / 2267595 . JSTOR 2267595 .
- ^ McKinsey, John Charles Chenoweth , ed. (Junio de 1938). "Blake, Archie. Expresiones canónicas en álgebra booleana, Departamento de Matemáticas, Universidad de Chicago, 1937" . The Journal of Symbolic Logic (Revisión). 3 (2:93): 93. doi : 10.2307 / 2267634 . JSTOR 2267634 .
- ^ Brown, Frank Markham; Rudeanu, Sergiu (1986), A Functional Approach to the Theory of Prime Implicants , Publication de l'institut mathématique, Nouvelle série, 40 , págs. 23–32
- ^ 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.
- ^ Quine, Willard Van Orman (noviembre de 1955). "Una forma de simplificar las funciones de la verdad". The American Mathematical Monthly . 62 (9): 627–631. doi : 10.2307 / 2307285 . hdl : 10338.dmlcz / 142789 . JSTOR 2307285 .
- ^ Bing, Kurt (1955). "Sobre la simplificación de fórmulas proposicionales". Boletín de la American Mathematical Society . 61 : 560.
- ^ Bing, Kurt (1956). "Sobre la simplificación de fórmulas funcionales de verdad". El diario de la lógica simbólica . 21 (3): 253-254. doi : 10.2307 / 2269097 . JSTOR 2269097 .