Cómo demostrar que los divisores de 15 forman un álgebra de Boole

Question

Esto del Ejercicio 3.1 de "Guía para principiantes de matemáticas discretas"

Sea B el conjunto de todos los divisores enteros positivos de 15, es decir, B = {1, 3, 5, 15}. Demostrar que B forma un álgebra booleana con elemento cero 1 y elemento unidad 15, siempre que las operaciones se definan como sigue: x+y es el mínimo común múltiplo de x e y, xy es el máximo común divisor, y x' es el cociente aritmético ordinario 15/x

Puedo ver simplemente calculando el HCF y el LCM para pares de 1 y 15 que lo siguiente se mantendrá.

1+1=1 1+15=15 15+1=15 15+15=15

1*1=1 1*15=1 15*1=1 15*15=15

1'=15 15'=1

Así que, esencialmente, para los dos elementos mencionados tengo las tablas de verdad completas para OR, AND y negación. Lo que no entiendo es qué hacer con los otros elementos {3,5}. ¿Tengo que demostrar de alguna manera que también están sujetos a los axiomas del álgebra de Boole? ¿Hay algún método de prueba más formal que debería utilizar para responder a esta pregunta?

Answer 1

Pista:

• Escribe números de la forma $3^\alpha \cdot 5^\beta$ para $\alpha,\beta \in \{0,1\}$ .
• Obsérvese que los divisores de $15$ escrito de la forma $\langle\alpha,\beta\rangle$ son esencialmente elementos de $\{0,1\} \times \{0,1\}$ .
• El conjunto de todos los vectores binarios de cierta longitud (aquí dos) forma un álgebra booleana cuyas operaciones son mínimo/conjunción y máximo/disyunción por componentes.

Espero que esto ayude $\ddot\smile$

Answer 2

Es un hecho general que $\mathbb{N}$ es una red distributiva con respecto a la relación de orden "divisor de": $$ a\mid b\quad\text{if and only if}\quad b=ac\text{ for some $ c $}. $$ El supremo y el ínfimo del par $\{a,b\}$ son el mínimo común múltiplo y el máximo común divisor, respectivamente.

Veamos la distributividad: $$ a\land(b\lor c)=(a\land b)\lor (a\land c). $$ Podemos excluir los casos en los que uno de los elementos es $0$ ya que $$ 0\land(b\lor c)=b\lor c,\qquad (0\land b)\lor(0\land c)=b\lor c $$ y $$ a\land(0\lor c)=a\land 0=a,\qquad (a\land 0)\lor(a\land c)=a\lor(a\land c)=a. $$ Entonces, supongamos que ninguno de los elementos es $0$ y se descomponen $a$ , $b$ y $c$ en productos de primos. Esto permite transferir los cálculos al mínimo y al máximo de pares de números naturales y se ve fácilmente que es distributivo.

El conjunto $D(n)$ de divisores de un número dado $n\ne0$ forman así una red distributiva que tiene un máximo, $n$ y un mínimo de $1$ porque $1$ es el mínimo en $(\mathbb{N},\,|\,)$ .

¿Cuándo es un álgebra booleana? Exactamente cuando $n$ es cuadrado libre, es decir, ningún cuadrado de un número primo divide a $n$ . De hecho, en este caso, para $a\in D(n)$ podemos ver que $n/a$ es un complemento de $a$ : $$ \gcd\left(a,\frac{n}{a}\right)=1,\qquad \operatorname{lcm}\left(a,\frac{n}{a}\right)=n, $$ Por otra parte, si $p^2\mid n$ ( $p$ un primo), $p$ no puede tener un complemento en $D(n)$ .