stringtranslate.com

Álgebra de Boole (estructura)

En álgebra abstracta , un álgebra de Boole o red de Boole es una red distributiva complementada . Este tipo de estructura algebraica captura propiedades esenciales tanto de las operaciones de conjuntos como de las operaciones lógicas . Un álgebra de Boole puede verse como una generalización de un álgebra de conjuntos de potencias o un cuerpo 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) .

Toda álgebra de Boole da lugar a un anillo de Boole , y viceversa, correspondiendo la multiplicación de anillos a la conjunción o encuentro ∧, y la adición de anillos a la disyunción exclusiva o diferencia simétrica (no a la disyunción ∨). Sin embargo, la teoría de anillos de Boole tiene una asimetría inherente entre los dos operadores, mientras que los axiomas y teoremas del álgebra de Boole expresan la simetría de la teoría descrita por el principio de dualidad . [1]

Red booleana de subconjuntos

Historia

El término "álgebra de Boole" rinde homenaje a George Boole (1815-1864), un matemático inglés autodidacta. Introdujo el sistema algebraico inicialmente en un pequeño panfleto, 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 de Boole y los retículos distributivos se debe a las Vorlesungen de 1890 de Ernst Schröder . El primer tratamiento extenso del álgebra de Boole en inglés es Universal Algebra de AN Whitehead de 1898. El álgebra de Boole como una 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ática seria con el trabajo de Marshall Stone en la década de 1930, y con la Teoría de celosía de Garrett Birkhoff de 1940. En la década de 1960, Paul Cohen , Dana Scott y otros encontraron nuevos resultados profundos en la lógica matemática y la teoría de conjuntos axiomáticos utilizando ramificaciones del álgebra de Boole, a saber, modelos forzados y de valor booleano .

Definición

Un álgebra de Boole es un conjunto A , equipado con dos operaciones binarias (llamadas "encuentro" o "y"), (llamada "unión" u "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), tales que para todos los elementos a , b y c de A , se cumplen los siguientes axiomas : [2]

Obsérvese, sin embargo, 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 (ver Propiedades probadas).

Un álgebra de Boole con un solo elemento se denomina álgebra de Boole trivial o álgebra de Boole degenerada . (En trabajos más antiguos, algunos autores exigían que 0 y 1 fueran elementos distintos para excluir este caso). [ cita requerida ]

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

a = ba     si y sólo si     ab = b .

La relación definida por ab si se cumplen estas condiciones equivalentes, es un orden parcial con menor elemento 0 y mayor elemento 1. El encuentro ab y la unión ab de dos elementos coinciden con su ínfimo y supremo , 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 autodual en el sentido de que si se intercambia por y 0 por 1 en un axioma, el resultado es nuevamente un axioma. Por lo tanto, al aplicar esta operación a un álgebra de Boole (o red de Boole), se obtiene otra álgebra de Boole con los mismos elementos; se la llama su dual . [3]

Ejemplos

  • 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 esas expresiones son iguales usando los axiomas anteriores si y solo si las formas de enunciado correspondientes son lógicamente equivalentes .
  • El álgebra de Boole de dos elementos también se utiliza para el diseño de circuitos en ingeniería eléctrica ; [nota 1] 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 estas 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 se puede modelar mediante una expresión booleana adecuada.
  • El álgebra de Boole de dos elementos también es importante en la teoría general de las álgebras de Boole, porque una ecuación que involucra varias variables es generalmente verdadera en todas las álgebras de Boole si y solo si es verdadera en el álgebra de Boole de dos elementos (lo cual puede comprobarse mediante un algoritmo de fuerza bruta trivial para un pequeño número de variables). Esto puede usarse, por ejemplo, para mostrar que las siguientes leyes ( Teoremas de consenso ) son generalmente válidas en todas las álgebras de Boole:
    • ( ab ) ∧ (¬ ac ) ∧ ( bc ) ≡ ( ab ) ∧ (¬ ac )
    • ( a∧b ) ∨ ( ¬a∧c ) ∨ ( b∧c )( a∧b ) ( ¬a∧c )​
  • Después del álgebra de Boole de dos elementos, el álgebra de Boole más simple es la definida por el conjunto potencia de dos átomos:
Diagrama de Hasse del álgebra de Boole de divisores de 30.

se convierte en un álgebra booleana cuando sus operaciones están definidas por ef  := e + fef y ef  := ef .

Homomorfismos e isomorfismos

Un homomorfismo entre dos álgebras de Boole A y B es una función f  : AB 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 ello se deduce que fa ) = ¬ f ( a ) para todo a en A . 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 retículos.

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

Anillos booleanos

