Atomi nelle algebre di Boole
In un algebra di Boole B un atomo è un elemento x tale che non esiste nessun elemento tra x e 0 (minimo). $$ \forall y \in B \text{ se } y \le x \Rightarrow \begin{cases} y=0 \\ y=x \end{cases} $$
Esempio 1
Nel caso più semplice dell'algebra booleana B { 0, 1 } l'atomo è l'elemento 1.
$$ 1·0 = 1∧0 = inf(0,1) = 0 \\ 1·1 = 1∧1 = inf(1,1) = 1 $$
Questo esempio è però troppo semplice per spiegare cos'è un atomo di Boole.
Provo a farne un altro più complesso.
Esempio 2
L'insieme B { 1, 2, 3, 5, 6, 10, 15, 30 } dei divisori di 30 è un reticolo distribuito.
L'elemento 30 è il massimo mentre l'elemento 1 è il minimo.
Posso indicare il massimo con il simbolo 1 e il minimo con il simbolo 0.
Fissate due operazioni binarie e un complemento, il reticolo diventa un'algebra di Boole.
$$ ( B , \le , +, \cdot, \overline{ }, 0, 1 ) $$
Gli atomi dell'algebra di Boole sono gli elementi 2, 3, 5 perché non esiste nessun elemento tra loro e lo 0 (minimo).
A questi va aggiunto anche l'elemento 1 ossia il minimo (0) del reticolo.
In conclusione, gli atomi sono gli elementi 1,2,3,5.
Le caratteristiche degli atomi di Boole
Se un elemento x è un atomo, non esistono altri elementi y e z dell'algebra di Boole, entrambi diversi da x, tali che y∨z=x.
Esempio
Nell'esempio dei divisori di 30 non esiste una coppia di elementi tale che sup(y,z)=2.
Lo stesso si può dire per gli altri atomi 1, 3, 5.
Se un elemento x è un atomo allora il prodotto xy è uguale a 0 oppure a x per qualsiasi elemento di B. $$ \forall y \in B \Rightarrow xy=0 \text{ o } x $$.
Esempio
Il prodotto 2·3 equivale a trovare l'estremo inferiore inf(2,3) ed è uguale a 0.
$$ inf(2,3)=0 $$
Nel caso del prodotto 2·6, invece, è uguale a 2 ossia a x.
$$ inf(2,6)=2 $$
Se x e y sono due atomi il prodotto xy è uguale a 0. $$ xy=0 $$.
Esempio
Gli elementi 2 e 3 sono due atomi.
Il prodotto 2·3 è uguale all'estremo inferiore inf(2,3) ed è uguale a 0.
$$ inf(2,3)=0 $$
Se x è un elemento di B tale che il prodotto xy=0 per qualsiasi altro elemento y di B, allora x=0.
Esempio
xy | 0 | 2 | 3 | 5 | 6 | 10 | 15 | 1 |
---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 0 | 2 | 0 | 0 | 2 | 2 | 2 | 2 |
3 | 0 | 3 | 0 | 0 | 3 | 3 | 3 | 3 |
5 | 0 | 5 | 0 | 0 | 5 | 5 | 5 | 5 |
6 | 0 | 2 | 3 | 0 | 6 | 2 | 3 | 6 |
10 | 0 | 2 | 0 | 5 | 6 | 10 | 5 | 10 |
15 | 0 | 0 | 3 | 5 | 0 | 5 | 15 | 15 |
1 | 0 | 2 | 3 | 5 | 6 | 10 | 15 | 1 |
Ogni elemento x dell'algebra di Boole può essere scritto come somma di atomi (xi). Questa scrittura è unica a parte l'ordine degli atomi nella somma. $$ x = \sum δ_i x_i $$ dove δ = {0,1}
Esempio
La somma x+y equivale a trovare l'estremo superiore sup(x,y).
Quindi posso ottenere l'elemento 6 come 2+3.
$$ 2 + 3 = 2∨3 = sup(2,3) = 6 $$
Questa scrittura è unica. Può solo variare l'ordine degli elementi sup(2,3)=sup(3,2)=6.
Allo stesso modo ottengo tutti gli altri elementi di B.
x+y | 2 | 3 | 5 | descrizione | |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | |
2 | 1 | 0 | 0 | 2 | |
3 | 0 | 1 | 0 | 3 | |
5 | 0 | 0 | 1 | 5 | |
6 | 1 | 1 | 0 | 2∨3 | |
10 | 1 | 0 | 1 | 2∨5 | |
15 | 0 | 1 | 1 | 3∨5 | |
1 | 1 | 1 | 1 | 2∨3∨5 |
La combinazione delle n-ple ∂ è unica.
Da questo posso dedurre un'altra osservazione importante.
Un'algebra di Boole può essere composta da insiemi contenenti 2n elementi
Dimostrazione
Se un algebra di Boole ha n atomi allora le n-ple ordinate sono 2n, perché ∂ può assumere soltanto i valori 0 o 1.
Ogni n-pla è unica e individua un elemento dell'insieme. C'è una corrispondenza biunivoca tra questi aspetti.
Pertanto, la cardinalità dell'insieme è uguale alle n-ple ossia 2n.
Nota. Non esistono algebre di Boole con 10,11,12 elementi ecc perché non esiste nessun numero intero n tale che xn=10. Possono, invece, essere algebre di Boole gli insiemi con 2, 4, 8,16, 32 elementi e così via.