Algebra di Boole

In matematica ed informatica, le algebre booleane, o reticoli booleani, sono strutture algebriche che rivestono una notevole importanza per varie ragioni.

"Catturano l'essenza" degli operatori logici AND, OR e NOT
Consentono di trattare in termini esclusivamente algebrici le operazioni insiemistiche dell'intersezione, dell'unione e della complementazione.
Permettono di trattare in termini algebrici questioni riguardanti singoli bits (0 e 1), sequenze binarie, matrici binarie (e di conseguenza, attraverso le loro matrici di incidenza i digrafi) e altre funzioni binarie (si tenga presente anche la nozione di funzione indicatrice).
Ogni algebra booleana, in quanto reticolo dotato di particolari proprietà, risulta criptomorfa (cioè associata biunivocamente e in modo da risultare logicamente equivalente) ad un insieme parzialmente ordinato reticolato. Inoltre ogni algebra booleana risulta criptomorfa ad un particolare tipo di anello, chiamato anello booleano.

Questi collegamenti per criptomorfismo fra reticoli booleani, posets reticolati e anelli booleani è opportuno siano chiariti in modo completo: solo in questo modo si può avere un controllo completo di tutte le applicazioni delle algebre booleane (e delle strutture relazionali e di anello associate).

Sono state definite da George Boole, un matematico inglese dell'University College di Cork, che per primo, verso la metà del XIX secolo le ha definite come componenti di un sistema logico. In particolare, l'algebra booleana era un tentativo di usare le tecniche algebriche per elaborare le espressioni nel calcolo di proposizionale. Oggi, le algebre booleane trovano molte applicazioni anche nella progettazione dei circuiti elettronici, proseguendo . In primo luogo sono state applicate alla commutazione da Claude Shannon negli anni intorno al 1940.

Gli operatori dell'algebra booleana possono essere rappresentati in vari modi. Spesso sono scritti semplicemente come AND, OR e NOT. Nella descrizione dei circuiti, possono anche essere usati NAND (NOT AND), NOR (NOT OR) e XOR (OR esclusivo). In matematica spesso si usa + per OR e $\cdot$ per AND (poiché per alcuni versi queste operazioni sono analoghe alla somma ed al prodotto in altre strutture algebriche), mentre si rappresenta il NOT con una barra segnata sopra l'espressione che viene negata.

Qui useremo la notazione comune $\wedge$ (o ^ per i browsers che non supportano il precedente carattere) per AND, $\vee$ (o v) per OR ed $\neg$ (o ~) per NOT.

Indice

1 Definizione algebrica

2 Simbologia

2.1 Operatori

2.1.1 NOT
2.1.2 OR
2.1.3 AND
2.1.4 XOR
2.1.5 NOR
2.1.6 NAND
2.1.7 XNOR

2.2 Simboli

2.2.1 Vero
2.2.2 Falso

3 Definizione e prime considerazioni

4 Esempi

5 Omomorfismi ed isomorfismi

6 Anelli, ideali e filtri booleani

7 Rappresentazione delle algebre booleane

8 Vedi anche

Definizione algebrica

Se B è un insieme formato da almeno 2 elementi, diciamo algebra booleana avente S come supporto la struttura algebrica costituita da S, da due operazioni binarie su B, OR e AND, da un'operazione unaria NOT su B e da un elemento particolare di B che indichiamo 0 i quali godono delle seguenti proprietà.

$\forall a,b \in B : a ~AND~ b = b ~AND~ a$ . AND è simmetrica

$\forall a,b \in B : a ~OR~ b = b ~OR~ a$ . OR è simmetrica

$\forall a \in B : NOT(NOT(a)) = a$ . NOT è un'involuzione

$\forall a,b \in B : NOT(a ~OR~ b) = NOT(a) ~AND~ NOT(b)$

$\forall a \in B : a ~AND~ \mathbf{0} = \mathbf{0} ;~ a ~OR~ \mathbf{0} = a$

Per ogni algebra booleana si definisce l'elemento 1 come il complementare dello 0: 1 := NOT(0). Per esso si deducono le proprietà

$\forall a \in B : a ~OR~ \mathbf{1} = \mathbf{1} ; a ~AND~ \mathbf{1} = a$

e in particolare

0 AND 1 = 0 ; 0 OR 1 = 1.

