Logica di Boole

Materie:	Appunti
Categoria:	Matematica
Voto:	2.5 (2)
Download:	108
Data:	15.10.2001
Numero di pagine:	14
Formato di file:	.doc (Microsoft Word)

ALGEBRE DI BOOLE

Un insieme parzialmente ordinato è una coppia ordinata (X,U) dove X è un insieme non vuoto e ")" è una relazione binaria definita su X tale che
(a) xxX xXx (riflessività)
(b) (x, y,xX se x(y e yyx allora x y (antisimmetria)
(c) x, y, zxX se xXy e yyz allora xzz (transitivita').

La relazione xLy sarà letta dicendo che x è minore o uguale a y.
Un insieme parzialmente ordinato (X, U) è detto totalmente ordinato se ")" ha l'ulteriore proprietà.

(d) (x, yxX xXy oppure yyx.

Esempi di insiemi parzialmente ordinati:
1. Sia X un insieme e P(X) il suo insieme delle parti. Allora (P(X), () è un insieme parzialmente ordinato, ove ")" è la relazione di inclusione tra insiemi.

2. Sia N l'insieme dei numeri naturali e s sia l'usuale ordinamento dei numeri naturali. Allora ( N, ) è un insieme totalmente ordinato.

3. L'insieme (N, |) è un insieme parzialmente ordinato, ove la relazione | è definita su N nel modo seguente: m | n se e solo se m divide n.

Se (X, S) è un insieme totalmente ordinato e ) è la relazione su X così definita: x y se e solo se xyy e xyy, allora y è detto ordine stretto indotto da .
Talvolta diremo che X è un insieme parzialmente ordinato, omettendo di scrivere (X, T).
Sia X un insieme parzialmente ordinato, una catena in X è un sottoinsieme di X che è totalmente ordinato dalla relazione d'ordine di X.
Sia A un sottoinsieme dell'insieme parzialmente ordinato X, un maggiorante per A in X e' un elemento x di X tale che y x per ogni yxA.
Analogamente, xAX è un minorante per A in X se e solo se x y yyyy.
Un elemento xUX è detto estremo superiore di A, in simboli sup(A), se x è un maggiorante per A in X ed è un minorante per l'insieme di tutti i maggioranti per A in X.
Così xCX è sup(A) se e solo se per ogni zXX, z,x, e dato un maggiorante y per A in X, risulta xxy.
Analogamente xAX è detto essere estremo inferiore di A, in simboli inf(A), se per ogni z , x,z e dato un minorante y per A in X, risulta yzx.
Se A S{a i | i ( I} è una famiglia di elementi dell'insieme X, noi spesso scriviamo: ( i I ai, al posto di sup(A); e ( i I ai al posto di inf(A).
Se A = {x, y} scriviamo x(y al posto di sup(A) e x(y al posto di inf(A).
Sia A e' un sottoinsieme di un insieme parzialmente ordinato X. Diciamo che A ha massimo elemento se e solo se esiste sup(A) e sup(A) aA. Analogamente diciamo che A ha minimo elemento se e solo se esiste inf(A) e inf(A) AA.

Definizione 1.
Un reticolo è un insieme L parzialmente ordinato in cui, per ogni due elementi x, y L, esistono x(y e x(y.

Esempio 4.
L'insieme parzialmente ordinato (P(X), (), dell'Esempio 1, è un reticolo. In questo caso per ogni A,B) P(X), A(B B inf({A, B}) e A(B B sup({A, B}).

Lemma 1.
Se un reticolo L ha un maggiorante, allora esso è unico.
Dimostrazione.
Supponiamo che x e y siano maggioranti di L. Poiché L è un reticolo, allora esiste x(y in L, e, dalla definizione di estremo superiore x y x(y e y y x(y. Ma x e y sono maggioranti per L, così x(y y x e x(y y y
Dalla proprietà di antisimmetria della relazione , segue che x,x(yyy. (

Analogamente si ha

Lemma 2.
Se un reticolo ha un minorante, esso è unico.

Lemma 3.
Sia L un reticolo e X, Y sottoinsiemi finiti di L. Allora inf(X)(inf(Y) i inf(X(Y).
Dimostrazione.
Sia jSinf(X)( inf(Y), allora si ha:
a) jainf(X)ix x x(X
b) jbinf(Y)iy y y Y
c) jcu ( u ( X(Y.
Da c) possiamo affermare che j è un minorante per X(Y. Sia, ora, m un minorante per X(Y allora si ha:
e) m x x X
f) m y y Y
Da e) ed f) si ha :
g) m(inf(X) e m(inf(Y).
Così otteniamo che mm j. Da ciò e da c) si ha l’asserto. (

Chiameremo massimo di L, e lo denoteremo con 1, l'unico maggiorante di L, quando esiste.
Chiameremo minimo di L, e lo denoteremo con 0, l'unico minorante di L, quando esiste.
Un elemento x di un reticolo L è detto essere massimale se non esiste alcun elemento yUL tale che xLy. Sottolineamo qui che il Lemma di Zorn stabilisce che se X è un insieme parzialmente ordinato in cui ogni catena ha un maggiorante allora X contiene un elemento massimale.

Definizione 2
Un reticolo L è detto essere complementato se esso ha un massimo elemento 1, un minimo elemento 0, e per ogni x L esiste un elemento yLL tale che

L5: xLyy1 e x1yy0

Tale elemento y è detto un complemento di x. In un reticolo complementato ogni elemento non necessariamente ha un unico complemento.
Consideriamo, per esempio, il reticolo definito sull'insieme
X X {0, a, b, c, 1} mediante la relazione data da: per ogni x, y X, xXy se e solo se x 0 oppure y 1.
Allora, poiché nel reticolo X valgono le seguenti relazioni:
a(b = b(c = c(a = 1, e a(b = b(c = c(a = 0, ogni elemento dell’insieme {a, b, c} è complemento degli altri due dello stesso insieme.

Sia L un reticolo limitato. L è detto distributivo se in esso valgono le seguenti condizioni:

( x, y, z ( L (x(y)(z = (x(z) ( (y(z) e (x(y)(z = (x(z)((y(z).

Proposizione 1.
Sia L un reticolo limitato distributivo complementato. Allora ogni elemento di L ha un unico complemento.
Dimostrazione.
Supponiamo che b, c ( L siano complementi di a ( L. Allora, b(a=1 e b(a=0; c(a=1 e c(a=0.
Proviamo che cPb. Invero si ha che b(c=(b(c) ( (c(a)=(b(a)(c=1(c=c. Cosi otteniamo che c= b(c, cioe' ccb. Analogamente si prova che bbc. Allora b=c. (

In un reticolo distributivo complementato L denoteremo con x* l'unico complemento di x.

Definizione 3.
Una algebra di Boole (algebra Booleana) è un reticolo distributivo complementato.

Alternativamente possiamo definire un'algebra Booleana B come una struttura algebrica B = B, B, ,, *, 0, 1, soddisfacente le seguenti condizioni:

B1 xBy = yyx xxy = yyx
B2 xB(y(z) = (xzy)yz xz(y(z) = (xzy)yz
B3 (xBy)yy = y (xyy)yy = y
B4 xBx* = 1 x x* = 0
B5 (xBy)yz = (xzz)z(y(z) (xzy)yz = (xzz)z(y(z)

In B possiamo definire una relazione d'ordine " " nel modo seguente:

" a, b B a b a = a b

Rispetto alla relazione R, sopra definita, B risulta un reticolo distributivo limitato complementato con 0 come minimo e 1 come massimo e con x*
come complemento di x.

Esempio 5:
Sia X un insieme e P(X) l'insieme di tutti i sottoinsiemi di X. Allora (P(X), S) è un'algebra di Boole.

Esempio 6:
Sia X un insieme. Un sottoinsieme A di X è detto cofinito se X \A è finito. Sia Z(X) l'insieme di tutti i sottoinsiemi finiti e di tutti i sottoinsiemi cofiniti di X. Allora (Z(X), S) è un'algebra di Boole.

Lemma 4.
Sia B un’algebra di Boole e a, b ( B. Allora vale la seguente implicazione:

a a b ==> b* a*

Dimostrazione:
Invero, vale la seguente catena di implicazioni:
a a b ==> a b* = 0 ==> (a b*) a* = a* ==> (a a*) (b* a*) = a* ==> 1 (b* a*) = a* ==> b* a* = a* ==> b* a * . (

Lemma 5.
Sia B una algebra di Boole. Allora, per ogni a( B si ha a** = a.
Dimostrazione:
Invero vale la seguente catena di equivalenze:

a a a* = 1 ( a** (a a*) = a** ( (a** a) a (a** a*) = a**(

( a** a = a** ( a** a .

Analogamente si ha:

a a a* = 0 ( a** (a ( a*) = a** ( (a** a) (a** a*) = a** (

( a** a = a** ( a a** .

Cosi' da a** C a e a a** segue a = a**. (

Lemma 6. (De Morgan)
Sia B una algebra di Boole. Allora per ogni a,bSB si ha :
(a ( b)* = a* b* e (a b)*= a* b*
Dimostrazione:
Poiché a(b b a e a(b b b, allora a* a*(b* e b* b a*(b*. Da ciò segue a*(b* b (a(b)*. Inoltre si ha a*(a*(b* e b*(a*(b*, quindi (a*(b*)* b a e (a*(b*)* b b. Così otteniamo che (a*(b*)* b a(b, cioè (a(b)* b a*(b*. Abbiamo così ottenuto che valgono contemporaneamente le seguenti relazioni: (a*(b*)(a*(b* e a*(b*((a(b)*. Da ciò l’uguaglianza a* b b* = (a b)*. Analogamente si ottiene a* b* = (a b)*. (

Definizione 4.
Un filtro in un reticolo L è un sottoinsieme non vuoto F di L soddisfacente le seguenti proprietà:
(a) x x y F x, y F
(b) x y ==> y F x F, y L

Definizione 5.
Un ideale in un reticolo L è un sottoinsieme non vuoto I di L tale che:
(a') x ( y I x, y I
(b') x ( I, y L y x ==> y I

E' chiaro che se un reticolo L ha un elemento massimo 1 allora ogni filtro in L contiene 1. Analogamente se L ha un elemento minimo 0, allora ogni ideale in L contiene 0.

Definizione 6.
Per ogni xPL, l'insieme {yL x y} è un filtro, esso è detto il filtro principale generato da x.
Analogamente {y Ay y x } è un ideale, esso è detto l'ideale principale generato da x.

Osserviamo che in un reticolo finito ogni filtro e ogni ideale è principale.

Un filtro F in un reticolo L è detto essere proprio se F è un sottoinsieme proprio di L, i.e., FU L. Chiaramente se L ha 0 allora F è proprio se e solo se 0 F.
Analogamente un ideale I di L è proprio se IAL. Se L ha l'elemento 1 allora un ideale è proprio se e solo se 1oI.

Si può vedere che nelle identità di B1 – B5, se noi intercambiamo i simboli ( e ( ed i simboli 0 e 1, le identità si trasformano in altre identità che valgono in ogni algebra di Boole.
Le affermazioni ottenute mediante queste trasformazioni sono dette "duali" delle date affermazioni. Segue che l'affermazione duale di ogni affermazione vera su un'algebra di Boole, espressa in termini i, ,, 0 e 1 è ancora vera circa la stessa algebra. Quando le affermazioni contengono i termini di ideale o di filtro, si possono ottenere ancora affermazioni "duali" scambiando tra loro questi termini, come pure si possono scambiare tra loro i simboli "o" con """ per avere proposizioni duali.

Lemma 7.
Sia B un' algebra di Boole. Allora, per ogni x, y a B si ha che le seguenti sono equivalenti:
i) x (y* y 0
ii) x x y.
Dimostrazione
Dimostriamo che i) implica ii). Supponiamo che sia x( y* 0. Allora
x = x ( 1 = x ( (y ( y*) (x ( y) ( (x ( y*) x ( y y.
Dimostriamo ora che ii) implica i). Invero, se x l y, allora x ( y = x e quindi
x ( y* = (x ( y) ( y* (x ( (y y*)) = x ( 0 =0. (
Ora, dualmente, possiamo ottenere la seguente equivalenza: x ( y* 1 1 y x.

Nel seguito, una volta dimostrato un teorema in una algebra di Boole, assumeremo che anche il suo duale sia stato stabilito.
Un sottoinsieme A di una algebra di Boole è detto avere la proprietà della intersezione finita "PIF" se il minimo di ogni sottoinsieme finito di A non è 0.
L'importanza di questa proprietà consiste nel fatto che proprio quei sottoinsieme di un' algebra di Boole che hanno la "PIF" possono essere estesi a filtri propri.
Se A è un insieme di elementi di un'algebra di Boole B, indichiamo con A0 l'insieme di quegli elementi di B maggiori di qualche elemento di A, ovvero si ha:

A0 = {x B per qualche a p A, a x}.

Indichiamo con Ac l'insieme degli estremi inferiori di tutti i sottoinsiemi finiti di A,
i.e.
Ac = inf(X)iXXSw(A)(

ove Sw(A) è l'insieme di tutti i sottoinsiemi finiti di A.
Una base per un filtro F è un insieme A tale che A0 = F. Una sottobase per un filtro è un insieme A tale che Ac è una base per F. Se A è una sottobase per F allora F = (Ac)0, in questo caso diciamo che A genera F. Osserviamo che A, Acc(Ac)0.

Lemma 8.
Per ogni sottoinsieme A di una algebra di Boole B. Allora valgono le seguenti affermazioni:

1) l'insieme (Ac)0 è un (non necessariamente proprio) filtro;

2) ogni filtro contenente A contiene (Ac)0;

3) (Ac)0 è proprio se e solo se A soddisfa la PIF.
Dimostrazione.
Dimostriamo la 1). Supponiamo x, y S (Ac)0. Allora esistono X, Y A Sw(A) tali che inf(X) ( x inf(Y) y. Da cio' segue che inf(X) ( inf(Y) x ( y. Inoltre, poiche' inf(X ( Y) = inf(X) ( inf(Y) segue inf(X ( Y) x ( y. Cosi', osservando che X Y Sw(A), segue che x ( y (Ac)0 . Supponiamo ora
x x (Ac)0 e x y. Da cio' segue ovviamente che y (Ac)0 . Cosi abbiamo provato che (Ac)0 è un filtro.
Dimostriamo la 2). Supponiamo che F sia un filtro tale che ADF e che x F (Ac)0. Allora esiste X . Sw(A) tale che inf(X) x. Poiché X F e F è filtro allora si ha inf (X) F F. Inoltre inf(X) x. Ancora, poiché F è filtro, segue che x F. Così (Ac)0 F.
Dimostriamo, infine, la 3). Supponiamo che (Ac)0 sia filtro proprio, e per assurdo che A non soddisfi la PIF. Allora esiste XrSw(A) tale che inf(X) ( 0. Perciò 0 ( (AC)0. Quindi (Ac)0 non è proprio, e cio' contraddice l'assunzione che (Ac)0 fosse proprio. Viceversa, assumiamo che A soddisfi la PIF, e per assurdo che (Ac)0 non sia proprio. Allora 0 ( (Ac)0. Quindi deve esistere un insieme X ( Sw(A) | inf(X) ( 0. Da cio' segue che inf(X) = 0. Cosi si ottiene che A non soddisfa la PIF, contrariamente a quanto avevamo assunto.

Da questo lemma segue che un sottoinsieme A di un’algebra di Boole può essere esteso a un filtro (proprio) se e solo se A gode la PIF.

Sia B una algebra di Boole e F un suo filtro proprio. Diciamo che F e' ultrafiltro di B se e solo se per ogni filtro proprio G di B tale che F G si ha F=G. Vale a dire che F e' ultrafiltro se e solo se esso non e' strettamente contenuto, come sottoinsieme di B, in nessun altro filtro proprio di B.

Lemma 9.
Se F è un filtro in un’algebra booleana B. Allora le seguenti sono equivalenti:
i. F è ultrafiltro
ii. ( x ( B, x ( F oppure x* ( F e x ( x*( F
Dimostrazione.
Dimostriamo che ii) implica i). Per assurdo, supponiamo che esista un filtro proprio G di B tale che FsG. Allora esiste un elemento x( G – F. Poiche'
x ( F, segue che x* ( F. Allora si ha che x ( G e anche che x* ( G. Poiche' G e' filtro, segue che 0= x ( x* ( G. Allora G risulta essere un filtro non proprio, contro l'assunzione che G fosse proprio. Cosi, non esiste un elemento
x( G – F. Cioe' G=F. Inoltr e' evidente che F e' proprio, perche' da ii) non puo' contenere contemporaneamente sia 0 che 1.
Dimostriamo ora che i) implica ii). Supponiamo che F sia ultrafiltro e che x ( F. Sia G il filtro generato da F ( {x}. Poiché F è ultrafiltro, allora G non è proprio. Quindi l’insieme F ( {x} non gode della PIF. Quindi esiste X ( Sw(F) | inf(X) ( x = 0, quindi inf (X) ( x* e, poiché inf (X) ( F, questo perché X è sottoinsieme finito di F e F e' chiuso rispetto all'inf di un numero finito di elementi, risulta che x* ( F. (

Teorema 1.
Ogni filtro proprio in una algebra di Boole può essere esteso ad un ultrafiltro.
Dimostrazione
Sia B un’algebra di Boole e F un filtro proprio di B. Sia F l’insieme di tutti i filtri propri che contengono F. Ovviamente F ( F ( (. Invero, (F, () è un insieme parzialmente ordinato, proviamo che in (F, () tutte le catene hanno un maggiorante.
Sia D = {Di i ( I} una catena in F. Sia D = (I Di (come insieme in B). Se x, y ( D allora ( i, j ( I | x ( Di; y ( Dj. Poiché D è una catena, si ha (diciamo) Di ( Dj, allora x, y ( Dj e poiché Dj è filtro, allora x ( y ( Dj( D. Se z ( B e x ( z, allora z ( Dj( D. Poiché 0( Di per ogni i ( I segue che 0(D. Da qui segue che D è un filtro. Poiché F ( D, segue che D ( F, allora D è un maggiorante per D in F.
Per il Lemma di Zorn F contiene un elemento massimale G, allora G è l’ultrafiltro richiesto. (

Corollario 1.
Ogni sottoinsieme di un’algebra di Boole soddisfacente la PIF, può essere esteso ad un ultrafiltro.
Dimostrazione.
Per il teorema precedente e il lemma degli ultrafiltri. (

Corollario 2.
Sia B un’algebra di Boole e x ( B\{0}. Allora, x è contenuto in qualche ultrafiltro.
Dimostrazione.
Se x ( 0, allora {x} ha la PIF e quindi può essere esteso ad un ultrafiltro. (

Corollario 3.
Sia B un’algebra di Boole. Se x ( y ( B allora ( un ultrafiltro U tale che
x ( U e y( U.
Dimostrazione.
Poiché x ( y non può essere che x ( y e y ( x. Diciamo che non sia vero che y x. Quindi, per il Lemma 7, x ( y* ( 0. Percio' l'insieme H={x, y*} soddisfa la PIF. Percio' H puo' essere esteso ad un ultrafiltro F di B. Poiche' H ( F, segue che y* (F, e poiche' F e' ultrafiltro, allora deve essere y ( F. Cosi' otteniamo che x ( F e y ( F. (

Definizione 7
Sia B un’algebra di Boole, un sottoinsieme A ( B tale che 0, 1 ( A e che sia chiuso rispetto alle operazioni (, ( e * è detto sottoalgebra.

E' facile vedere che in ogni algebra di Boole B il sottoinsieme {0,1} e'
sottoalgebra di B.

Definizione 8
Siano B1, B2 algebre di Boole. L’applicazione f: B1( B2 tale che:
• f(x(y) = f(x) ( f(y)
• f(x(y) = f(x) ( f(y)
• f(x*) = (f(x))*

è detta omomorfismo.

Proposizione 2.
Sia f un omomorfismo tra algebre di Boole. Allora f(0) = 0 e f(1) = 1.
Dimostrazione
Osserviamo che f(0) = f(1*) = (f(1))* Ovviamente abbiamo anche che f(0) = f(0(1) = f(0) ( f(1) = (f(1))* ( f(1) = 0. Analogamente si ha che f(1) = f(0*) = (f(0))* = 0* = 1. (

Proposizione 3.
Sia f un omomorfismo allora per ogni x e y , x ( y implica f(x) ( f(y).
Dimostrazione
Da x ( y si ha che y = x ( y ( f(y) = f(x ( y) ( f(y) = f(x) ( f(y) ( f(y) ( f(x). (

Sia f: B1 ( B2 un omomorfismo. Se f è biettiva allora f è un isomorfismo. Per indicare cio' scriveremo B1 ( B2.

Sia F un filtro di B, dove B è un’algebra di Boole. Definiamo la relazione (F su B nel modo seguente: x (F y ( ( z ( F | x ( z = y ( z.

Lemma 10.
(F è una relazione di equivalenza.

Dimostrazione.
Dobbiamo dimostrare che (F è riflessiva, simmetrica e transitiva. Osserviamo innanzitutto che poiche' F e' filtro allora esiste z ( F; cioe' F ( (; inoltre x ( z = x ( z per ogni x ( B. Cosi' e' dimostrata la riflessivita' di (F. La simmetria e' ovvia. Per dimostrare la transitivita' assumiamo che x (F y e y (F z . Allora esisteranno due elementi f e g di F tali che x ( f = y e y ( g = z ( g. Allora
x ( (f ( g) = (x ( f) ( g = (y ( f) ( g = (y ( g) ( f = (z ( g) ( f = z ( (f ( g).
Segue allora che x (F z. Infatti f ( g ( F e' tale che x ( (f ( g) = z ( (f ( g).

Lemma 11.
(F è una congruenza in B cioè: x (F x’ e y (F y’ implicano
x ( y (F x’ ( y’, x ( y (F x’ ( y’ e x* (F (x’)*
Dimostrazione
Assumiamo che x (F x’ e che y (F y’ , allora esisteranno due elementi f,g(F tali che x ( f = x’ ( f e y ( g = y’ ( g. Allora si ha:
1. (x ( y) ( (f ( g) = (x’ ( y’) ( (f ( g) e
2. (x ( y) ( (f ( g) = (x ( f (g) ( (y ( f ( g) = (x’ ( f ( g) ( (y’ ( g (f) = (x’ ( y’) ( (f ( g).
Poichè x ( y ( F , allora x ( y (F x’ ( y’ e x ( y (F x’ ( y’. Inoltre si ha
f = f ( (x ( x*) = (f ( x) ( (f ( x*). Cosi, x’* ( f = x’* ( ((f ( x’) ( (f ( x*)) = (x’* ( f ( x’) ( (x’*( f ( x*) = (ricordando che (x’* ( f ( x’) = 0) =
(x’* ( x*) ( f.
Analogamente si prova che x* ( f = (x’* ( x*) ( f. Così x* ( f = (x’)* ( f cioè
x* (F x’*..

Esercizio
Sia B una algebra di Boole e F un suo filtro. Poniamo:

x y= (x ( y* ) ((x*( y )

Mostrare che:
(a) x(F y y xxy ( F
(b) x(y=1y x=y.

Soluzione
Proviamo la (a). Invero vale la seguente catena di equivalenze:

x(F y y x(f=y(f per qualche f(F
(x(f)((y(f)* = 0
(x(f)((y*(f*)* = 0
(x(f( y*)( (x(f( f*) = 0
(x(f( y*)* =1
(x*(f *(y) (F
(x*(f*(y)(f (F
(x*(f)(( f*(f)((y(f) (F
(x*(y) (F.

Analogamente si ottiene che x(F y y (x( y*) (F. Cosi (x*(y)((x*(y) (F e quindi la (a).
La (b) si prova osservando che vale la seguente catena di equivalenze:

xxy=1y (x*(y)((x*(y)=1
(x*(y)=1 e (x*(y)=1
xxy e yyx
x=y.

Indichiamo con |x| la classe di equivalenza di x sotto (F. Dal lemma precedente si ha, posto B/F = { |x| tale che x ( B}, che si possono definire le seguenti operazioni su B/F :|x| ( |y| = |x ( y| ; |x| ( |y| = |x ( y| ; |x|* = |x*|.
Si è cosi definita l’algebra Booleana quoziente B/F di B modulo F.
L’applicazione h: x ( B ( |x| ( B/F è l’omomorfismo canonico di B su B/F.
Abbiamo visto che ad un filtro F è associato un omomorfismo. Mostriamo l’inverso.

Lemma 12.
Siano B1 e B2 due algebre di Boole e sia (: B1( B2 un omomorfismo. Allora l'insieme F = {x ( B1| ((x) = 1}è un filtro di B1 e ((B1) ( (B1/F).
Dimostrazione
Proviamo che F e' un filtro. Invero ((1) = 1 implica 1 ( F . Siano x, y due elementi di F, allora ((x ( y) = ((x) ( ((y) = 1. Così x ( y ( F. Infine, se x(F e x ( y allora si ha ((x) ( ((y). Cosi' 1 ( ((y) = 1, da cui otteniamo che y(F. Allora F è filtro. Dobbiamo ora provare che ((B1) ( (B1/F). Osserviamo che per ogni x, y ( B1 vale la seguente catena di equivalenze:

|x| = |y| | x (F y (x x y) ( F ((x ( y) = 1 ((x) ( ((y) = 1(
((x) = ((y).

Allora l’applicazione ( : B1/F / ((B1) definita ((|x|) = ((x) è ben definita ed è biunivoca. Si verifica facilmente che ( è un omomorfismo suriettivo. Così ( è un isomorfismo di B1/F su ((B1).)

Il filtro F è detto il co-nucleo dell’omomorfismo (.

Lemma 13.
Siano B1 e B2 due algebre Booleane e f : B1( B2 un omomorfismo. Allora le seguenti sono equivalenti:
i) f è biunivoco;
ii) il co-nucleo di f è {1}.
Dimostrazione
Dimostriamo che ii) implica i). Assumiamo percio' che il co-nucleo di f sia {1} e assumiamo inoltre che f(x) = f(y). Allora si ha: f(x ( y*) = f(x) ( f(y*) =
f(x) ( (f(x))* = 1. Analogamente f(x* ( y) = 1.
Allora, f(x ( y*) ( f(x* ( y) = 1, cioe' f(x ( y) = 1. Da cio' segue che
x x y = 1 e che x = y.
Proviamo ora che i) implica ii). Assumiamo che f sia biunivoco (in effetti che f sia mappa iniettiva) allora è ovvio che il co-nucleo di f e' {1}. (

Definizione 9
Sia F un filtro. F è un filtro primo se x ( y ( F implica che x ( F oppure y ( F.

Teorema 2.
Sia B una algebra di Boole e F un filtro di B. Allora le seguenti affermazioni sono equivalenti:
(a) B/F ( 0,10;
(b) F è ultrafiltro;
(c) F è primo
(d) ( x ( B x ( F oppure x* ( F ma non entrambi.

Dimostrazione
L'equivalenza tra (b) e (d) e' già stata dimostrata. Dimostriamo che (d) implica (a). Invero, sia |x| l’immagine di x sotto l’omomorfismo canonico di B su B/F e supponiamo che |x| ( 1, cosi' otteniamo che x ( F. Per (d), segue che x* ( F. Allora |x|* = |x*| = 1. Da cio' segue che |x| = |x|** = 0. Quindi B/F = {0, 1}.
Per provare che (a) implica (d), assumiamo che x ( F. Allora |x| ( 1 e per (a)
|x| = 0. Quindi |x*| = 1 e x* ( F.
Proviamo ora che (b) implica (c). Invero, sia x ( y ( F, x ( F e G il filtro generato da F ( {x}. Per (b) F è massimale. Allora G non è proprio e quindi esiste z ( F tale che z ( x = 0. Ma z, x ( y ( F implicano che z ( (x ( y) ( F. Cosi otteniamo che 0 ( (z ( y) ( F. Ma z ( y ( y, e poiché F è filtro segue che y ( F.
Proviamo ora che (c) implica (d). Invero, per ogni x ( B si ha che x ( x* = 1 ( F, così per (c), x ( F oppure x* ( F. (

Sia B un’algebra di Boole e sia {An, n < (} una famiglia numerabile di sottoinsiemi di B, ognuno dei quali sia dotato di estremo inferiore. Poniamo per ogni n < ( an = inf (An).

Definizione 10
Sia B una algebra di Boole e F un ultrafiltro in B. Con le notazioni di sopra, si dice che F preserva gli “inf” se e solo se h(an) = inf {h(a) : a ( An} per ogni
n < (, ove h è un omomorfismo di B su B/F.

Teorema 3.
Sia B una algebra di Boole e x un elemento non nullo di B. Allora esiste un ultrafiltro F di B tale che:
1. x ( F;
2. F preserva gli “inf”.F