Álgebra de Boole (estructura) - Boolean algebra (structure)

En álgebra abstracta , un álgebra booleana o una red booleana es una red distributiva complementada . Este tipo de estructura algebraica captura propiedades esenciales tanto de operaciones de conjuntos como de operaciones lógicas . Un álgebra de Boole puede verse como una generalización de un álgebra de conjuntos de potencias o un campo de conjuntos , o sus elementos pueden verse como valores de verdad generalizados . También es un caso especial de un álgebra de De Morgan y un álgebra de Kleene (con involución) .

Cada álgebra booleana da lugar a un anillo booleano , y viceversa, 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 disyunción ∨). Sin embargo, la teoría de los anillos booleanos tiene una asimetría inherente entre los dos operadores, mientras que los axiomas y teoremas del álgebra booleana expresan la simetría de la teoría descrita por el principio de dualidad .

Rejilla booleana de subconjuntos

Historia

El término "álgebra de Boole" honra a George Boole (1815-1864), un matemático inglés autodidacta. Introdujo el sistema algebraico inicialmente en un pequeño folleto, The Mathematical Analysis of Logic , publicado en 1847 en respuesta a una controversia pública en curso entre Augustus De Morgan y William Hamilton , y más tarde como un libro más sustancial, The Laws of Thought , publicado en 1854. La formulación de Boole difiere de la descrita anteriormente en algunos aspectos importantes. Por ejemplo, la conjunción y la disyunción en Boole no eran un par dual de operaciones. El álgebra de Boole surgió en la década de 1860, en artículos escritos por William Jevons y Charles Sanders Peirce . La primera presentación sistemática del álgebra booleana y las celosías distributivas se debe a la Vorlesungen de 1890 de Ernst Schröder . El primer tratamiento extenso del álgebra booleana en inglés es el Álgebra universal de 1898 de AN Whitehead . El álgebra booleana como estructura algebraica axiomática en el sentido axiomático moderno comienza con un artículo de 1904 de Edward V. Huntington . El álgebra de Boole alcanzó la mayoría de edad como matemáticas serias con el trabajo de Marshall Stone en la década de 1930, y con la Teoría Lattice de 1940 de Garrett Birkhoff . En la década de 1960, Paul Cohen , Dana Scott y otros encontraron profundas nuevos resultados en la lógica matemática y la teoría axiomática de conjuntos utilizando vástagos del álgebra de Boole, a saber, obligando y modelos valiosos-booleana .

Definición

Un álgebra de Boole es una sexta tupla que consta de un conjunto A , equipado con dos operaciones binarias ∧ (llamadas "encuentro" o "y"), ∨ (llamada "unión" o "o"), una operación unaria ¬ (llamada " complemento "o" no ") y dos elementos 0 y 1 en A (llamados" inferior "y" superior ", o elemento" menor "y" mayor ", también denotados por los símbolos ⊥ y ⊤, respectivamente), de manera que para todos los elementos de un , b y c de a , los siguientes axiomas sostienen:

una ∨ ( segundo ∨ c ) = ( una ∨ segundo ) ∨ c	un ∧ ( b ∧ c ) = ( a ∧ b ) ∧ c	asociatividad
a ∨ b = b ∨ a	a ∧ b = b ∧ a	conmutatividad
a ∨ ( a ∧ b ) = a	a ∧ ( a ∨ b ) = a	absorción
a ∨ 0 = a	a ∧ 1 = a	identidad
una ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( una ∨ c )	un ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( una ∧ c )	distributividad
a ∨ ¬ a = 1	a ∧ ¬ a = 0	complementos

Sin embargo, tenga en cuenta que la ley de absorción e incluso la ley de asociatividad pueden excluirse del conjunto de axiomas, ya que pueden derivarse de los otros axiomas (consulte Propiedades probadas ).