Si definisce inoltre l'operatore binario OR esclusivo denotato XOR:

$\forall a,b \in B : a ~XOR~ b := (a ~OR~ b) ~AND~ ( NOT(a ~AND~ b))$

Si può osservare la simmetria della definizione e quindi quella di XOR: : $\forall a,b \in B : a ~XOR~ b = b ~XOR~ a$ .

La collezione di tutti i sottoinsiemi di un dato insieme (che può essere opportuno chiamare insieme ambiente) munita delle operazioni di unione, intersezione e complementazione di insiemi costituisce un'algebra booleana. In questa algebra all'operatore XOR corrisponde la differenza

Simbologia

Gli operatori dell'algebra booleana possono essere rappresentati in vari modi, oltre a quello adottato in precedenza consistente nel servirsi dei loro nomi AND, OR, NOT. Le diverse simbologie sono scelte in base al campo in cui si lavora.

I matematici usano spesso il simbolo + per l'OR, e × per l'AND, in quanto per alcuni versi questi operatori lavorano in modo analogo alla somma e alla moltiplicazione. La negazione NOT viene rappresentata spesso da una linea disegnata sopra l'argomento della negazione, cioè dell'espressione che deve essere negata.

Nella progettazione di circuiti elettronici, vengono utilizzati anche gli operatori brevi NAND (AND negato), NOR (OR negato) e XNOR (XOR negato); questi operatori, come XOR, sono delle combinazioni dei tre operatori base e quindi non costituiscono un arricchimento della specie di strutture, vengono usati solo per rendere la notazione più semplice.

Operatori:

NOT: x, ~, &not, !;
AND: *, AND, ^, BUT (usato nella logica brasiliana insieme al NOT);
OR: +, OR, v;
XOR: +, ⊕, ∨, ^, EOR, orr;
NAND
NOR
XNOR

Valori:

vero (true), 1, ON, SI;
falso (false), 0, OFF, NO;

Operatori

NOT

L'operatore NOT Restituisce il valore inverso di quello in entrata. Una concatenazione di NOT è semplificabile con un solo NOT in caso di dispari ripetizioni o con nessuno nel caso di pari.

Spesso, per semplificare espressioni complesse, si usano operatori brevi che uniscono l'operazione di NOT ad altre, questi operatori sono NOR (OR + NOT), NAND (AND + NOT), XNOR (XOR + NOT). La negazione, in questi casi, viene applicata dopo il risultato dell'operatore principale (OR, AND, XOR).

OR

L'operatore OR restituisce vero se almeno una delle proposizioni in entrata restituisce vero:

1 OR 0 = 1
1 OR 1 = 1
0 OR 0 = 0
1 OR 1 OR 0 = 1
0 OR 0 OR 1 = 1
0 OR 0 OR 0 = 0

AND

L' operazione logica AND (letteralmente e in inglese) restituisce vero se e solo se entrambe le proposizioni hanno valore vero, altrimenti restituisce falso.

vero AND vero = vero
vero AND falso = falso
falso AND vero = falso
falso AND falso = falso

AND può essere generalizzata ad un numero arbitrario di proposizioni in ingresso: se sono tutte vere restituisce vero, altrimenti falso, per esempio:

vero AND vero AND vero AND vero AND vero AND vero = vero
vero AND falso AND vero AND falso AND vero AND falso = falso
falso AND falso AND falso AND falso AND falso AND falso = falso

È possibile realizzare un'operazione logica AND con un numero di proposizioni arbitrarie concatenando varie AND a due ingressi, per esempio:

p1 AND (p2 AND (p3 AND p4))

Nei circuiti digitali, la porta logica AND è un meccanismo comune per avere un segnale di vero se un certo numero di altri segnali sono tutti veri.

XOR

L'operatore XOR (detto anche OR esclusivo) restituisce 1 (vero) se solo uno degli elementi è 1 e tutti gli altri 0.

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

1 XOR 1 XOR 1 XOR 1 = 0
1 XOR 0 XOR 1 XOR 0 = 0
0 XOR 0 XOR 0 XOR 0 = 0
1 XOR 0 XOR 0 XOR 0 = 1
0 XOR 1 XOR 0 XOR 0 = 1

Nella teoria degli insiemi corrisponde alla differenza.

NOR

L'operatore NOR restituisce 1 (vero) se entrambi gli elementi sono 0 e tutti gli altri 0 (falso).

