Algebra Booleana
In matematica ed informatica l'algebra booleana è quella struttura algebrica dove sono definite le operazioni logiche di OR, AND, XOR (OR esclusivo) e NOT come la teoria degli insiemi definisce le operazioni di unione, intersezione, differenza e complemento degli insiemi.Questa teoria venne così chiamata in onore di George Boole, un matematico inglese, che ha per primo definito le operazioni sopraelencate come facenti parte di una struttura algebrica. La prima definizione è stata redatta nella metà del diciannovesimo secolo. Specificamente, l'algebra booleana era un tentativo di usare le tecniche algebriche per risolvere il problema del calcolo delle proposizioni. Oggi, l'algebra booleana trova molte applicazioni nella progettazione elettronica. Le prime applicazioni pratiche sono state sviluppate da Claude E. Shannon nel ventesimo secolo.
Gli operatori dell'algebra booleana possono essere rappresentati in vari modi. Sono spesso indicati con i loro nomi e cioè AND OR NOT. Nella progettazione di circuiti elettronici, vengono utilizzati anche gli operatori brevi NAND (AND negato), NOR (OR negato) e XNOR (XOR negato), questi operatori sono delle combinazioni degli operatori base e quindi non aggiungono potenza all'algebra, vengono usati solo per rendere la notazione più semplice. I matematici usano spesso il simbolo + per l'AND , e × per l'OR, in quanto per alcuni versi questi operatori lavorano in modo analogo alla somma e alla moltiplicazione. La negazione NOT viene rappresentata da una linea disegnata sopra l'espressione che deve essere negata.
Noi useremo due notazioni, quella tipicamente usata nell'informatica e spesso nell'elettronica, e una utilizzata dalla maggior parte dei logici moderni, con (o ^ per i browsers a che non riconoscono il carattere) per la AND, (o v) per l'OR e ¬ (o ~) per la 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, NAND, XNOR, in questo caso, dopo l'operazione risultata dall'operatore principale (AND, OR, XOR)
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.
L'operatore XOR (detto anche OR esclusivo) restituisce 1 (vero) se solo uno degli elementi è 1 e tutti gli altri 0.
L'operatore XNOR indica un XOR negato (NOT XOR), questo signifca che restituisce 1 solo se un solo elemento è uguale a 0 e tutti gli altri elementi sono 1.
L'algebra booleana è una struttura algebrica ordinata (A,,) con le seguenti quattro proprietà supplementari:
Come ogni insieme ordinato, l'algebra booleana (A, , ) crea un insieme parzialmente ordinato (A, ≤) definendo
In effetti si può anche definire l'algebra booleana come un insieme dotato di proprietà distributiva (A, ≤) (considerato come un insieme parzialmente ordinato) con lo 0 come elemento inferiore e 1come elemento superiore dell'insieme, per ogni elemento xdell'insieme si ha un elemento complementare ¬x tale che
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 molti teoremi validi in tutte le algebre booleane. Per esempio per ogni elemento a e b di un algebra booleana siverifica che:
Analisi generale degli operatori
Operatori base
NOT
OR
AND
L' operazione logica AND (letteralmente e in inglese) restituisce vero se e solo se entrambe le proposizioni hanno valore vero, altrimenti resituisce falso.
AND può essere generalizzata ad un numero arbitrario di proposizioni in ingresso: se sono tutte vere restituisce vero, altrimenti falso, per esempio:
È possibile realizzare un'operazione logica AND con un numero di proposizioni arbitrarie concatenando varie AND a due ingressi, per esempio:XOR
-
Nella teoria degli insiemi corrisponde alla differenza.Operatori Brevi
NOR
NAND
XNOR
-Definizione e prime considerazioni
Da questi assiomi, uno può direttamente ricavare che il più piccolo elemento è lo 0, il più grande elemento è l'1 e l'operatore di ¬a (NOT a, complemento di a) è determinato univocamente.
(ovviamente è equivalente per b = a b).
In questo caso e sono usati per definire intersezione e unione (join) di due elementi. Come prima se esiste l'elemento complementare questo è univocamente definito.
e che entrambi le leggi di deMorgan sono valide.
Si può applicare la teoria della dualità all'algebra booleana. Specificatamente l'ordine ottenuto scambiando gli operatori and è equivalente a quello di partenza ed infatti è un algebra. Ecco il duale della legge distributiva,
In generale, tutte le leggi valide per le algebre booleane possono essere trasformate nelle leggi duali scambiando lo 0 con 1, con , e ≤ con ≥.
| (OR) | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 1 |
| (AND) | 0 | 1 |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
Quest'algebra ha applicazioni in logica, dove 0 è interpretato come "falso", 1 è "vero", è "intersezione", è l'"unione" e ¬ è la "negazione". Le espressioni che coinvolgono le variabili e gli operatori booleani rappresentano le dichiarazioni e due espressioni possono essere dichiarate uguale usando i suddetti assiomi se e soltanto se le forme corrispondenti di dichiarazione sono logicamente equivalenti.
L'algebra booleana a due stati è utilizzata per la progettazione di circuiti elettronici in ingegneria elettronica; in questo ambito 0 e 1 rappresentano i due stati di un circuito digitale, in genere 0 è il livello basso di tensione mentre 1 rappresenta il livello alto della 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 è molto importante nella teoria generale delle algebre booleane, perché un'equazione che coinvolge parecchie variabili è generalmente vera in tutte le algebre booleane se e soltanto se è vera nell'algebra booleana a due stati, la quale può essere controllata con facilità anche da un'analisi a forza bruta. Ciò per esempio può essere usato per dimostrare che le leggi seguenti sono generalmente valide in tutte le algebre booleane:
- (a b) (¬a c) (b c) = (a b) (¬a c)
- (a b) (¬a c) (b c) = (a b) (¬a c)
Per ogni numero narurale n, l'insieme dei divisori positivi di n forma un insieme distributivo se si scrive a ≤ b per indicare a dividee b. Questo insieme è dotato di un algebra booleana se per ogni n non vi siano divisori quadrati. Il più piccolo elemento, quello che usualmente indichiamo con lo 0 in quest'algebra è 1 mentre l'elemento che usualmente indichiamo con l'1 in questi insiemi è l'elemento "n".
Un altro esempio dell'algebra booleana deriva dagli spazi topologici: Se X è uno spazio topologico, l'insieme dei sottoelementi di X formano del caso siano aperti o chiusi un esempio di algebra booleana con gli operatori di = unione e = intersezione.
Se R è un anello arbitrario dove è definito un insieme idempotente tipo:
- A = { m in R : m2 = m e mx = xm per ogni x in R }
Un omomorfismo tra le algebre booleane A e B è una funzione f : A → B che collega ogni a, b in A:
Omomorfismo e isomorfismo
Da ciò segue che f(¬a) = ¬f(a) per ogni a in A. La classe di tutte le algebre booleane, insieme alla nozione di morfismo, forma una categoria. Ogni isomorfismo da A a B è un "omomorfismo" tra A e B e è biiettivo. L'inverso di un isomorfismo è a sua volta un isomorfismo che determina le due algebre booleane isomorfe A e B. Dal punto di vista della teoria booleana dell'algebra, non vi sono motivi di preferire un insieme rispetto all'altro, hanno solo una diversa notazione.
Ogni algebra booleana (A, , ) crea un anello (A, +, *)
se si definisce a + b = (a ¬b) (b ¬a) (questi operatori sono chiamati "differenze simmetriche" nel caso degli insiemi e XOR nel caso della logica) e a * b = a b. L'elemento 0 nell'algebra booleana nell'anello coincide con l'insieme vuoto 0 ; l'operazione di moltiplicare per l'identità coincide con l'1 nell'algebra booleana. Questo anello ha la proprietà che a * a = a per ogni a in A; gli anelli con queste proprietà sono chiamati anelli booleani.
Per contro se un anello booleano "A" è stato già definito possiamo trasformarlo in un'algebra booleana definendo x y = x + y + xy
e x y = xy.
Poiche queste funzioni sono le inverse di quelle di partenza possiamo dire che ogni anello booleano definisce un'algebra e viceversa. In più, se mappiamo f : A → B otteniamo un omomorfismo di un algebra booleana se e solo se abbiamo un omomorfismo di anelli booleani. La categoria degli anelli booleani e delle algebre booleane sono equivalenti.
Un anello ideale nell'algebra booleana A è un sottoinsieme I tale che per ogni x, y in '\'I si ha che x y in I e per ogni a in A si ha a x in I. Questa notazione di ideale coincide con la notazione di anello ideale negli anelli booleani. Un ideale I in A è chiamato primo se I ≠ A e se a b in I implica sempre a in I o b in I. Un ideale I in Aè chiamato massimale se I ≠ A e se è l'unico ideale che contiene I è A medesimo. 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 in un'algebra booleana A è un sottoinsieme p tale che per ogni x, y in p si abbia x y in p e per ogni a in A se a x = a allora a è in p.
Si può dimostrare che ogni algebra booleana finita è isomorfica all'algebra booleana di tutti i sottoinsiemi di un insieme limitato. Di conseguenza il numero di elementi di ogni algebra limitata è una potenza di due.
Stone dichiara nel suo teorema sulla rappresentazione delle algebre booleane che ogni algebra booleana "A" è isomorfica a tutte le algebre booleane aperte-chiuse in un certo spazio topologico, detto compatto non connesso di Hausdorff
Anelli, ideali e filtri booleani
Rappresentazione delle algebre booleane
Vedi anche
| Astronomia | Biologia | Botanica | Chimica | Ecologia | Economia | Fisica | Geometria | Informatica | Matematica | Medicina | Statistica | Telecomunicazioni |