Un álgebra booleana con un solo elemento se llama álgebra booleana trivial o álgebra booleana degenerada . (En trabajos más antiguos, algunos autores requerían que 0 y 1 fueran elementos distintos para excluir este caso).

De los tres últimos pares de axiomas anteriores (identidad, distributividad y complementos) se deduce, o del axioma de absorción, que

a = b ∧ a     si y solo si     a ∨ b = b .

La relación ≤ definida por a ≤ b si se cumplen estas condiciones equivalentes, es un orden parcial con el elemento mínimo 0 y el elemento mayor 1. El encuentro a ∧ b y la unión a ∨ b de dos elementos coinciden con su mínimo y superior , respectivamente, con respecto a ≤.

Los primeros cuatro pares de axiomas constituyen una definición de una red acotada .

De los primeros cinco pares de axiomas se deduce que cualquier complemento es único.

El conjunto de axiomas es auto-dual en el sentido de que si uno intercambia ∨ con ∧ y 0 con 1 en un axioma, el resultado es nuevamente un axioma. Por tanto, al aplicar esta operación a un álgebra booleana (o retícula booleana), se obtiene otra álgebra booleana con los mismos elementos; se llama su dual .

Ejemplos de

• El álgebra booleana no trivial más simple, el álgebra booleana de dos elementos , tiene solo dos elementos, 0 y 1, y está definida por las reglas:

• Tiene aplicaciones en lógica , interpretando 0 como falso , 1 como verdadero , ∧ como y , ∨ como o , y ¬ como no . Las expresiones que involucran variables y las operaciones booleanas representan formas de enunciado, y se puede demostrar que dos de tales expresiones son iguales usando los axiomas anteriores si y solo si las formas de enunciado correspondientes son lógicamente equivalentes .

• El álgebra booleana de dos elementos también se utiliza para el diseño de circuitos en ingeniería eléctrica ; aquí 0 y 1 representan los dos estados diferentes de un bit en un circuito digital , típicamente alto y bajo voltaje . Los circuitos se describen mediante expresiones que contienen variables, y dos de esas expresiones son iguales para todos los valores de las variables si y solo si los circuitos correspondientes tienen el mismo comportamiento de entrada-salida. Además, cada posible comportamiento de entrada-salida puede modelarse mediante una expresión booleana adecuada.

• El álgebra booleana de dos elementos también es importante en la teoría general de las álgebras booleanas, porque una ecuación que involucra varias variables es generalmente verdadera en todas las álgebras booleanas si y solo si es verdadera en el álgebra booleana de dos elementos (que puede ser verificada por un algoritmo de fuerza bruta trivial para un pequeño número de variables). Esto se puede usar, por ejemplo, para mostrar que las siguientes leyes ( teoremas de consenso ) son generalmente válidas en todas las álgebras de Boole:
  • ( a ∨ b ) ∧ (¬ a ∨ c ) ∧ ( b ∨ c ) ≡ ( a ∨ b ) ∧ (¬ a ∨ c )
  • ( a ∧ b ) ∨ (¬ a ∧ c ) ∨ ( b ∧ c ) ≡ ( a ∧ b ) ∨ (¬ a ∧ c )

• El conjunto de potencia (conjunto de todos los subconjuntos) de cualquier conjunto no vacío dado S forma un álgebra de Boole, un álgebra de conjuntos , con las dos operaciones ∨: = ∪ (unión) y ∧: = ∩ (intersección). El elemento más pequeño 0 es el conjunto vacío y el elemento más grande 1 es el conjunto S mismo.

• Después del álgebra booleana de dos elementos, el álgebra booleana más simple es la definida por el conjunto de potencias de dos átomos:

• El conjunto de todos los subconjuntos de S que son finitos o cofinitos es un álgebra de Boole, un álgebra de conjuntos .
• Comenzando con el cálculo proposicional con κ símbolos de oración, forme el álgebra de Lindenbaum (es decir, el conjunto de oraciones en el cálculo proposicional módulo de equivalencia lógica ). Esta construcción produce un álgebra booleana. De hecho, es el álgebra booleana libre sobre generadores κ. Una asignación de verdad en cálculo proposicional es entonces un homomorfismo de álgebra booleana de esta álgebra al álgebra booleana de dos elementos.
• Dado cualquier linealmente ordenado conjunto L con un elemento menos, el álgebra de intervalo es el álgebra más pequeña de subconjuntos de L que contienen todos los intervalos semiabiertos [ un , b ) de tal manera que una está en L y b se, ya sea en L o igual a ∞. Las álgebras de intervalo son útiles en el estudio de las álgebras de Lindenbaum-Tarski ; cada álgebra booleana contable es isomórfica a un álgebra de intervalo.

Diagrama de Hasse del álgebra de Boole de divisores de 30.

• Para cualquier número natural n , el conjunto de todos los divisores positivos de n , que define a ≤ b si a divide b , forma una red distributiva . Este enrejado es un álgebra booleana si y solo si n es libre de cuadrados . El elemento inferior y superior de este álgebra de Boole es el número natural 1 y n , respectivamente. El complemento de a viene dado por n / a . El encuentro y la unión de una y b viene dada por el máximo común divisor (MCD) y el menos común múltiplo (lcm) de una y b , respectivamente. La suma de anillos a + b viene dada por mcm ( a , b ) / mcd ( a , b ). La imagen muestra un ejemplo para n = 30. Como contraejemplo, considerando el n = 60 no libre de cuadrados , el máximo común divisor de 30 y su complemento 2 sería 2, mientras que debería ser el elemento inferior 1.
• Otros ejemplos de álgebras booleanas surgen de espacios topológicos : si X es un espacio topológico, entonces la colección de todos los subconjuntos de X que son tanto abiertos como cerrados forma un álgebra booleana con las operaciones ∨: = ∪ (unión) y ∧: = ∩ (intersección).
• Si R es un anillo arbitrario y definimos el conjunto de idempotentes centrales por
  A = { e ∈ R  : e ² = e , ex = xe , ∀ x ∈ R }
  entonces el conjunto A se convierte en un álgebra booleana con las operaciones e ∨ f  : = e + f - ef y e ∧ f  : = ef .

Homomorfismos e isomorfismos

Un homomorfismo entre dos álgebras de Boole A y B es una función f  : A → B tal que para todo a , b en A :

f ( a ∨ b ) = f ( a ) ∨ f ( b ),

f ( a ∧ b ) = f ( a ) ∧ f ( b ),

f (0) = 0,

f (1) = 1.

De esto se deduce que f (¬ una ) = ¬ f ( un ) para todos una en una . La clase de todas las álgebras de Boole, junto con esta noción de morfismo, forma una subcategoría completa de la categoría de celosías.

Un isomorfismo entre dos álgebras de Boole A y B es un homomorfismo f  : A → B con un homomorfismo inverso, es decir, un homomorfismo g  : B → A tal que la composición g ∘ f : A → A es la función identidad en A , y la composición f ∘ g : B → B es la función identidad en B . Un homomorfismo de álgebras de Boole es un isomorfismo si y solo si es biyectivo .

Anillos booleanos

Todo álgebra de Boole ( A , ∧, ∨) da lugar a un anillo ( A , +, ·) definiendo a + b  : = ( a ∧ ¬ b ) ∨ ( b ∧ ¬ a ) = ( a ∨ b ) ∧ ¬ ( a ∧ b ) (esta operación se llama diferencia simétrica en el caso de conjuntos y XOR en el caso de la lógica) y a · b  : = a ∧ b . El elemento cero de este anillo coincide con el 0 del álgebra de Boole; el elemento de identidad multiplicativo del anillo es el 1 del álgebra de Boole. Este anillo tiene la propiedad de que a · a = a para todo a en A ; los anillos con esta propiedad se denominan anillos booleanos .