0 NOR 0 = 1
0 NOR 1 = 0
1 NOR 0 = 0
1 NOR 1 = 0

1 NOR 1 NOR 1 NOR 1 = 0
1 NOR 0 NOR 1 NOR 0 = 1
0 NOR 0 NOR 0 NOR 0 = 1
1 NOR 0 NOR 0 NOR 0 = 0
0 NOR 1 NOR 0 NOR 0 = 0

NAND

L'operatore NAND restituisce 0 (falso) se entrambi gli elementi sono 1 e tutti gli altri 1 (vero).

0 NAND 0 = 1
0 NAND 1 = 1
1 NAND 0 = 1
1 NAND 1 = 0

1 NAND 1 NAND 1 NAND 1 = 1
1 NAND 0 NAND 1 NAND 0 = 1
0 NAND 0 NAND 0 NAND 0 = 1
1 NAND 0 NAND 0 NAND 0 = 1
0 NAND 1 NAND 0 NAND 0 = 1

XNOR

L'operatore XNOR indica un XOR negato (NOT XOR), questo significa che restituisce 1 solo se un solo elemento è uguale a 0 e tutti gli altri elementi sono 1.

0 XNOR 0 = 1
0 XNOR 1 = 0
1 XNOR 0 = 0
1 XNOR 1 = 1

1 XNOR 1 XNOR 1 XNOR 1 = 1
1 XNOR 0 XNOR 1 XNOR 0 = 1
0 XNOR 0 XNOR 0 XNOR 0 = 1
1 XNOR 0 XNOR 0 XNOR 0 = 0
0 XNOR 1 XNOR 0 XNOR 0 = 0

Simboli

Vero

Falso

Definizione e prime considerazioni

Un'algebra booleana è un reticolo (A, $\wedge$ , $\vee$ ) (considerato come struttura algebrica) con le seguenti quattro proprietà supplementari:

limitata inferiormente: Esiste un elemento 0, tale che $a \vee 0 = a$ per ogni a in A.
limitata superiormente: Esiste un elemento 1, tale che $a \wedge 1 = a$ per ogni a in A.
soddisfa la legge distributiva: Per ogni a, b, c in A, (a $\vee$ b) $\wedge$ c = ( a $\wedge$ c ) $\vee$ ( b $\wedge$ c).
esistenza del complementare: Per ogni a in A esiste un elemento $\neg$ a in A tale che $a \vee \neg a = 1$ e $a \wedge \neg a = 0$ .

Direttamente da questi assiomi, si può vedere che il più piccolo elemento 0, il più grande elemento 1 ed il complementare $\neg a$ di ogni elemento a sono determinati univocamente.

Come per ogni reticolo, ad un'algebra booleana (A, $\wedge$ , $\vee$ ) si associa un insieme parzialmente ordinato (A, $\leq$ ), definendo:

$a \leq b \Leftrightarrow a = a \wedge b$ (che è anche equivalente a $b = a \vee b$ ).

Si può anche associare un'algebra booleana a un reticolo distributivo (A, $\leq$ ) (considerato come insieme parzialmente ordinato) dotato di elemento minimo 0 e di elemento massimo 1, in cui ogni elemento x ha un complementare $\neg x$ ) tale che

$x \wedge \neg x = 0$ e $x \vee \neg x = 1$

Qui $\wedge$ e $\vee$ sono usati per denotare l'inf ed il sup di due elementi. Se i complementi esistono, allora sono unici.

La definizione di algebra booleana come struttura dotata di relazione d'ordine e come struttura algebrica, come di consueto, possono essere usate scambievolmente ed entrambe sono di grande utilità per importare risultati e concetti sia dall'algebra universale che dalla teoria degli ordini. Le due definizioni sono equivalenti e possono essere scambiate all'occorrenza. In molti casi pratici lavorare usando congiunzioni, disgiunzioni e complementi può essere il metodo migliore per affrontare un problema e definirlo correttamente.

Ora si possono ottenere numerosi teoremi validi in ogni algebra booleana. Per esempio, per ogni elemento a e b di un'algebra booleana, si trova che

$a \wedge 0 = 0$ e $a \vee 1 = 1$
$\neg 1 = 0$ e $\neg 0 = 1$
$\neg \neg a = a$

