En lógica matemática , los axiomas mínimos para el álgebra booleana son supuestos que son equivalentes a los axiomas del álgebra booleana (o cálculo proposicional ), elegidos para ser lo más cortos posible. Por ejemplo, un axioma con seis operaciones NAND y tres variables es equivalente al álgebra de Boole:
donde la barra vertical representa la operación lógica NAND (también conocida como el trazo de Sheffer ).
Es uno de los 25 axiomas candidatos para esta propiedad identificados por Stephen Wolfram , al enumerar las identidades de Sheffer de longitud menor o igual a 15 elementos (excluidas las imágenes especulares) que no tienen modelos no conmutativos con cuatro o menos variables, y primero se demostró que son equivalentes por William McCune , Branden Fitelson y Larry Wos . [1] [2] MathWorld , un sitio asociado con Wolfram, ha llamado al axioma el "axioma de Wolfram". [3] McCune y col. También encontró un axioma único más largo para el álgebra de Boole basado en la disyunción y la negación. [2]
En 1933, Edward Vermilye Huntington identificó el axioma
como equivalente al álgebra de Boole, cuando se combina con la conmutatividad de la operación OR ,, y el supuesto de asociatividad, . [4] Herbert Robbins conjeturó que el axioma de Huntington podría ser reemplazado por
que requiere un uso menos del operador de negación lógica . Ni Robbins ni Huntington pudieron probar esta conjetura; ni tampoco Alfred Tarski , que se interesó mucho en él más tarde. La conjetura fue finalmente probada en 1996 con la ayuda de un software de prueba de teoremas . [5] [6] [7] Esta prueba estableció que el axioma de Robbins, junto con la asociatividad y la conmutatividad, forman una base tridimensional para el álgebra booleana. La existencia de una base 2 fue establecida en 1967 por Carew Arthur Meredith : [8]
Al año siguiente, Meredith encontró una base 2 en términos del trazo de Sheffer: [9]
En 1973, Padmanabhan y Quackenbush demostraron un método que, en principio, produciría una base 1 para el álgebra booleana. [10] La aplicación de este método de una manera sencilla produjo "axiomas de enorme longitud", [2] lo que provocó la pregunta de cómo se podrían encontrar axiomas más cortos. Esta búsqueda arrojó la base 1 en términos del trazo de Sheffer dado anteriormente, así como la base 1
que está escrito en términos de OR y NOT. [2]
Referencias
- ^ Wolfram, Stephen (2002). Un nuevo tipo de ciencia . Wolfram Media. ISBN 978-1579550080.
- ^ a b c d McCune, William ; Veroff, Robert; Fitelson, Branden ; Harris, Kenneth; Feist, Andrew; Wos, Larry (2002), "Axiomas simples cortos para el álgebra de Boole", Journal of Automated Reasoning , 29 (1): 1–16, doi : 10.1023 / A: 1020542009983 , MR 1940227
- ^ Rowland, Todd; Weisstein, Eric W. "Wolfram Axiom" . MathWorld .
- ^ Huntington, EV (1933). "Nuevos conjuntos de postulados independientes para el álgebra de la lógica, con especial referencia a los Principia Mathematica de Whitehead y Russell ". Trans. Amer. Matemáticas. Soc. 25 : 247-304.
- ^ Henkin, Leon ; Monk, J. Donald; Tarski, Alfred (1971). Álgebras cilíndrico, Parte I . Holanda Septentrional . ISBN 978-0-7204-2043-2. OCLC 1024041028 .
- ^ McCune, William (1997). "Solución del problema de Robbins". Revista de razonamiento automatizado . 19 : 263-276. doi : 10.1023 / A: 1005843212881 .
- ^ Kolata, Gina (10 de diciembre de 1996). "Prueba matemática informática muestra poder de razonamiento" . The New York Times . Para erratas, consulte McCune, William (23 de enero de 1997). "Comentarios sobre la historia de Robbins" . Laboratorio Nacional Argonne . Archivado desde el original el 5 de junio de 1997.
- ^ Meredith, CA ; Antes, AN (1968). "Lógica ecuacional" . Notre Dame J. Lógica formal . 9 : 212-226. doi : 10.1305 / ndjfl / 1093893457 . Señor 0246753 .
- ^ Meredith, CA (1969). "Postulados de la ecuación para el trazo de Sheffer" . Notre Dame J. Lógica formal . 10 : 266–270. doi : 10.1305 / ndjfl / 1093893713 . Señor 0245423 .
- ^ Padmanabhan, R .; Quackenbush, RW (1973). "Teorías ecuacionales de álgebras con congruencias distributivas" . Proc. Amer. Matemáticas. Soc. 41 : 373–377. doi : 10.1090 / S0002-9939-1973-0325498-2 .