Por el contrario, si se da un anillo booleano A , podemos convertirlo en un álgebra booleana definiendo x ∨ y  : = x + y + ( x · y ) y x ∧ y  : = x · y . Dado que estas dos construcciones son inversas entre sí, podemos decir que cada anillo booleano surge de un álgebra booleana y viceversa. Además, un mapa f  : A → B es un homomorfismo de álgebras booleanas si y solo si es un homomorfismo de anillos booleanos. Las categorías de anillos booleanos y álgebras booleanas son equivalentes.

Hsiang (1985) proporcionó un algoritmo basado en reglas para comprobar si dos expresiones arbitrarias denotan el mismo valor en cada anillo booleano. De manera más general, Boudet, Jouannaud y Schmidt-Schauß (1989) proporcionaron un algoritmo para resolver ecuaciones entre expresiones arbitrarias de anillos booleanos. Empleando la similitud de los anillos booleanos y las álgebras booleanas, ambos algoritmos tienen aplicaciones en la demostración automatizada de teoremas .

Ideales y filtros

Un ideales del álgebra de Boole A es un subconjunto I tal que para todo x , y en el que tenemos x ∨ y en el que por todas una en A tenemos un ∧ x en I . Esta noción de ideales coincide con la noción de anillo de ideales en el anillo de Boole A . Un ideal I de A se llama primer si me ≠ A y si un ∧ b en la que siempre implica una en I o B en I . Además, para cada a ∈ A tenemos que a ∧ -a = 0 ∈ I y luego a ∈ I o -a ∈ I para cada a ∈ A , si I es primo. Un I ideal de A se llama máximo si I ≠ A y si el único ideal que contiene I correctamente es el propio A. Para un I ideal , si un ∉ I y -a ∉ I , entonces I ∪ { a } o I ∪ { -a } está contenido propiamente en otro J ideal . Por lo tanto, que un I no es máximo y, por lo tanto, las nociones de ideal primo e ideal máximo son equivalentes en álgebras de Boole. Por otra parte, estas nociones coinciden con el anillo de los teóricos de ideal primo y ideal maximal en el anillo Boolean A .

El dual de un ideal es un filtro . Un filtro del álgebra de Boole A es un subconjunto p tal que para todo x , y en p tenemos x ∧ y en p y para todo a en A tenemos a ∨ x en p . El dual de un ideal máximo (o primo ) en un álgebra de Boole es ultrafiltro . Los ultrafiltros se pueden describir alternativamente como morfismos de 2 valores desde A hasta el álgebra booleana de dos elementos. La afirmación de que cada filtro en un álgebra de Boole se puede extender a un ultrafiltro se llama Teorema del Ultrafiltro y no se puede probar en ZF , si ZF es consistente . Dentro de ZF, es estrictamente más débil que el axioma de elección . El teorema del ultrafiltro tiene muchas formulaciones equivalentes: cada álgebra booleana tiene un ultrafiltro , cada ideal en un álgebra booleana puede extenderse a un ideal primo , etc.

Representaciones

Se puede demostrar que cada finita álgebra de Boole es isomorfo al álgebra de Boole de todos los subconjuntos de un conjunto finito. Por lo tanto, el número de elementos de cada álgebra booleana finita es una potencia de dos .

El célebre teorema de representación de Stone para álgebras booleanas establece que cada álgebra booleana A es isomórfica con el álgebra booleana de todos los conjuntos abiertos en algún espacio topológico ( compacto y totalmente desconectado de Hausdorff ).

Axiomática

