Algebra di Boole

Enciclopedia della Scienza e della Tecnica (2008)

algebra di Boole

Silvio Bozzi

Introdotte nel 1848 da George Boole come controparte algebrica della logica dei termini e di quella ipotetica, le algebre di Boole trovano una prima formulazione assiomatica per opera di Alfred N. Whitehead ed Edward V. Huntington nei primi anni del Novecento e, nella doppia veste di algebra delle proposizioni e di algebra delle classi, costituiranno – tra la fine dell’Ottocento e l’inizio del Novecento – l’oggetto dell’algebra della logica. Il loro ingresso nel mondo della matematica propriamente detta avverrà negli anni Trenta quando Marshall Stone farà emergere la loro doppia natura di anelli che, secondo l’originaria prospettiva di Boole, godono della legge di idempotenza x2=x− i cosiddetti anelli booleani – e di reticoli limitati, distributivi e complemementati, come già intuito da Charles S. Peirce ed Ernst Schröder. In questa seconda prospettiva, lo studio delle algebre di Boole diviene un capitolo importante della teoria generale dei reticoli introdotta negli anni Trenta del secolo scorso da Garrett Birkhoff. Un reticolo è un insieme ordinato 〈I, ≤ > in cui ogni coppia di elementi (e quindi ogni insieme finito) ha un infimo e un supremo. Nel caso questo avvenga per ogni sottoinsieme il reticolo sarà completo. Esempio fondamentale è l’insieme P(A) dei sottoinsiemi di un insieme, ordinato dall’inclusione. È facile verificare che se indichiamo con ∧ l’operazione di prendere l’infimo di due elementi e con ∨ quella di prendere il supremo avremo che:

xx = x xx = x

xy = y x xy = yx

(xy) ∧ z = (xy) ∨ z =

= x ∧ (y x) = x ∨ (y x)

x ∧ (xy) = x x ∨ (xy) = x.

All’inverso se un’algebra 〈A,∧,∨〉 soddisfa gli assiomi di sopra e definiamo xy se xy=x, avremo che 〈A,≤〉 risulta un reticolo di cui ∧ e ∨ sono rispettivamente l’infimo e il supremo. Un reticolo è limitato se possiede elemento minimo 0 ed elemento massimo 1, condizione che si può esprimere equazionalmente dicendo che:

0 ∨ x = x 1 ∧ x = x.

Dato un elemento x di un reticolo limitato complemento di x è ogni y per cui

xy = 0 xy = 1.

In generale non è detto che un elemento abbia un complemento o che ne abbia uno solo. L’unicità è garantita se il reticolo è distributivo, cioè se:

x ∧ (y z) = (x y) ∨ (z y)

x ∨ (y z) = (x y) ∧ (x z).

Se un reticolo è tale che ogni elemento ha uno e un solo complemento diremo che è complementato e potremo definire un’operazione ′: AA per cui

xx ′ = 1 xx ′ = 0.

Le algebre di Boole sono reticoli limitati, distributivi e complementati. Esempi sono l’algebra B(I)=〈P(I),∩,∪,‒〉 dei sottoinsiemi di un insieme dato mentre non sono algebre di Boole né il reticolo dei chiusi né quello degli aperti di uno spazio topologico. Algebre di Boole sono invece i reticoli dei clopen (gli insiemi aperti e chiusi) di uno spazio topologico mentre di Boole e σ-completa (chiusa cioè rispetto a infimi e supremi di famiglie numerabili) è l’algebra dei boreliani di uno spazio. Il risultato che ha dato l’inizio allo studio sistematico delle algebre di Boole è il teorema dimostrato da Marshall Stone nel 1936 per cui ogni algebra di Boole è isomorfa ;all’algebra dei clopen di uno spazio compatto totalmente sconnesso. Nel 1947 Lynn Loomis ha provato un risultato analogo per le algebre di Boole σ-complete che intervengono nella teoria della misura. In tutti questi teoremi di rappresentazione, i punti dello spazio sono ideali massimali (o i loro duali, gli ultrafiltri) dell’algebra. Lo studio e la classificazione di filtri e ultrafiltri nelle algebre di Boole è divenuto così di importanza centrale e ha avuto moltissime applicazioni. Nella logica matematica, per es., dove l’insieme delle proposizioni di un linguaggio enunciativo, una volta che si identifichino gli enunciati equivalenti rispetto alla logica classica, costituisce un’algebra di Boole (l’algebra di Lindenbaum del linguaggio) e i filtri corrispondono alle teorie. Questo non esaurisce però l’orizzonte della teoria delle algebre di Boole che continua a svilupparsi in molteplici direzioni che vanno dalla teoria della misura, all’algebra universale, alla topologia generale.

Computer. Hardware; Logica matematica

CATEGORIE
TAG

Teoria della misura

Logica matematica

Garrett birkhoff

Insieme ordinato

Spazio compatto