Matematica III - l'algebra booleana

Algebra di Boole

Strutture algebriche

In informatica viene fatto uso dell'algebra astratta per rappresentare, semplificare relazioni e condizioni all'interno di programmi, studiarne la struttura e formalizzare i processi di logica. Si dice che un insieme I è dotato o che costituisce un'algebra astratta se in esso sono definite ovunque due operazioni binarie interne, che facciano corrispondere ad una qualsiasi coppia di elementi di I ancora un elemento di I.

Richiami operazioni su insiemi

Un'operazione si dice binaria se opera su due elementi di un qualsiasi insieme. Ad esempio, l'addizione è un'operazione binaria, perché ha bisogno di due elementi, gli addendi, per essere eseguita. Un'operazione, poi, si definisce interna se presi due elementi appartenenti ad un generico insieme A e applicata su di essi l'operazione, il risultato è ancora un elemento di A. Ad esempio, prendiamo in considerazione l'insieme dei numeri dispari. Se prendiamo due elementi qualsiasi di quest'insieme e scegliamo di applicargli l'addizione, possiamo facilmente constatare che il risultato è un numero sempre pari. Quindi l'addizione non è un'operazione interna rispetto all'insieme dei numeri dispari. Viceversa, se prendiamo due elementi qualsiasi dall'insieme dei numeri pari e applichiamo su di essi l'addizione, ci risulterà sempre un numero pari, numero che, dunque, appartiene all'insieme di partenza. Allora l'addizione è un'operazione interna all'insieme dei numeri pari.

L'insieme I è detto anche insieme di sostegno dell'algebra. Viene usualmente indicato con il simbolo + l'operazione di OR booleana, invece denotata con il simbolo · l'operazione di AND booleana. Formalmente un'algebra è definita mediante la tripla < I, +, · >.

Operazioni sugli insiemi

Prendiamo in considerazione due insiemi A e B, supponiamo che entrambi siano inclusi in un altro insieme, che definiamo come insieme universo, sugli insiemi sono definite le seguenti operazioni:

• A OR B – (A+B) costituisce l'insieme degli elementi appartenenti ad almeno uno dei due insiemi;
• A AND B – (A·B) costituisce l'insieme degli elementi appartenenti ad ambedue gli insiemi;
• NOT A – (~A) costituisce l'insieme degli elementi che appartengono a T, ma non ad A.

Di seguito sono riportate in modo schematico tutte le proprietà delle due operazioni booleane.

Proprietà delle operazioni booleane