Fondamenti di informatica - Laurea triennale Informatica/Algebra Booleana

L'algebra booleana è una struttura matematica astratta che generalizza le proprietà viste in precedenza per le operazioni logiche.

Un’algebra booleana è composta da:

• un insieme B;
• due elementi distinti, chiamati 0 e 1;
• due operazioni binarie, indicate con + e ⋅;
• un’operazione unaria di complemento, indicata con ′.

Si scrive:

[B,+,⋅,′,0,1]

Gli elementi 0 e 1 non sono necessariamente i numeri 0 e 1: sono solo simboli che rappresentano due elementi speciali dell’insieme.

Allo stesso modo, + e ⋅ non sono necessariamente la somma e il prodotto ordinari, ma operazioni astratte che soddisfano certe leggi.

Le leggi fondamentali

Un’algebra booleana deve soddisfare alcune proprietà fondamentali.

Leggi associative

(a+b)+c=a+(b+c)

(a⋅b)⋅c=a⋅(b⋅c)

Servono a dire che, quando si combinano tre elementi, il modo in cui si mettono le parentesi non cambia il risultato.

Leggi commutative

a+b=b+a

a⋅b=b⋅a

L’ordine degli elementi non cambia il risultato.

Leggi distributive

a⋅(b+c)=(a⋅b)+(a⋅c)

a+(b⋅c)=(a+b)⋅(a+c)

Queste leggi mostrano come le due operazioni interagiscono tra loro.

Leggi di identità

a+0=a

a⋅1=a

L’elemento 0 è l’identità rispetto a +, mentre 1 è l’identità rispetto a ⋅.

Leggi del complemento

Per ogni elemento a, esiste un complemento a′ tale che:

a+a′=1

a⋅a′=0

Il complemento di un elemento si comporta come la sua “negazione”.

Esempi di algebre booleane

Un esempio importante è l’insieme:

{0,1}

con le operazioni logiche corrispondenti a OR, AND e NOT.

Un altro esempio fondamentale è l’insieme delle parti di un insieme universale U, cioè:

P(U)

In questo caso:

• + corrisponde all’unione ∪;
• ⋅ corrisponde all’intersezione ∩;
• il complemento A′ corrisponde al complemento di un insieme rispetto a U;
• 0 corrisponde all’insieme vuoto ∅;
• 1 corrisponde all’insieme universale U.

Quindi anche la teoria degli insiemi può essere vista come un’algebra booleana.

Unicità del complemento

Il complemento di un elemento è unico.

Questo significa che, se due elementi b e c soddisfano entrambi le proprietà del complemento di a, allora devono essere uguali:

b=c

Questa proprietà è importante perché permette di parlare del complemento di a come di un elemento ben determinato, indicato con a′.

Proprietà derivate delle algebre booleane

Dalle leggi fondamentali si possono ricavare molte altre proprietà.

Leggi idempotenti

a+a=a

a⋅a=a

Applicare la stessa operazione a un elemento con sé stesso non cambia l’elemento.

Leggi dei limiti

a+1=1

a⋅0=0

L’elemento 1 domina rispetto a +, mentre 0 domina rispetto a ⋅.

Leggi di assorbimento

a+(a⋅b)=a

a⋅(a+b)=a

Queste leggi dicono che una parte ridondante dell’espressione può essere eliminata.

Legge dell’involuzione

(a′)′=a

Il complemento del complemento di un elemento è l’elemento stesso.

Leggi di De Morgan

(a+b)′=a′⋅b′ (a⋅b)′=a′+b′

Queste sono le versioni astratte delle leggi di De Morgan già note nella logica e nella teoria degli insiemi.

Nel caso degli insiemi diventano:

(A∪B)′=A′∩B′ (A∩B)′=A′∪B′

Il principio di dualità

Una caratteristica importante delle algebre booleane è che molte proprietà appaiono in coppie.

Per esempio:

a+0=a

ha come proprietà duale:

a⋅1=a

Il duale di una proposizione si ottiene scambiando:

• + con ⋅;
• ⋅ con +;
• 0 con 1;
• 1 con 0.

Quindi

Il duale di un teorema sulle algebre booleane è anch’esso un teorema.

Questo significa che, una volta dimostrata una proprietà, spesso si ottiene automaticamente anche la sua versione duale.