La primera axiomatización de las celosías / álgebras booleanas en general fue dada por el filósofo y matemático inglés Alfred North Whitehead en 1898. Incluía los axiomas anteriores y adicionalmente x ∨1 = 1 yx ∧0 = 0. En 1904, el matemático estadounidense Edward V. Huntington (1874-1952) dio probablemente la axiomatización más parsimoniosa basada en ∧, ∨, ¬, incluso probando las leyes de asociatividad (ver recuadro). También demostró que estos axiomas son independientes entre sí. En 1933, Huntington estableció la siguiente axiomatización elegante para el álgebra de Boole. Requiere solo una operación binaria + y un símbolo funcional unario n , para ser leído como 'complemento', que satisfaga las siguientes leyes:

1. Conmutatividad : x + y = y + x .
2. Asociatividad : ( x + y ) + z = x + ( y + z ).
3. Ecuación de Huntington : n ( n ( x ) + y ) + n ( n ( x ) + n ( y )) = x .

Herbert Robbins preguntó de inmediato: si la ecuación de Huntington se reemplaza por su dual, a saber:

4. Ecuación de Robbins : n ( n ( x + y ) + n ( x + n ( y ))) = x ,

¿Forman (1), (2) y (4) una base para el álgebra de Boole? Al llamar a (1), (2) y (4) un álgebra de Robbins , la pregunta es: ¿Es cada álgebra de Robbins un álgebra booleana? Esta pregunta (que llegó a conocerse como la conjetura de Robbins ) permaneció abierta durante décadas y se convirtió en una pregunta favorita de Alfred Tarski y sus estudiantes. En 1996, William McCune del Laboratorio Nacional Argonne , basándose en trabajos anteriores de Larry Wos, Steve Winker y Bob Veroff, respondió afirmativamente a la pregunta de Robbins: cada álgebra de Robbins es un álgebra booleana. Para la prueba de McCune fue crucial el programa informático EQP que diseñó. Para una simplificación de la demostración de McCune, vea Dahn (1998).

Se ha trabajado más para reducir el número de axiomas; consulte Axiomas mínimos para el álgebra booleana .

Generalizaciones

Eliminar el requisito de existencia de una unidad de los axiomas del álgebra booleana produce "álgebras booleanas generalizadas". Formalmente, un retículo distributivo B es un retículo booleano generalizado, si tiene un elemento más pequeño 0 y para cualquier elemento a y b en B tal que a ≤ b , existe un elemento x tal que a ∧ x = 0 y a ∨ x = b. Definiendo a ∖ b como el único x tal que (a ∧ b) ∨ x = a y (a ∧ b) ∧ x = 0, decimos que la estructura (B, ∧, ∨, ∖, 0) es un booleano generalizado álgebra , mientras que (B, ∨, 0) es un semirretículo booleano generalizado . Las celosías booleanas generalizadas son exactamente los ideales de las celosías booleanas.

Una estructura que satisface todos los axiomas de las álgebras de Boole, excepto los dos axiomas de distributividad, se denomina red ortocomplementada . Las celosías ortocomplementadas surgen naturalmente en la lógica cuántica como celosías de subespacios cerrados para espacios de Hilbert separables .

Ver también

Notas

Referencias

Trabajos citados

• Davey, BA; Priestley, HA (1990). Introducción a las celosías y el orden . Libros de texto de matemáticas de Cambridge. Prensa de la Universidad de Cambridge.
• Cohn, Paul M. (2003), Álgebra básica: grupos, anillos y campos , Springer, págs. 51, 70–81, ISBN 9781852335878
• Givant, Steven; Halmos, Paul (2009), Introducción a las álgebras de Boole , Textos de pregrado en matemáticas , Springer , ISBN 978-0-387-40293-2.
• Goodstein, RL (2012), "Capítulo 2: El sistema auto-dual de axiomas" , Álgebra booleana , Publicaciones de Courier Dover, págs. 21 y siguientes, ISBN 9780486154978
• Huntington, Edward V. (1904). "Conjuntos de postulados independientes para el álgebra de la lógica" . Transacciones de la American Mathematical Society . 5 (3): 288-309. doi : 10.1090 / s0002-9947-1904-1500675-4 . JSTOR  1986459 .
• Padmanabhan, Ranganathan; Rudeanu, Sergiu (2008), Axiomas para celosías y álgebras booleanas , World Scientific, ISBN 978-981-283-454-6.
• Piedra, Marshall H. (1936). "La teoría de las representaciones para el álgebra de Boole" . Transacciones de la American Mathematical Society . 40 : 37-111. doi : 10.1090 / s0002-9947-1936-1501865-8 .
• Whitehead, AN (1898). Tratado de álgebra universal . Prensa de la Universidad de Cambridge. ISBN 978-1-4297-0032-0.