e che sono valide entrambe le leggi di deMorgan, cioè

$\neg ( a \vee b ) = ( \neg a ) \wedge ( \neg b)$
$\neg ( a \wedge b ) = ( \neg a ) \vee ( \neg b)$

Si può anche applicare alle algebre booleane la teoria della dualità. Specificatamente l'ordine ottenuto scambiando gli operatori AND and OR è equivalente a quello di partenza. Infatti l'algebra ottenuta scambiando $\wedge$ con $\vee$ , è ancora un'algebra booleana. Così la versione duale della legge distributiva,

$( a \wedge b ) \vee c = ( a \vee c ) \wedge ( b \vee c )$

è ancora verificata. In generale, ogni legge valida per le algebre booleane può essere trasformata in un'altra legge duale valida scambiando 0 con 1, $\wedge$ con $\vee$ e $\leq$ con $\geq$ .

Esempi

L'algebra booleana più importante ha soltanto due elementi, 0 e 1 ed è definita dalle seguenti regole

$\vee$	0	1
0	0	1
1	1	1

$\wedge$	0	1
0	0	0
1	0	1

Questa algebra ha applicazioni nella logica, dove 0 è interpretato come "falso", 1 come vero, $\vee$ è AND, $\wedge$ è OR e $\neg$ è "NOT". Le espressioni che coinvolgono le variabili e le operazioni booleane rappresentano forme dichiarative; due espressioni possono essere equivalenti utilizzando i suddetti assiomi se e soltanto se le forme dichiarative corrispondenti sono logicamente equivalenti. L'algebra booleana binaria, inoltre, è usata per il disegno di circuiti nell'ingegneria elettronica; qui 0 e 1 rappresentano le due condizioni differenti di un bit in un circuito digitale, in genere bassa e alta tensione . I circuiti sono descritti da espressioni che contengono delle variabili e due espressioni sono uguali per tutti i valori delle variabili se e soltanto se i circuiti corrispondenti hanno la stessa funzione di trasferimento. Ogni combinazione dei segnali in ingresso in uscita dal componente può essere rappresentata da un'adeguata espressione booleana

L'algebra booleana a due stati è inoltre importante nella teoria generale delle algebre booleane, perché un'equazione che coinvolge parecchie variabili è generalmente vera in ogni algebra booleana se e soltanto se è vera nell'algebra booleana a due stati. Ciò può, per esempio, essere usato per indicare che le seguenti leggi ( teoremi di consenso ) sono generalmente valide in ogni algebra booleana:

$( a \vee b ) \wedge ( \neg a \vee c ) \wedge ( b \vee c ) = ( a \vee b ) \wedge ( \neg a \vee c)$

$( a \wedge b ) \vee ( \neg a \wedge c ) \vee ( b \wedge c ) = ( a \wedge b ) \vee ( \neg a \wedge c)$

Il raggruppamento di un generico insieme S, forma un'algebra booleana con le due operazioni $\vee$ = unione e $\wedge$ = intersezione. Il più piccolo elemento 0 è l' insieme vuoto ed il più grande elemento 1 è l' insieme S stesso.

L'insieme di tutti i sottoinsiemi di un insieme S che sono limitati è un'algebra booleana.

Per ogni numero naturale n, l'insieme di tutti i divisori positivi di n forma un reticolo distributivo se scriviamo $a \leq b$ per a divide b. Questo reticolo è un'algebra booleana se e soltanto se per ogni n non vi sono divisori quadrati. Il più piccolo elemento,che in generale indichiamo con lo 0, in questa algebra booleana è il numero naturale 1; mentre l'elemento che usualmente indichiamo con l'1 in questi insiemi è l'elemento "n".

Altri esempi di algebre booleane sono dati dagli spazi topologici: se X è uno spazio topologico, allora l'insieme di tutti i sottoinsiemi di X che siano aperti o chiusi formano un'algebra booleana con le operazioni $\vee$ = unione e $\wedge$ = intersezione.

Se R è un anello arbitrario dove è definito un insieme idempotente tipo:

A = { a in R : a² = a e a $\cdot$ x = x $\cdot$ a per ogni x in R }

L'insieme A diventa un'algebra booleana con le operazioni a $\vee$ b = a + b − a $\cdot$ b ed a $\wedge$ b = a $\cdot$ b.

Omomorfismi ed isomorfismi

