Álgebra de Boole

Este artículo está sobre el sistema algebraico . Para conocer la rama de la lógica matemática que estudia las proposiciones y las operaciones sobre ellas, consulte Álgebra de la lógica .

El álgebra booleana [1] [2] [3] es un conjunto no vacío A con dos operaciones binarias (análogo de conjunción ), (análogo de disyunción ), una operación unaria (análogo de negación ) y dos elementos seleccionados: 0 (o Falso) y 1 (o Verdadero) tales que para cualquier a , b y c del conjunto A los siguientes axiomas son verdaderos : $\tierra$ $\lor$ $\lno$

$a \lor (b \lor c) = (a \lor b) \lor c$	$a \tierra (b \tierra c) = (a \tierra b) \tierra c$	asociatividad
$a\lor b = b\lor a$	$a \tierra b = b \tierra a$	conmutatividad
$a \lor (a \land b) = a$	$a \land (a \lor b) = a$	leyes de absorción
$a \lor (b \land c) = (a \lor b) \land (a \lor c)$	$a \land (b \lor c) = (a \land b) \lor (a \land c)$	distributividad
$a \lo \lno a = 1$	$a \tierra \lno a = 0$	adicionalidad

En la notación · + ¯

$\begin{align} & a+(b+c)=(a+b)+c & a(bc)=(ab)c \\ & a+b=b+a & ab=ba \\ & a+ab =a & a(a+b)=a \\ & a+bc=(a+b)(a+c) & a(b+c)=ab+ac \\ & a+\bar{a}=1 &a\bar{a} = 0 \end{alinear}$

Los primeros tres axiomas significan que ( A , , ) es una red . Por lo tanto, un álgebra booleana se puede definir como una red distributiva en la que se cumplen los dos últimos axiomas. Una estructura en la que se cumplen todos los axiomas menos el penúltimo se denomina pseudoálgebra booleana . Nombrado en honor a George Boole . $\tierra$ $\lor$

Algunas propiedades

Se puede ver a partir de los axiomas que el elemento más pequeño es 0, el más grande es 1 y el complemento ¬ a de cualquier elemento a está determinado de manera única. Para todo a y b de A , las siguientes igualdades también son verdaderas:

$a \lo a = a$	$a \tierra a = a$
$un \lor 0 = un$	$un \tierra 1 = un$
$a\lor 1 = 1$	$a\tierra 0 = 0$
$\lno 0 = 1$	$\lno 1 = 0$	complemento 0 es 1 y viceversa
$\lnot (a \lor b) = \lnot a \land \lnot b$	$\lnot (a \land b) = \lnot a \lor \lnot b$	leyes de Morgan
$\lno \lno un = un$ .		involutividad de la negación , la ley de eliminación de la doble negación .

Identidades básicas

Esta sección repite las propiedades y axiomas descritos anteriormente con la adición de algunos más.

Tabla resumen de propiedades y axiomas descritos anteriormente:

$a\lor b = b\lor a$	$a \tierra b = b \tierra a$	1 conmutatividad , portabilidad
$a \lor (b \lor c) = (a \lor b) \lor c$	$a \tierra (b \tierra c) = (a \tierra b) \tierra c$	2 asociatividad , compatibilidad
3.1 conjunción con respecto a la disyunción $a \lor (b \land c) = (a \lor b) \land (a \lor c)$	3.2 disyunción con respecto a la conjunción $a \land (b \lor c) = (a \land b) \lor (a \land c)$	3 distributividad , distributividad
$a \lo \lno a = 1$	$a \tierra \lno a = 0$	4 complementariedad , complementariedad (propiedades de las negaciones)
$\lnot (a \lor b) = \lnot a \land \lnot b$	$\lnot (a \land b) = \lnot a \lor \lnot b$	5 leyes de De Morgan
$a \lor (a \land b) = a$	$a \land (a \lor b) = a$	6 leyes de absorción
$a \lor(\lnot a \land b) = a \lor b$	$a \land(\lnot a \lor b) = a \land b$	7 Blake-Poretsky
$a \lo a = a$	$a \tierra a = a$	8 idempotencia
$\lno \lno un = un$		9 involutividad de la negación , la ley de eliminación de la doble negación
$un \lor 0 = un$	$un \tierra 1 = un$	10 propiedades constantes
$a\lor 1 = 1$	$a\tierra 0 = 0$
suma 0 es 1 $\lno 0 = 1$	suma 1 si 0 $\lno 1 = 0$
$(a \lor b)\land(\lno a \lor b)=b$	$(a \land b) \lor (\lno a \land b)=b$	11 Vinculación

Ejemplos

El álgebra booleana no trivial más simple contiene solo dos elementos, 0 y 1, y las acciones en ella están definidas por la siguiente tabla:

∧	0	una
0	0	0
una	0	una

∨	0	una
0	0	una
una	una	una

a	0	una
¬a	una	0

Esta álgebra booleana se usa más comúnmente en lógica , ya que es un modelo exacto del cálculo proposicional clásico . En este caso, 0 se llama falso , 1 se llama verdadero . Las expresiones que contienen operaciones booleanas y variables son formas proposicionales.