Referencias generales

• Brown, Stephen; Vranesic, Zvonko (2002), Fundamentos de la lógica digital con diseño VHDL (2ª ed.), McGraw – Hill , ISBN 978-0-07-249938-4. Consulte la Sección 2.5.
• Boudet, A .; Jouannaud, JP; Schmidt-Schauß, M. (1989). "Unificación en anillos booleanos y grupos abelianos" . Revista de Computación Simbólica . 8 (5): 449–477. doi : 10.1016 / s0747-7171 (89) 80054-9 .
• Cori, Rene; Lascar, Daniel (2000), Lógica matemática: un curso con ejercicios , Oxford University Press , ISBN 978-0-19-850048-3. Vea el Capítulo 2.
• Dahn, BI (1998), "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.

• Halmos, Paul (1963), Conferencias sobre álgebras booleanas , Van Nostrand, ISBN 978-0-387-90094-0.
• Halmos, Paul ; Givant, Steven (1998), Lógica como álgebra , Exposiciones matemáticas Dolciani, 21 , Asociación Matemática de América , ISBN 978-0-88385-327-6.
• Huntington, EV (1933a), "Nuevos conjuntos de postulados independientes para el álgebra de la lógica" (PDF) , Transactions of the American Mathematical Society , American Mathematical Society, 35 (1): 274-304, doi : 10.2307 / 1989325 , JSTOR  1989325.
• Huntington, EV (1933b), "Álgebra booleana: una corrección", Transactions of the American Mathematical Society , 35 (2): 557–558, doi : 10.2307 / 1989783 , JSTOR  1989783
• Hsiang, Jieh (2007). "Demostración del teorema de refutación mediante sistemas de reescritura de términos" . Inteligencia artificial . 25 (3): 255–300. arXiv : cond-mat / 0606434 . doi : 10.1016 / 0004-3702 (85) 90074-8 .
• Mendelson, Elliott (1970), Álgebra booleana y circuitos de conmutación , Serie de esquemas de Schaum en matemáticas, McGraw – Hill , ISBN 978-0-07-041460-0
• Monk, J. Donald; Bonnet, R., eds. (1989), Manual de álgebras booleanas , Holanda Septentrional , ISBN 978-0-444-87291-3. En 3 volúmenes. (Volumen 1: ISBN  978-0-444-70261-6 , Volumen 2: ISBN  978-0-444-87152-7 , Volumen 3: ISBN  978-0-444-87153-4 )
• Sikorski, Roman (1966), Álgebras de Boole , Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer Verlag.
• Stoll, RR (1963), Teoría y lógica de conjuntos , WH Freeman, ISBN 978-0-486-63829-4. Reimpreso por Dover Publications , 1979.

enlaces externos

• "Álgebra de Boole" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Enciclopedia de Filosofía de Stanford : " Las Matemáticas del Álgebra de Boole ", por J. Donald Monk.
• McCune W., 1997. Las álgebras de Robbins son booleanas JAR 19 (3), 263—276
• "Álgebra booleana" por Eric W. Weisstein , Proyecto de demostraciones Wolfram , 2007.
• Burris, Stanley N .; Sankappanavar, HP, 1981. Un curso de álgebra universal. Springer-Verlag. ISBN  3-540-90578-2 .
• Weisstein, Eric W. "Álgebra booleana" . MathWorld .