Toda álgebra de Boole ( A , ∧, ∨) da lugar a un anillo ( A , +, ·) al definir a + b  := ( a ∧ ¬ b ) ∨ ( b ∧ ¬ a ) = ( ab ) ∧ ¬( ab ) (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  := ab . El elemento cero de este anillo coincide con el 0 del álgebra de Boole; el elemento 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 llaman anillos booleanos .

Por el contrario, si se da un anillo booleano A , podemos convertirlo en un álgebra booleana definiendo xy  := x + y + ( x · y ) y xy  := x · y . [4] [5] Dado que estas dos construcciones son inversas entre sí, podemos decir que todo anillo booleano surge de un álgebra booleana, y viceversa. Además, una función f  : AB 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 ; [6] de hecho, las categorías son isomorfas .

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

Ideales y filtros

Un ideal del álgebra de Boole A es un subconjunto no vacío I tal que para todo x , y en I tenemos xy en I y para todo a en A tenemos ax en I . Esta noción de ideal coincide con la noción de ideal de anillo en el anillo booleano A . Un ideal I de A se llama primo si IA y si ab en I siempre implica a en I o b en I . Además, para todo aA tenemos que a ∧ − a = 0 ∈ I , y entonces si I es primo tenemos aI o aI para todo aA . Un ideal I de A se llama maximal si IA y si el único ideal que contiene apropiadamente a I es el propio A. Para un ideal I , si aI y aI , entonces I ∪ { a } o I ∪ {− a } está contenido en otro ideal propio J . Por lo tanto, tal I no es maximal, y por lo tanto las nociones de ideal primo e ideal maximal son equivalentes en las álgebras de Boole. Además, estas nociones coinciden con las de la teoría de anillos de ideal primo e ideal maximal en el anillo booleano A .

El dual de un ideal es un filtro . Un filtro del álgebra de Boole A es un subconjunto no vacío p tal que para todo x , y en p tenemos xy en p y para todo a en A tenemos ax en p . El dual de un ideal maximal (o primo ) en un álgebra de Boole es ultrafiltro . Los ultrafiltros pueden describirse alternativamente como morfismos de 2 valores desde A hasta el álgebra de Boole de dos elementos. La afirmación de que todo filtro en un álgebra de Boole puede extenderse a un ultrafiltro se llama lema del ultrafiltro y no puede probarse en la teoría de conjuntos de Zermelo-Fraenkel (ZF), si ZF es consistente . Dentro de ZF, el lema del ultrafiltro es estrictamente más débil que el axioma de elección . El lema del ultrafiltro tiene muchas formulaciones equivalentes: cada álgebra de Boole tiene un ultrafiltro , cada ideal en un álgebra de Boole puede extenderse a un ideal primo , etc.

Representaciones

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

El célebre teorema de representación de Stone para las álgebras de Boole establece que toda álgebra de Boole A es isomorfa al álgebra de Boole de todos los conjuntos abiertos y cerrados en algún espacio topológico ( de Hausdorff compacto y totalmente desconectado ).

Axiomática

La primera axiomatización de las redes/álgebras booleanas en general fue dada por el filósofo y matemático inglés Alfred North Whitehead en 1898. [7] [8] Incluía los axiomas anteriores y adicionalmente x ∨ 1 = 1 y x ∧ 0 = 0 . En 1904, el matemático estadounidense Edward V. Huntington (1874-1952) dio probablemente la axiomatización más parsimoniosa basada en , , ¬ , incluso demostrando las leyes de asociatividad (ver recuadro). [9] También demostró que estos axiomas son independientes entre sí. [10] En 1933, Huntington propuso la siguiente axiomatización elegante para el álgebra de Boole. [11] Requiere solo una operación binaria + y un símbolo funcional unario n , para ser leído como 'complemento', que satisfacen 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ó inmediatamente: Si la ecuación de Huntington se reemplaza por su dual, a saber:

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

¿(1), (2) y (4) forman una base para el álgebra de Boole? Si llamamos a (1), (2) y (4) un álgebra de Robbins , la pregunta entonces es: ¿toda álgebra de Robbins es un álgebra de Boole? 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 en el Laboratorio Nacional de Argonne , basándose en el trabajo anterior de Larry Wos, Steve Winker y Bob Veroff, respondió afirmativamente a la pregunta de Robbins: toda álgebra de Robbins es un álgebra de Boole. Crucial para la prueba de McCune fue el programa de computadora EQP que diseñó. Para una simplificación de la prueba de McCune, véase Dahn (1998).

Se han realizado más trabajos para reducir el número de axiomas; véase Axiomas mínimos para el álgebra de Boole .

Generalizaciones

Si eliminamos el requisito de la existencia de una unidad de los axiomas del álgebra de Boole, obtenemos "álgebras de Boole generalizadas". Formalmente, una red distributiva B es una red booleana generalizada si tiene un elemento mínimo 0 y para cualesquiera elementos a y b en B tales que ab , existe un elemento x tal que ax = 0 y ax = b . Si definimos a \ b como la única x tal que ( ab ) ∨ x = a y ( ab ) ∧ x = 0 , decimos que la estructura ( B , ∧, ∨, \, 0) es un álgebra de Boole generalizada , mientras que ( B , ∨, 0) es una semired booleana generalizada . Las redes booleanas generalizadas son exactamente los ideales de las redes booleanas.

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

Véase también

Notas

  1. ^ Estrictamente, los ingenieros eléctricos tienden a utilizar estados adicionales para representar otras condiciones del circuito, como alta impedancia (consulte IEEE 1164 o IEEE 1364) .

Referencias

  1. ^ Givant y Halmos 2009, pág. 20.
  2. ^ Davey y Priestley 1990, págs. 109, 131, 144.
  3. ^ Goodstein 2012, pág. 21 y siguientes.
  4. ^ Piedra 1936.
  5. ^ Hsiang 1985, pág. 260.
  6. ^ Cohn 2003, pág. 81.
  7. ^ Padmanabhan y Rudeanu 2008, pág. 73.
  8. ^ Whitehead 1898, pág. 37.
  9. ^ Huntington 1904, págs. 292-293.
  10. ^ Huntington 1904, pág. 296.
  11. ^ Huntington 1933a.

Obras citadas

Referencias generales

Enlaces externos