Pagina iniziale | Navigazione |
Google

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.

Table of contents
1 Analisi generale degli operatori
2 Definizione e prime considerazioni
3 Esempi
4 Omomorfismo e isomorfismo
5 Anelli, ideali e filtri booleani
6 Rappresentazione delle algebre booleane
7 Vedi anche

Analisi generale degli operatori

Operatori base

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)

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.

  • 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.

-

  • 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.

Operatori Brevi

NOR

NAND

XNOR

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.

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

-

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

Definizione e prime considerazioni

L'algebra booleana è una struttura algebrica ordinata (A,,) con le seguenti quattro proprietà supplementari:

  1. limitata inferiormente : Esiste un elemento 0, tale che a 0 = a per il ogni a in A (a OR 0 = a per il ogni a in A).

  2. limitata superiormente : Esiste un elemento 1, tale che a 1 = a per il ogni a in A (a AND 1 = a per il ogni a in A).
  3. supporta la legge distributiva : Per ogni a, b, c in A, ( a b) c = (a c) (b c); (a OR b) AND c = (a AND c) OR (b AND c).
  4. esiste il complementare: Per ogni a in A esiste un elemento ¬a in A tale che a ¬a=1 e a¬a = 0 (a OR NOT a = 1 e a AND NOT a = 0).

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.

Come ogni insieme ordinato, l'algebra booleana (A, , ) crea un insieme parzialmente ordinato (A, ≤) definendo

ab se a = a b
(ovviamente è equivalente per b = a b).

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

x ¬x = 0 e x ¬x = 1

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.

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:

  • a 0 = 0 e a 1 = 1,
  • ¬1 = 0 e ¬0 = 1,
  • ¬ ¬ a = a
e che entrambi le leggi di deMorgan sono valide.
  • ¬(a b) = (¬a) (¬b) e ¬(a b) = (¬a) (¬b)

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,
  • (a b) c = (a c) (b c)
In generale, tutte le leggi valide per le algebre booleane possono essere trasformate nelle leggi duali scambiando lo 0 con 1, con , e ≤ con ≥.

Esempi

Un algebra booleana molto importante è formata solo da due elementi, 0 e 1, e definisce queste regole

       
(OR)01
001
111

(AND)01
000
101

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)

IL raggruppamento di un generico insieme S forma un'algebra booleana se supporta gli operatori di = unione e = intersezione. Il più piccolo elemento deve essere lo 0 che deverappresentare l'insieme vuoto e l'elemento tiù grande deve essere l'1 che rappresenta l'insieme S.

Per ogni numero narurale n, l'insieme dei divisori positivi di n forma un insieme distributivo se si scrive ab 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 }
allora l'insieme "A" è un algebra booleana con gli operatori m f = m + f + mf e m f = mf.

Omomorfismo e isomorfismo

Un omomorfismo tra le algebre booleane A e B è una funzione f : AB che collega ogni a, b in A:

f(a b) = f(a) f(b)
f(a b) = f(a) f(b)
f(0) = 0
f(1) = 1
Da ciò segue che fa) = ¬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.

Anelli, ideali e filtri booleani

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 : AB 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 IA e se a b in I implica sempre a in I o b in I. Un ideale I in Aè chiamato massimale se IA 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.

Rappresentazione delle algebre booleane

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

Vedi anche


Astronomia | Biologia | Botanica | Chimica | Ecologia | Economia | Fisica | Geometria | Informatica | Matematica | Medicina | Statistica | Telecomunicazioni


GNU Fdl - it.Wikipedia.org




Google | 

Enciclopedia |  La Divina Commedia di Dante |  Mappa | : A |  B |  C |  D |  E |  F |  G |  H |  I |  J |  K |  L |  M |  N |  O |  P |  Q |  R |  S |  T |  U |  V |  W |  X |  Y |  Z |