Un omomorfismo tra due algebre booleane A e B è una funzione f: A $\rightarrow$ B tale che per ogni a, b in A:

f( a $\vee$ b ) = f( a ) $\vee$ f( b )
f( a $\wedge$ b ) = f( a ) $\wedge$ f( b )
f(0) = 0
f(1) = 1

Da queste proprietà segue anche f( $\neg$ a) = $\neg$ f(a) per ogni a in A . Ogni algebra booleana, con la definizione di omomorfismo, forma una categoria. Un isomorfismo da A su B è un omomorfismo da A su B che è biiettivo. L'inverso di un isomorfismo è ancora un isomorfismo, e le due algebre booleane A e B si dicono isomorfe. Dal punto di vista della teoria dell'algebra booleana , due algebre booleane isomorfe non sono distinguibili, ma differiscono soltanto nella notazione dei loro elementi.

Anelli, ideali e filtri booleani

Ad ogni algebra booleana (A, $\wedge$ , $\vee$ ) si può associare un anello (A, +, *) definendo a + b := (a $\wedge \neg$ b) $\vee$ ( b $\wedge \neg$ a ) (questa operazione è detta "differenza simmetrica" nel caso di insiemi e XOR nella logica) ed a * b := (a $\wedge$ b ). In questo anello l'elemento neutro per la somma coincide con lo 0 dell'algebra booleana, mentre l'elemento neutro della moltiplicazione è l'elemento 1 dell'algebra booleana. Questo anello ha la proprietà che a * a = a per ogni a in A; gli anelli con questa proprietà sono chiamati anelli booleani.

Viceversa, assegnato un anello booleano A, possiamo trasformarlo in un'algebra booleana definendo x $\vee$ y = x + y − x $\cdot$ y e x $\wedge$ y = x $\cdot$ y. Poiché queste due operazioni sono l'una l'inversa dell'altra, possiamo affermare che ogni anello booleano è criptomorfo di un'algebra booleana e viceversa. Inoltre, una funzione f : A $\rightarrow$ B è un omomorfismo tra algebre booleane se e soltanto se è un omomorfismo tra anelli booleani. La categoria degli anelli booleani e delle algebre booleane sono equivalenti.

Un anello ideale dell'algebra booleana A è un sottoinsieme I tale che per ogni x, y in I si ha x $\vee$ y in I e per ogni a in A a $\wedge$ x in I. Questa nozione di ideale coincide con la nozione di anello ideale negli anelli booleani. Un ideale I di A è detto primo se I $\neq$ A e se a $\wedge$ b in I implica sempre a in I o b in I. Un ideale I di A è detto massimale se I $\neq$ A e se l'unico ideale proprio contenente I è A stesso. Questa notazione coincide con la notazione teorica del primo ideale e massimo ideale nell'anello booleano A.

Il duale di un ideale è un filtro. Un filtro dell'algebra booleana A è un sottoinsieme F tale che per ogni x, y in F si ha x $\wedge$ y in F e per ogni a in A se a $\vee$ x = a allora a è in F.

L'operazione di complementazione * applicata ai sottoinsiemi manda dunque gli ideali in filtri e viceversa: se B è un'algebra booleana e $I \subseteq B$ un suo ideale (proprio), allora $\tilde I = \{x^*:x\in I\}$ è il filtro (proprio) duale di I. Se invece $F \subseteq B$ è un filtro (proprio), $\tilde F = \{x^*:x\in F\}$ l'ideale (proprio) duale di F .

Rappresentazione delle algebre booleane

Si può dimostrare che ogni reticolo booleano finito è isomorfo al reticolo booleano di tutti i sottoinsiemi di un insieme finito. Di conseguenza, il numero di elementi di ogni reticolo booleano finito ha un sostegno che contiene un numero di elementi uguale ad una potenza di 2.

In figura è rappresentato il diagramma di Hasse dell'algebra di Boole di ordine otto.

Immagine:Cub.png

Marshall Stone ha enunciato il celebre teorema di rappresentazione per le algebre booleane dimostrando che ogni algebra booleana "A" è isomorfa a tutte le algebre booleane aperte-chiuse in un certo spazio topologico, detto compatto non connesso di Hausdorff

Vedi anche

Forma canonica
Sistema formale
Porta logica
Funzione booleana
Mappa di Karnaugh
Diagramma di Venn