Hispanopedia Wiki
Articulo de referencia

Álgebra de Robbins

En álgebra abstracta , un álgebra de Robbins es un álgebra que contiene una sola operación binaria. ∨ {\displaystyle \lor } y una sola operación unaria ¬ {\displaystyle \neg } q...

Hispanopedia WikiContenido en espanolLectura gratuita

En álgebra abstracta , un álgebra de Robbins es un álgebra que contiene una sola operación binaria.∨{\displaystyle \lor }y una sola operación unaria¬{\displaystyle \neg }que satisfacen los siguientes axiomas : [ 1 ]

Para todos los elementos a , b y c :

  1. Asociatividad :a∨(b∨do)=(a∨b)∨do{\displaystyle a\lor \left(b\lor c\right)=\left(a\lor b\right)\lor c}
  2. Conmutatividad :a∨b=b∨a{\displaystyle a\lor b=b\lor a}
  3. Ecuación de Robbins :¬(¬(a∨b)∨¬(a∨¬b))=a{\displaystyle \neg \left(\neg \left(a\lor b\right)\lor \neg \left(a\lor \neg b\right)\right)=a}

Durante muchos años se conjeturó, aunque sin probarse, que todas las álgebras de Robbins son álgebras booleanas . Esto fue demostrado por William McCune en 1997, [ 1 ] [ 2 ] [ 3 ] por lo que el término "álgebra de Robbins" es ahora simplemente un sinónimo de "álgebra booleana".

Historia

En 1933, Edward Huntington propuso un nuevo conjunto de axiomas para álgebras booleanas, [ 4 ] [ 5 ] que consiste en (1) y (2) anteriores, más:

  • Ecuación de Huntington :¬(¬a∨b)∨¬(¬a∨¬b)=a.{\displaystyle \neg (\neg a\lor b)\lor \neg (\neg a\lor \neg b)=a.}

A partir de estos axiomas, Huntington derivó los axiomas habituales del álgebra de Boole.

Poco después, Herbert Robbins planteó la conjetura de Robbins , a saber, que la ecuación de Huntington podía sustituirse por lo que se conocería como la ecuación de Robbins, y el resultado seguiría siendo álgebra booleana .∨{\displaystyle \lor }interpretaría la unión booleana y¬{\displaystyle \neg }Complemento booleano . La intersección booleana y las constantes 0 y 1 se definen fácilmente a partir de las primitivas del álgebra de Robbins. A la espera de la verificación de la conjetura, el sistema de Robbins se denominó "álgebra de Robbins".

Para verificar la conjetura de Robbins, era necesario demostrar la ecuación de Huntington, o alguna otra axiomatización de un álgebra booleana, como teoremas de un álgebra de Robbins. Huntington, Robbins, Alfred Tarski y otros trabajaron en el problema, pero no lograron encontrar una demostración ni un contraejemplo.

La prueba de McCune

En 1996, William McCune demostró la conjetura utilizando el demostrador automático de teoremas EQP (demostrador de ecuaciones). [ 6 ] McCune desarrolló EQP mientras trabajaba en la División de Matemáticas e Informática del Laboratorio Nacional Argonne . [ 7 ] McCune consideraba a EQP un prototipo que desarrolló específicamente para demostrar la conjetura de Robbins, a diferencia de OTTER , otro demostrador de teoremas que desarrolló para uso general. [ 8 ] La demostración tardó ocho días en completarse con EQP. Posteriormente, McCune llamó a Robbins, que entonces tenía 81 años, para comunicarle que la conjetura había sido demostrada. [ 7 ]

La demostración de McCune se basó en trabajos previos sobre la conjetura realizados por Steve Winker, también investigador en Argonne. [ 6 ] [ 9 ]

Para una demostración completa de la conjetura de Robbins en una notación consistente y siguiendo fielmente a McCune, véase Mann (2003). [ 10 ] Dahn (1998) simplificó la demostración de McCune para máquinas. [ 3 ]

Véase también

Referencias

  1. ^ Weisstein, Eric W. "Álgebra de Robbins " . Consultado el 9 de septiembre de 2025 .
  2. ↑ McCune, William (1997). "Solución del problema de Robbins". Journal of Automated Reasoning . 19 (3): 263– 276. doi : 10.1023/A:1005843212881 .
  3. 1 2 Dahn, Bernd I (1998-10-15). "Las álgebras de Robbins son booleanas: una revisión de la solución generada por computadora de McCune del problema de Robbins" . Journal of Algebra . 208 (2): 526– 532. doi : 10.1006/jabr.1998.7467 . ISSN 0021-8693 . 
  4. ↑ Huntington, Edward V. (1933). "Nuevos conjuntos de postulados independientes para el álgebra de la lógica, con especial referencia a los Principia mathematica de Whitehead y Russell" . Transactions of the American Mathematical Society . 35 : 274–304 . doi : 10.1090/S0002-9947-1933-1501684-X . JSTOR 1989325 . 
  5. ↑ Huntington, Edward V. (1933). "Álgebra booleana. Una corrección" . Transactions of the American Mathematical Society . 35 (2): 557– 558. doi : 10.1090/S0002-9947-1933-1501702-9 . JSTOR 1989783 . 
  6. 1 2 McCune, William (1996). "Las álgebras de Robbins son booleanas" . Boletín informativo de la Asociación para el Razonamiento Automatizado . 35 : 1–3 .
  7. 1 2 Kolata, Gina (10 de diciembre de 1996). "Prueba matemática computacional muestra poder de razonamiento" . The New York Times . Recuperado el 10 de diciembre de 2025 .
  8. ↑ Bonacina, Maria Paola; Stickel, Mark E., eds. (2013). Razonamiento automatizado y matemáticas: ensayos en memoria de William W. McCune . Berlín, Heidelberg: Springer. pág. IX. ISBN  3642366740. Consultado el 10 de diciembre de 2025 .
  9. ↑ Wos, Larry (2013). «El legado de un gran investigador». En Bonacina, Maria Paola; Stickel, Mark E. (eds.). Razonamiento automatizado y matemáticas: ensayos en memoria de William W. McCune (PDF) . Berlín, Heidelberg: Springer. pág. 6. ISBN  3642366740. Consultado el 10 de diciembre de 2025 .
  10. ↑ Wampler-Doty, Matthew (2010). "Una demostración completa de la conjetura de Robbins" . The Archive of Formal Proofs .

Sitio web de McCune en EQP