En matemáticas , un anillo booleano R es un anillo para el cual x 2 = x para todo x en R , [1] [2] [3] es decir, un anillo que consta solo de elementos idempotentes . [4] [5] Un ejemplo es el anillo de números enteros módulo 2 .
Cada anillo booleano da lugar a un álgebra booleana , con la multiplicación de anillos correspondiente a la conjunción o encuentro ∧, y la adición de anillos a la disyunción exclusiva o diferencia simétrica (no la disyunción [ , [6] que constituiría un semiring ). Los anillos booleanos llevan el nombre del fundador del álgebra booleana, George Boole .
Notaciones
Hay al menos cuatro sistemas de notación diferentes e incompatibles para anillos booleanos y álgebras:
- En álgebra conmutativa la notación estándar es utilizar x + Y = ( x ∧ ¬ Y ) ∨ (¬ x ∧ Y ) para la suma anillo de x y y , y el uso xy = x ∧ y por su producto.
- En lógica , una notación común es usar x ∧ y para el encuentro (igual que el producto del anillo) y usar x ∨ y para la unión, dada en términos de la notación del anillo (dada justo arriba) por x + y + xy .
- En teoría y lógica de conjuntos también es común usar x · y para el encuentro, y x + y para el conjunto x ∨ y . Este uso de + es diferente del uso en la teoría de anillos.
- Una convención poco común es usar xy para el producto y x ⊕ y para la suma del anillo, en un esfuerzo por evitar la ambigüedad de +.
Históricamente, el término "anillo booleano" se ha utilizado para significar un "anillo booleano posiblemente sin una identidad", y "álgebra booleana" se ha utilizado para significar un anillo booleano con una identidad. La existencia de la identidad es necesaria para considerar el anillo como un álgebra sobre el campo de dos elementos : de lo contrario, no puede haber un homomorfismo de anillo (unital) del campo de dos elementos en el anillo booleano. (Esto es lo mismo que el antiguo uso de los términos "anillo" y "álgebra" en la teoría de la medida . [A] )
Ejemplos de
Un ejemplo de anillo booleano es el conjunto de potencias de cualquier conjunto X , donde la suma en el anillo es una diferencia simétrica y la multiplicación es una intersección . Como otro ejemplo, también podemos considerar el conjunto de todos los subconjuntos finitos o cofinitos de X , nuevamente con la diferencia simétrica y la intersección como operaciones. De manera más general, con estas operaciones, cualquier campo de conjuntos es un anillo booleano. Según el teorema de representación de Stone, cada anillo booleano es isomorfo a un campo de conjuntos (tratado como un anillo con estas operaciones).
Relación con las álgebras de Boole
Dado que la operación de unión ∨ en un álgebra booleana a menudo se escribe de forma aditiva, tiene sentido en este contexto denotar la adición de anillos con ⊕, un símbolo que se usa a menudo para denotar o exclusivo .
Dado un anillo Boolean R , para x y y en R podemos definir
- x ∧ y = xy ,
- x ∨ y = x ⊕ y ⊕ xy ,
- ¬ x = 1 ⊕ x .
Estas operaciones luego satisfacen todos los axiomas para encuentros, uniones y complementos en un álgebra booleana . Así, cada anillo booleano se convierte en un álgebra booleana. De manera similar, cada álgebra booleana se convierte en un anillo booleano así:
- xy = x ∧ y ,
- x ⊕ y = ( x ∨ y ) ∧ ¬ ( x ∧ y ).
Si un anillo booleano se traduce en un álgebra booleana de esta manera, y luego el álgebra booleana se traduce en un anillo, el resultado es el anillo original. El resultado análogo se mantiene comenzando con un álgebra booleana.
Un mapa entre dos anillos booleanos es un homomorfismo de anillo si y solo si es un homomorfismo de las álgebras booleanas correspondientes. Además, un subconjunto de un anillo booleano es un ideal de anillo ( ideal de anillo principal, ideal de anillo máximo) si y solo si es un ideal de orden (ideal de orden principal, ideal de orden máximo) del álgebra de Boole. El anillo cociente de un anillo booleano módulo un anillo ideal corresponde al álgebra de factores del álgebra booleana correspondiente módulo el ideal de orden correspondiente.
Propiedades de los anillos booleanos
Cada anillo booleano R satisface x ⊕ x = 0 para todo x en R , porque sabemos
- x ⊕ x = ( x ⊕ x ) 2 = x 2 ⊕ x 2 ⊕ x 2 ⊕ x 2 = x ⊕ x ⊕ x ⊕ x
y dado que ( R , ⊕) es un grupo abeliano, podemos restar x ⊕ x de ambos lados de esta ecuación, lo que da x ⊕ x = 0. Una prueba similar muestra que cada anillo booleano es conmutativo :
- x ⊕ y = ( x ⊕ y ) 2 = x 2 ⊕ xy ⊕ yx ⊕ y 2 = x ⊕ xy ⊕ yx ⊕ y
y esto produce xy ⊕ yx = 0, lo que significa xy = yx (usando la primera propiedad anterior).
La propiedad x ⊕ x = 0 muestra que cualquier anillo booleano es un álgebra asociativa sobre el campo F 2 con dos elementos, precisamente de una manera. En particular, cualquier anillo booleano finito tiene como cardinalidad una potencia de dos . No todo álgebra asociativa unital sobre F 2 es un anillo booleano: considere, por ejemplo, el anillo polinomial F 2 [ X ].
El anillo cociente R / I de cualquier anillo booleano R módulo cualquier ideal I es de nuevo un anillo booleano. Asimismo, cualquier subanillo de un anillo booleano es un anillo booleano.
Cualquier localización de un anillo booleano R por un conjunto es un anillo booleano, ya que todos los elementos de la localización son idempotentes.
El anillo máximo de cocientes (en el sentido de Utumi y Lambek ) de un anillo booleano R es un anillo booleano, ya que todo endomorfismo parcial es idempotente. [7]
Cada ideal primo P en un anillo Boolean R es máxima : el anillo cociente R / P es un dominio de integridad y también un anillo de Boole, por lo que es isomorfo al campo F 2 , que muestra la maximalidad de P . Dado que los ideales máximos son siempre primos, los ideales primos y los ideales máximos coinciden en anillos booleanos.
Los anillos booleanos son anillos regulares de von Neumann .
Los anillos booleanos son absolutamente planos: esto significa que cada módulo sobre ellos es plano .
Todo ideal finitamente generado de un anillo booleano es principal (de hecho, ( x , y ) = ( x + y + xy )).
Unificación
La unificación en anillos booleanos es decidible , [8] es decir, existen algoritmos para resolver ecuaciones arbitrarias sobre anillos booleanos. Tanto la unificación como el emparejamiento en anillos booleanos libres generados de forma finita son NP-completos , y ambos son NP-duros en anillos booleanos finamente presentados . [9] (De hecho, como cualquier problema de unificación f ( X ) = g ( X ) en un anillo booleano puede reescribirse como el problema de emparejamiento f ( X ) + g ( X ) = 0, los problemas son equivalentes).
La unificación en anillos booleanos es unitaria si todos los símbolos de función no interpretados son nulares y finitarios de lo contrario (es decir, si los símbolos de función que no aparecen en la firma de los anillos booleanos son todos constantes, entonces existe un unificador más general y, de lo contrario, el conjunto mínimo completo de unificadores. es finito). [10]
Ver también
- Forma normal de suma de anillo
Notas
- ^ Cuando un anillo booleano tiene una identidad, entonces una operación de complemento se vuelve definible en él, y una característica clave de las definiciones modernas tanto del álgebra de Boole como del álgebra sigma es que tienen operaciones de complemento.
Referencias
- ^ Fraleigh (1976 , p. 200)
- ^ Herstein (1975 , p. 130)
- ↑ McCoy (1968 , p. 46)
- ^ Fraleigh (1976 , p. 25)
- ^ Herstein (1975 , p. 268)
- ^ https://math.stackexchange.com/q/1621618
- ^ B. Brainerd, J. Lambek (1959). "Sobre el anillo de cocientes de un anillo booleano". Boletín matemático canadiense . 2 : 25-29. doi : 10.4153 / CMB-1959-006-x . Corolario 2.
- ^ Martin, U .; Nipkow, T. (1986). "Unificación en anillos booleanos". En Jörg H. Siekmann (ed.). Proc. 8º CADE . LNCS. 230 . Saltador. págs. 506–513. doi : 10.1007 / 3-540-16780-3_115 . ISBN 978-3-540-16780-8.
- ^ Kandri-Rody, Abdelilah; Kapur, Deepak; Narendran, Paliath (1985). "Un enfoque teórico ideal para problemas de palabras y problemas de unificación sobre álgebras conmutativas presentadas de forma finita". Técnicas y aplicaciones de reescritura . Apuntes de conferencias en informática. 202 . págs. 345–364. doi : 10.1007 / 3-540-15976-2_17 . ISBN 978-3-540-15976-6.
- ^ A. Boudet; J.-P. Jouannaud ; M. Schmidt-Schauß (1989). "Unificación de anillos booleanos y grupos abelianos". Revista de Computación Simbólica . 8 (5): 449–477. doi : 10.1016 / s0747-7171 (89) 80054-9 .
Otras lecturas
- Atiyah, Michael Francis ; Macdonald, IG (1969), Introducción al álgebra conmutativa , Westview Press, ISBN 978-0-201-40751-8
- Fraleigh, John B. (1976), Un primer curso de álgebra abstracta (2a ed.), Addison-Wesley , ISBN 978-0-201-01984-1
- Herstein, IN (1975), Temas de álgebra (2a ed.), John Wiley & Sons
- McCoy, Neal H. (1968), Introducción al álgebra moderna (edición revisada), Allyn y Bacon , LCCN 68015225
- Ryabukhin, Yu. M. (2001) [1994], "Anillo booleano" , Encyclopedia of Mathematics , EMS Press
enlaces externos
- John Armstrong, anillos booleanos