Lalgebra di Boole (anche detta algebra booleana, logica booleana o reticolo booleano), in matematica e logica matematica, è il ramo dell'algebra in cui le variabili possono assumere solamente i valori vero e falso (valori di verità), generalmente denotati rispettivamente come 1 e 0.
Storia Ideata nel 1847 all'University College Cork da George Boole nel suo libro The Mathematical Analysis of Logic per scrivere in forma algebrica la logica proposizionale e da lui ulteriormente sviluppata nel 1854 in An Investigation of the Laws of Thought, l'algebra di Boole è stata fondamentale nel campo dell'elettronica digitale, dove nella progettazione dei circuiti elettronici rivestono grande importanza i teoremi deducibili dagli assiomi che fondano l'algebra, come il teorema di Shannon del 1940 che mostra come scomporre una funzione booleana complessa in funzioni più semplici, o per ottenere un'espressione canonica da una tabella della verità. L'algebra di Boole riveste un ruolo di fondamentale importanza nell'informatica, tanto che ogni linguaggio di programmazione moderno definisce al suo interno gli operatori logici; è usata inoltre anche nella teoria degli insiemi e nella probabilità.
Descrizione Le operazioni fondamentali non sono addizione e sottrazione ma gli operatori logici: la congiunzione o prodotto logico, indicata con ∧ oppure AND, la disgiunzione o somma logica, indicata con ∨ oppure OR, e la negazione o complementazione, indicata con ¬ oppure NOT. Con tale formalismo si possono descrivere le relazioni logiche in modo simile a quanto fa l'algebra ordinaria con le relazioni numeriche: la combinazione di AND, OR e NOT permette di sviluppare qualsiasi funzione booleana e i tre operatori logici formano pertanto un insieme funzionalmente completo.
Definizione formale Matematicamente, si dice algebra di Boole un qualunque reticolo dotato di proprietà, quali la distributività, l'esistenza di minimo e massimo e l'esistenza del complemento: l'algebra booleana risulta criptomorfa, cioè associata biunivocamente e in modo da risultare logicamente equivalente a un insieme parzialmente ordinato reticolato. D'altra parte, ogni algebra booleana risulta criptomorfa a un particolare tipo di anello, chiamato anello booleano. La struttura può essere specificata attraverso gruppi e anelli o attraverso i reticoli in modo del tutto equivalente.
Più precisamente, si parla di algebra di Boole in riferimento a un insieme K sul quale sono definite le operazioni di somma logica (+, OR) e prodotto logico (*, AND), cioè una terna , che costituisce un reticolo in cui sono inoltre soddisfatte la proprietà distributiva, l'esistenza del minimo e del massimo e l'esistenza del complemento.
Nel dettaglio, si ha un'algebra di Boole quando su sono soddisfatte le seguenti proprietà:
Commutativa
Associativa
Assorbimento
Distributiva
Idempotenza
Esistenza di minimo e massimo
Esistenza del complemento
Il modo in cui sono elencate le proprietà vuole mettere in evidenza la simmetria che c'è tra i due operatori, che è poi all'origine della legge di dualità e altre proprietà molto importanti. Nell'elencare gli assiomi, il complemento è stato indicato con un trattino sulla variabile (che è tipograficamente difficile da realizzare, anche se è la notazione migliore); il complemento può anche essere indicato con un "!" (punto esclamativo) antecedente alla variabile booleana (notazione tipica della programmazione in C e C++), con uno slash prima della variabile o addirittura con un segno meno antecedente a essa, quando non è una notazione equivoca. Il complemento corrisponde all'operazione logica NOT.
Un'ultima osservazione riguarda il fatto che le prime 4 proprietà riguardano i reticoli in generale, mentre le restanti sono proprie dell'algebra di Boole, che sarà quindi indicata con la sestupla . Data la formulazione generale, da questo momento in poi ci si riferisce all'algebra primordiale, che considera , cioè l'insieme su cui si basa l'algebra di Boole è composto solamente dal minimo e dal massimo.
Si elencano ora la legge di dualità e alcune proprietà derivanti dagli assiomi ora visti con le relative dimostrazioni; oltre a queste conseguenze, ci sono poi due importanti teoremi dell'algebra booleana che sono i teoremi di De Morgan e il teorema di Shannon. I teoremi che si dimostrano ora sono validi per qualsiasi "porzione di realtà" che soddisfa gli assiomi di quest'algebra astratta e, in particolare, saranno applicabili nell'algebra degli insiemi, nell'algebra della logica delle proposizioni e nell'algebra dei circuiti.
Legge di dualità Da qualsiasi identità booleana se ne può trarre un'altra per dualità, sostituendo cioè a ogni operatore e agli elementi 0 e 1 il rispettivo duale: il duale di + è *, il duale di 0 è 1 (la dimostrazione di questo sta al prossimo paragrafo), il duale di a è in generale !a (a negato, NOT a).
Grazie a questa legge, si può vedere come i 14 postulati dati per definire l'algebra booleana non sono tutti indipendenti tra loro: in particolare, si vede che PX e PX' (per X=1,...,7) sono uno il duale dell'altro.
Complementi di 0 e 1 0 e 1 sono uno il complementare dell'altro: per dimostrarlo basta verificare la definizione di complemento, cioè che
Si vede immediatamente che
applicando rispettivamente la proprietà del minimo e quella del massimo e il teorema ora enunciato risulta così dimostrato.
Si nota che, per come è strutturata quest'algebra, questa dimostrazione ha permesso di dimostrare a partire dagli assiomi che l'elemento neutro esiste ed è unico (l'esistenza non è quindi postulata e l'unicità è insita nell'esistenza essendo solo 2 i valori con cui sta lavorando, cosa non vera per altri tipi di algebra e altre strutture algebriche).
Convoluzione Negando due volte lo stesso elemento, si ottiene l'elemento stesso (logica aristotelica: una doppia negazione corrisponde a un'affermazione).
Per dimostrarlo, basta considerare l'assioma di esistenza del complemento considerato su due elementi a e b=!a:
Essendo valida la proprietà commutativa e siccome il complemento esiste unico, se ne deduce facilmente che , che è quello che si voleva dimostrare.
Elementi neutri 0 è l'elemento neutro della somma (disgiunzione logica, ∨, OR) e 1 è l'elemento neutro del prodotto (congiunzione logica, ∧, AND).
Per la dimostrazione, basta sfruttare la proprietà dell'assorbimento grazie alla quale si deduce che:
Ora, sfruttando la proprietà del massimo e minimo per la quale a*0=0 e a+1=1, si deduce facilmente che:
che è quello che si doveva dimostrare.
Assorbimento del complemento (secondo teorema dell'assorbimento) L'assorbimento del complemento dice che
Per dimostrarlo, basta applicare la proprietà distributiva secondo la quale:
dopodiché, notando che a+!a=1 e che 1 è l'elemento neutro del prodotto logico risulta dimostrato il teorema.
Per la legge di dualità si capisce anche che esiste un teorema duale a questo che sarà:
Questo teorema può essere preso per vero accettando la validità della legge di dualità, oppure può essere dimostrato in modo del tutto analogo al precedente. Si nota che, nello scrivere l'espressione duale, si è dovuta rispettare la precedenza di applicazione delle operazioni e perciò le parentesi intorno ad a+!b della seconda espressione sono necessarie.
Teorema dell'elemento unico Se e , allora y è unico (o anche x è unico perché si vede che, essendo valida la proprietà commutativa, il ruolo di x e y nelle espressioni è lo stesso).
Per la dimostrazione, si suppone per assurdo che esistano due valori distinti y e z che soddisfano le due espressioni, e cioè
Essendo anche che
si è ottenuto che
Nell'ultimo passaggio, si è sfruttato il principio di equivalenza delle eguaglianze e non si è semplificato la x, cosa che non è stata dimostrata e non può essere dimostrata in quest'algebra. Allora, quello che si ha ora è che
Moltiplicando membro a membro e utilizzando la proprietà distributiva, si ha:
cioè y=z e perciò l'elemento che soddisfa le due relazioni scritte sopra è unico.
Principio di eliminazione Come si è accennato prima, nell'algebra di Boole non valgono i principi di eliminazione, cioè non vale che:
Vale che y=z solamente se queste due espressioni ora scritte valgono contemporaneamente.
L'unica cosa che si può dire invece nel caso in cui valga solo la prima espressione è che:
Funzioni booleane
L'algebra di Boole è la trattazione dell'algebra universale a due stati e dei modelli di tale teoria, detti algebre booleane. L'algebra universale si occupa di studiare la famiglia di operazioni su un insieme, detto insieme fondamentale della famiglia algebrica e, nel caso della struttura algebrica booleana, questo contiene i soli valori 0 e 1. In pratica le algebre booleane si occupano della trattazione delle funzioni booleane di cui ora si accennano le nozioni principali: lo studio di queste funzioni è fondamentale oggi per lo studio di circuiti e reti logiche, perciò se ne possono vedere subito gli scopi pratici, ma l'importanza di queste strutture algebriche non si limita solo a questo perché è anche fondamentale nello studio delle proposizioni e dell'insiemistica, che sono argomenti un po' più astratti ma altrettanto validi e importanti.
Il numero degli argomenti che richiede un'operazione definita sull'insieme fondamentale è detto arietà (un'addizione ad esempio è un'operazione di arietà 2, anche detta operazione binaria): un'operazione su {0,1} di arietà n può essere applicata a ognuno dei 2n possibili valori dei suoi n argomenti (cioè basta calcolare le disposizioni di 2 elementi su n posti), ad esempio se si ha un'operazione di arietà 3, dato che K={0,1}, gli argomenti possibili sono 000,001,010,011,100,101,110,111 che sono 8.
Per ogni scelta di argomenti l'operazione può produrre i soli risultati 0 e 1 e per questo ci sono 22n operazioni di n argomenti: questo numero corrisponde quindi al numero totale di funzioni possibili di n variabili nell'algebra booleana.
L'algebra a due stati possiede 2 operazioni con nessun argomento (220) che restituiscono i valori 0 e 1 senza considerare nessun argomento, e 4 operazioni con un solo argomento(221): le operazioni possibili sono due (21), l'identità e la negazione e perciò in totale le operazioni sono 4 in quanto si ha ha {0,1} → {0,1} (id.), {0,1} → {1,0} (neg.), {0,1} → 0 (falso), {0,1} → 1 (vero). Vi sono poi 16 operazioni binarie, 256 operazioni ternarie, 65.536 operazioni quaternarie e così via.
Siccome l'algebra di cui sta parlando è fondata su un insieme finito, una funzione può essere rappresentata oltre che in forma algebrica (cioè composizione di AND, OR e NOT), in forma tabellare, cioè con una tabella in cui a ogni composizione delle variabili "di input" (usando una terminologia più informatica) si fa corrispondere l'uscita (o anche le uscite): tutte le funzioni, anche di altre algebre, possono in teoria essere rappresentate tramite tabelle ma se l'insieme su cui è fondata l'algebra è infinito (ad esempio l'insieme dei numeri reali) non è un modo comodo per studiare la funzione; per l'algebra booleana usare le tabelle è un modo utile per studiare le funzioni e ad esempio permette facilmente la costruzione di circuiti e reti logiche nelle applicazioni elettroniche. Un esempio di tabelle si ha considerando operazioni binarie che si è già visto essere 16:
ABf0f1f2f3f4f5f6f7f8f9f10f11f12f13f14f15000000000011111111010000111100001111100011001100110011110101010101010101