Lezione 26 (17 maggio 1999 h. 9.30-11.30)

Prime proprietà delle algebre di Boole

Proposizione 26.1   Sia L un'algebra di Boole. Allora

1.

  $\forall a \in L$ si ha (a')'=a;

2.

  $\forall a,b\in L$ si ha $(a \wedge b)'= a' \vee b'$;

3.

  $\forall a,b\in L$ si ha $(a \vee b)'= a' \wedge b'$.

Le proprietà (2) e (3) vengono chiamate le leggi di de Morgan.

Dim.  (1). a' è il complemento di a, quindi $a\vee a'=1$ e $a \wedge a'=0$. Ma allora, a è un complemento di a', dall'unicità del complemento segue allora la tesi.

(2). Usando le proprietà distributive, commutative di $\wedge$ e $\vee$ e le proprietà dello 0 e dell'1 si ha:

$1 \wedge1 =1$	=	$1 \wedge1 =1$	(commutativa)
	=	$1 \wedge1 =1$	(distributiva)
	=	$1 \wedge1 =1$	(commutativa)
	=	$1 \wedge1 =1$	(associativa)
	=	$1 \wedge1 =1$	(complemento)
	=	$1 \wedge1 =1$	(1)

ed analogamente

$0 \vee0 =0$	=	$0 \vee0 =0$	(distributiva)
	=	$0 \vee0 =0$	(commutativa)
	=	$0 \vee0 =0$	(associativa)
	=	$0 \vee0 =0$	(complemento)
	=	$0 \vee0 =0$	(0)

Quindi $a' \vee b'$ è un complemento di $a\wedge b$. Per l'unicità del complemento si ha la tesi.

(3). Applichiamo la (2) a a' e b' si ottiene

$$(a')'\vee(b')'= (a'\wedge b')'$$

e quindi per la (1),

$$a \vee b = (a'\wedge b')'$$

Complementando entrambi i membri ed usando di nuovo la (1) si ha allora

$$(a \vee b)' = ((a' \wedge b')')'=a' \wedge b'$$

che è la tesi.     $\square$

Le algebre di Boole sono anelli booleani

Sia L un'algebra di Boole, definiamo due operazioni binarie su L ponendo:

$$\begin{eqnarray*}a+b & = & (a\wedge b')\vee(a'\wedge b) \\ ab & = & a \wedge b \end{eqnarray*}$$

Teorema 26.2   Sia L un'algebra di Boole, allora L con le operazionei + e $\cdot$ appena definite è un anello booleano.

Dim.  + è commutativa. Segue immediatamente dalla commutatività di $\vee$ e $\wedge$, infatti

$$b+a = (b \wedge a') \vee(b' \wedge a) = (b' \wedge a) \vee(b \wedge a') = (a \wedge b') \vee(a' \wedge b) = a+b$$

+ è associativa. Siano $a,b,c\in L$ allora, dalla definizione di + si ha

(a+b)+c	=	$(((a\wedge b')\vee(a'\wedge b)) \wedge c')\vee(((a\wedge b')\vee(a'\wedge b))'\wedge c)$
	=	$(((a\wedge b')\vee(a'\wedge b)) \wedge c')\vee(((a\wedge b')\vee(a'\wedge b))'\wedge c)$

Usando la distributività e l'associatività delle operazioni

$(a\wedge b'\wedge c')\vee(a'\wedge b\wedge c')$

=

$(a\wedge b'\wedge c')\vee(a'\wedge b\wedge c')$

Usando le formule di de Moivre e le altre proprietà

$(a'\wedge b'\wedge c) \vee(a\wedge b\wedge c)$	=	$(a'\wedge b'\wedge c) \vee(a\wedge b\wedge c)$
	=	$(a'\wedge b'\wedge c) \vee(a\wedge b\wedge c)$
	=	$(a'\wedge b'\wedge c) \vee(a\wedge b\wedge c)$
	=	$(a'\wedge b'\wedge c) \vee(a\wedge b\wedge c)$
	=	$(a'\wedge b'\wedge c) \vee(a\wedge b\wedge c)$
	=	$(a'\wedge b'\wedge c) \vee(a\wedge b\wedge c)$
	=	$(a'\wedge b'\wedge c) \vee(a\wedge b\wedge c)$

e quindi, in definitiva,

$$(a+b)+c=(a\wedge b'\wedge c') \vee(a'\wedge b\wedge c')\vee(a'\wedge b'\wedge c) \vee(a\wedge b\wedge c)$$

Ma ora, usando la commutatività di + e la formula appena provata, si ha:

$$\begin{eqnarray*}a+(b+c) & = & (b+c)+a \\ & = & (b \wedge c' \wedge a') \vee(b... ...edge b' \wedge c) \vee (a \wedge b \wedge c) \\ & = & (a+b)+c \end{eqnarray*}$$

Esistenza dello 0. Lo 0 dell'algebra di boole è anche 0 per l'anello. Infatti:

$$a+0 = (a \wedge0')\vee(a'\wedge0)=(a \wedge1)\vee(a'\wedge0) = a \vee0= a$$

Esistenza dell'opposto.

$$a + a =(a \wedge a')\vee(a'\wedge a) = 0 \vee0 = 0.$$

$\cdot$ è associativa. Segue immediatamente dall'associatività di $\wedge$.

Proprietà distributiva.

$$\begin{eqnarray*}a(b+c) & = & a\wedge((b\wedge c')\vee(b'\wedge c)) \\ & = & (... ...edge c)) \\ & = & (a\wedge b\wedge c')\vee(a\wedge b'\wedge c) \end{eqnarray*}$$

d'altra parte

$$\begin{eqnarray*}ab+ac & = & (a\wedge b)+(a\wedge c) \\ & = & ((a\wedge b) \we... ...edge c) \\ & = & (a\wedge b \wedge c') \vee(a'\vee b'\wedge c) \end{eqnarray*}$$

e quindi a(b+c)=ab+ac.

Esistenza dell'identità. L'1 dell'algebra è 1 anche per l'anello, dato che $1a=1\wedge a= a$ per ogni $a\in L$.

Ogni elemento è idempotente. Infatti

$$a^2=aa=a\wedge a = a$$

per ogni $a\in L$.     $\square$

Il teorema appena dimostrato dà un modo di definire una struttura di anello booleano a partire da quella di algebra di Boole, mentre il teorema 25.10 permetteva di fare il percorso inverso, ossia di ottenere una struttura di algebra di Boole a partire da quella di anello booleano. Effettivamente queste due costruzioni sono una l'inversa dell'altra, ossia

Teorema 26.3   Dato un anello booleano costruiamo l'algebra di boole come nel teorema 25.10 e da questa costruiamo l'anello booleano come nel teorema precedente, ritroviamo esattamente l'anello da cui si è partiti e vicersa, data un'algebra di Boole fattone l'anello booleano e quindi l'algebra di boole, si riottiene l'algebra di Boole di partenza.

Dim.  Sia R un anello booleano, allora la struttura di algebra di Boole è definita da

$$\begin{eqnarray*}a \vee b & = & a + b +ab \\ ab & = & a\wedge b \\ a' & = & 1 + a \end{eqnarray*}$$

A partire da questi si definiscono i due nuovi operatori di somma e prodotto ponendo:

$$\begin{eqnarray*}a \oplus b & = & (a \wedge b')\vee(a' \wedge b) \\ a \odot b & = & a \wedge b \end{eqnarray*}$$

Evidentemente $\odot =\cdot$. Ma, ricordando che un anello booleano è commutativo e ha caratteristica 2 si ha anche

$$\begin{eqnarray*}a \oplus b & = & (a \wedge b')\vee(a' \wedge b) \\ & = & (a \... ... + a^2b^2 \\ & = & a + b + ab + ab + ab + ab + ab + ab = a + b \end{eqnarray*}$$

e quindi anche $\oplus = +$.

Viceversa, sia L un'algebra di Boole. La struttura di anello è definita da:

$$\begin{eqnarray*}a+b & = & (a\wedge b')\vee(a'\wedge b) \\ ab & = & a \wedge b \end{eqnarray*}$$

a partire dalla quale viene definita una struttura di algebra di boole ponendo

$$\begin{eqnarray*}a \triangledown b & = & a + b + ab \\ a \vartriangle b & = & ab \end{eqnarray*}$$

Chiaramente $\vartriangle = \wedge$. D'altra parte

$$\begin{eqnarray*}a \triangledown b & = & a + b + ab \\ & = & ((a \wedge b')\ve... ...\vee a')\wedge b)\\ & = & (a \wedge1)\vee(1\wedge b) = a\vee b \end{eqnarray*}$$

e quindi anche $\triangledown = \vee$.     $\square$

Osservazione 26.4   Se X è un insieme allora le due strutture su ${\cal P}(X)$ di algebra di Boole e di anello booleano definite rispettivamente dalle operazioni $\cup$, $\cap$, $\complement$ e $\bigtriangleup$, $\cap$ sono in corrispondenza come dal teorema precedente. Questo segue evidentemente dalle formule:

$$\begin{eqnarray*}A \bigtriangleup B & = & (A\cap \complement B)\cup(\complement ... ...triangleup(A\cap B) \\ \complement A & = & X \bigtriangleup A \end{eqnarray*}$$

la prima delle quali è la definizione di $\bigtriangleup$ mentre la seconda e la terza sono di immediata verifica.

Definizione di morfismo di algebre di Boole

Definizione 26.5   Siano B e B' algebre di Boole, diremo che un'applicazione $\varphi:B\to B'$ è un morfismo di algebre di boole se per ogni $a,b\in B$ si ha

$$\begin{eqnarray*}\varphi(a \vee b) & = & \varphi(a)\vee\varphi(b) \\ \varphi(a... ...varphi(a)\wedge\varphi(b) \\ \varphi(a') & = & (\varphi(a))'. \end{eqnarray*}$$

Si dirà che $\varphi$ è un isomorfismo se e solo se è bigettivo.

Esercizio 26.1    Si provi che se $\varphi:B\to B'$ è un morfismo di algebre di Boole allora $\varphi(0)=0$ e $\varphi(1)=1$.
Soluzione

Si dimostra la seguente

Proposizione 26.6   Siano B e B' due algebre di Boole, allora $\varphi:B\to B'$ è un morfismo di algebre di boole se e solo se è un morfismo di anelli per le rispettive strutture di anello booleano.

Osservazione 26.7   La proposizione precedente mostra che il teorema 26.3 non solo dà una corrispondenza tra struttura di algebra di Boole e struttura di anello booleano, ma che tale corrispondenza non cambia l'insieme dei morfismi, in altre parole le due teorie da una parte quella degli anelli booleani e dall'altra quella delle algebre di Boole sono due facce della stessa medaglia e si possono usare contemporaneamente e tutti i risultati di una si traducono in risultati dell'altra.

Definizione di sottoreticoli e sottoalgebre di Boole

Definizione 26.8   Sia L un reticolo diremo che un sottoinsieme non vuoto $S\subseteq L$ è un sottoreticolo se e solo se

1.

$a,b\in S \Rightarrow a \vee b\in S$

2.

$a,b\in S \Rightarrow a \wedge b\in S$

Se L è un'algebra di Boole, diremo che S è una sottoalgebra di Boole se in più

1.

$a\in S\Rightarrow a'\in S$

Esercizio 26.2    Si provi che se L è un reticolo e S è un sottoreticolo di L allora S munito dell'ordinamento indotto da quello di L è un reticolo.
Soluzione

Osservazione 26.9   Visto l'esercizio precedente e tenendo conto che i reticoli possono essere definiti anche a partire dall'ordine, verrebbe voglia di prendere quella data nell'esercizio come definizione. In realtà in generale non è detto che S sia un sottoreticolo pur essendo un reticolo con l'ordinamento indotto. Affinché S sia un sottoreticole, è necessario anche che l'estremo inferiore (risp. superiore) fatto in S coincida con quello fatto in L.Si consideri ad esempio il reticolo L rappresentato nel diagramma di figura 1. Allora S₁, pur essendo un reticolo con l'ordinamento indotto, non è un sottoreticolo: l'estremo inferiore tra a e b fatto in S₁ è ), mentre fatto in L è c. S₂ è invece un sottoreticolo.

  

Figure 1: S₂ è un sottoreticolo di L ma non S₁

Proposizione 26.10   Sia B un'algebra di Boole, allora S è una sottoalgebra se e solo se è un sottoanello per la struttura di anello booleano.

Osservazione 26.11   La proposizione precedente mostra come anche la nozione di sottostruttura sia conservata dalla corrispondenza data dal teorema 26.3.

Esercizio 26.3    Si provi che se S è una sottoalgebra dell'algebra di Boole B, allora $0,1\in S$.
Soluzione

Teorema di rappresentazione per le algebre di Boole

Teorema 26.12   Sia L un'algebra di Boole. Allora esiste un insieme X tale che L è isomorfa ad una sottoalgebra di ${\cal P}(X)$. Se L è finita allora esiste X tale che L è isomorfa a ${\cal P}(X)$.

Dim.  È conseguenza immediata del teorema di rappresentazione per anelli booleani di quanto visto nelle proposizioni 26.6 e 26.10 e di quanto osservato in 26.4. Infatti per ilteorema di rappresentazione degli anelli booleani esiste un morfismo iniettivo di anelli booleani $\varepsilon: L \to {\cal P}(X)$ per un opportuno insieme X, che è anche surgettivo quando L è finito. Allora $\varepsilon$ è un morfismo di algebre di Boole quando si considerino le strutture corrispondenti, e quindi la tesi.     $\square$

Corollario 26.13   Se L è un'algebra di Boole finita, allora esiste n tale che $\left\vert L\right\vert =2^n$.

Esempio 26.14   Si consideri il reticolo L rappresentato nel diagramma di figurafig:S<L. Ci chiediamo: è un 'algebra di Boole? Per il corollario precedente, la risposta è chiaramente no, in quanto questo reticolo ha 6 elementi e 6 non è una potenza di 2.