El conjunto de todos los subconjuntos de un conjunto dado S forma un álgebra booleana con respecto a las operaciones ∨ := ∪ (unión), ∧ := ∩ (intersección) y la operación de complemento unario. El elemento más pequeño aquí es el conjunto vacío , y el elemento más grande es el S entero .
Considere el conjunto de todos los divisores naturales de un número natural sin cuadrados dado . Definamos dos operaciones binarias: encontrar el máximo común divisor (análogo a la conjunción) y el mínimo común múltiplo (análogo a la disyunción); el papel de la negación lo juega una operación de un solo lugar que asigna un divisor a un divisor La estructura resultante es un álgebra booleana; en él, los análogos del cero booleano y el uno son, respectivamente, los números 1 y La disposición de los axiomas y propiedades generales anteriores del álgebra booleana para un conjunto da una serie de identidades teóricas de números útiles y no obvias [4] . $tu$ $metro,$ $tu$ $d$ ${\ estilo de visualización m/d.}$ $metro.$ $tu$
El álgebra de Lindenbaum-Tarski ( el conjunto factorial de todos los enunciados con respecto a la equivalencia en el cálculo dado con las operaciones correspondientes) de cualquier cálculo proposicional es un álgebra booleana. En este caso, la estimación de verdad de las fórmulas de cálculo es un homomorfismo del álgebra de Lindenbaum-Tarski en un álgebra booleana de dos elementos.
Si R es un anillo arbitrario , entonces el conjunto de idempotentes centrales se puede definir sobre él de la siguiente manera:
A = { e ∈ R : e ² = e , ex = xe , ∀ x ∈ R },
entonces el conjunto A será un Álgebra booleana con operaciones e ∨ f : = e + f − ef y e ∧ f := ef .

El principio de dualidad

Hay declaraciones duales en álgebras booleanas, ambas son verdaderas o ambas falsas. Es decir, si en una fórmula que es verdadera en algún álgebra booleana, cambiamos todas las conjunciones a disyunciones, 0 a 1, ≤ a > y viceversa, o < a ≥ y viceversa, entonces obtenemos una fórmula que también es verdadera en esta álgebra booleana. Esto se sigue de la simetría de los axiomas con respecto a tales reemplazos.

Representaciones de álgebras booleanas

Se puede demostrar que cualquier álgebra booleana finita es isomorfa al álgebra booleana de todos los subconjuntos de algún conjunto. De ello se deduce que el número de elementos en cualquier álgebra booleana finita será una potencia de dos.

El teorema de Stone establece que cualquier álgebra booleana es isomorfa al álgebra booleana de todos los conjuntos abiertos de algún espacio topológico compacto de Hausdorff totalmente desconectado .

Axiomatización

En 1933, el matemático estadounidense Huntington propuso la siguiente axiomatización para las álgebras booleanas:

Axioma de conmutatividad : x + y = y + x .
Axioma de asociatividad : ( x + y ) + z = x + ( y + z ).
Ecuación de Huntington : n ( n ( x ) + y ) + n ( n ( x ) + n ( y )) = x .

Aquí se usa la notación de Huntington: + significa disyunción, n significa negación.

Herbert Robbins planteó la siguiente pregunta: ¿es posible reducir el último axioma como está escrito a continuación, es decir, la estructura definida por los axiomas escritos a continuación será un álgebra booleana?

Axiomatización del álgebra de Robbins:

Axioma de conmutatividad : x + y = y + x .
Axioma de asociatividad : ( x + y ) + z = x + ( y + z ).
Ecuación de Robbins : norte ( norte ( x + y ) + norte ( x + norte ( y ))) = x .

Esta pregunta ha permanecido abierta desde la década de 1930 y ha sido una pregunta favorita de Tarski y sus alumnos.

En 1996, William McCune , utilizando algunos de los resultados obtenidos antes que él, dio una respuesta afirmativa a esta pregunta. Por lo tanto, cualquier álgebra de Robbins es un álgebra booleana.

Véase también

Notas

↑ DA Vladimirov. Obras de referencia en línea de Springer : álgebra booleana . Springer-Verlag (2002). Consultado el 4 de agosto de 2010. Archivado desde el original el 9 de febrero de 2012.
↑ Vladimirov, 1969 , pág. 19
↑ Kuznetsov, 2007 .
↑ Vilenkin N. Ya., Shibasov L. P. Shibasova 3. F. Detrás de las páginas de un libro de texto de matemáticas: Aritmética. Álgebra. Geometría: Libro. para estudiantes en los grados 10-11 educación general instituciones _ - M. : Educación : JSC "Literatura Educativa", 1996. - S. 197. - 319 p.

Literatura

Vladimirov D. A. Álgebras booleanas . - M. : "Nauka", 1969. - 320 p.
Kuznetsov OP Matemáticas discretas para un ingeniero . - San Petersburgo. : Lan, 2007. - 394 p.
Ivanov B. N. Matemáticas discretas. Algoritmos y programas. Curso Avanzado . - M. : "Izvestia", 2011. - 512 p. (enlace no disponible)
Gurov S. I. Álgebras booleanas, conjuntos ordenados, redes: definiciones, propiedades, ejemplos . - M. : Librokom, 2013. - 352 p.

diccionarios y enciclopedias	gran ruso universalis

Matemáticas discretas
combinatoria Teoría de grafos