Algebra di Boole

L'algebra di Boole(anche dettaalgebra booleana,logica booleanaoreticolo booleano), inmatematicaelogica matematica, è il ramo dell'algebrain cui levariabilipossono assumere solamente i valoriveroefalso(valori di verità), generalmente denotati rispettivamente come 1 e 0.
Ideata nel 1847 all'University College CorkdaGeorge Boolenel suo libroThe Mathematical Analysis of Logicper scrivere in forma algebrica lalogica proposizionalee da lui ulteriormente sviluppata nel 1854 inAn Investigation of the Laws of Thought, l'algebra di Boole è stata fondamentale nel campo dell'elettronica digitale, dove nella progettazione deicircuiti elettronicirivestono grande importanza i teoremi deducibili dagli assiomi che fondano l'algebra, come ilteorema di Shannondel1940che mostra come scomporre unafunzione booleanacomplessa in funzioni più semplici, o per ottenere un'espressione canonicada unatabella della verità. L'algebra di Boole riveste un ruolo di fondamentale importanza nell'informatica, tanto che ognilinguaggio di programmazionemoderno definisce al suo interno gli operatori logici; è usata inoltre anche nellateoria degli insiemie nellaprobabilità.
Le operazioni fondamentali non sonoaddizioneesottrazionema glioperatori logici: la congiunzione o prodotto logico, indicata con ∧ oppureAND, la disgiunzione o somma logica, indicata con ∨ oppureOR, e la negazione o complementazione, indicata con ¬ oppureNOT. Con tale formalismo si possono descrivere le relazioni logiche in modo simile a quanto fa l'algebra ordinaria con le relazioni numeriche: la combinazione di AND, OR e NOT permette di sviluppare qualsiasifunzione booleanae i tre operatori logici formano pertanto uninsieme funzionalmente completo.
Matematicamente, si dice algebra di Boole un qualunquereticolodotato di proprietà, quali ladistributività, l'esistenza diminimoemassimoe l'esistenza delcomplemento: l'algebra booleana risultacriptomorfa, cioè associata biunivocamente e in modo da risultare logicamente equivalente a uninsieme parzialmente ordinatoreticolato. D'altra parte, ogni algebra booleana risulta criptomorfa a un particolare tipo di anello, chiamatoanello booleano. La struttura può essere specificata attraversogruppieanellio attraverso ireticoliin modo del tutto equivalente.
Più precisamente, si parla di algebra di Boole in riferimento a un insieme K sul quale sono definite le operazioni disomma logica(+, OR) eprodotto logico(*, AND), cioè una terna(K,+,∗){\displaystyle (K,+,*)}, che costituisce un reticolo in cui sono inoltre soddisfatte la proprietà distributiva, l'esistenza delminimoe delmassimoe l'esistenza delcomplemento.
Nel dettaglio, si ha un'algebra di Boole quando su(K,+,∗){\displaystyle (K,+,*)}sono soddisfatte le seguenti proprietà:
Idempotenza
Il modo in cui sono elencate le proprietà vuole mettere in evidenza la simmetria che c'è tra i due operatori, che è poi all'origine dellalegge di dualitàe altre proprietà molto importanti. Nell'elencare gli assiomi, il complemento è stato indicato con un trattino sulla variabile (che è tipograficamente difficile da realizzare, anche se è la notazione migliore); il complemento può anche essere indicato con un "!" (punto esclamativo) antecedente allavariabile booleana(notazione tipica della programmazione in C e C++), con uno slash prima della variabile o addirittura con un segno meno antecedente a essa, quando non è una notazione equivoca. Ilcomplementocorrisponde all'operazione logicaNOT.
Un'ultima osservazione riguarda il fatto che le prime 4 proprietà riguardano i reticoli in generale, mentre le restanti sono proprie dell'algebra di Boole, che sarà quindi indicata con la sestupla(K,+,∗,!,0,1){\displaystyle (K,+,*,!,0,1)}. Data la formulazione generale, da questo momento in poi ci si riferisce all'algebra primordiale, che consideraK={0,1}{\displaystyle K=\{0,1\}}, cioè l'insieme su cui si basa l'algebra di Boole è composto solamente dal minimo e dal massimo.
Si elencano ora la legge di dualità e alcune proprietà derivanti dagli assiomi ora visti con le relative dimostrazioni; oltre a queste conseguenze, ci sono poi due importanti teoremi dell'algebra booleana che sono iteoremi di De Morgane ilteorema di Shannon. I teoremi che si dimostrano ora sono validi per qualsiasi "porzione di realtà" che soddisfa gli assiomi di quest'algebra astratta e, in particolare, saranno applicabili nell'algebra degli insiemi, nell'algebra della logica delle proposizionie nell'algebra dei circuiti.
Da qualsiasi identità booleana se ne può trarre un'altra perdualità, sostituendo cioè a ogni operatore e agli elementi 0 e 1 il rispettivo duale: il duale di + è *, il duale di 0 è 1 (la dimostrazione di questo sta al prossimo paragrafo), il duale diaè in generale!a(a negato, NOT a).
Grazie a questa legge, si può vedere come i 14 postulati dati per definire l'algebra booleana non sono tutti indipendenti tra loro: in particolare, si vede che PX e PX' (per X=1,...,7) sono uno il duale dell'altro.
0 e 1 sono uno il complementare dell'altro: per dimostrarlo basta verificare la definizione di complemento, cioè che
Si vede immediatamente che
applicando rispettivamente la proprietà del minimo e quella del massimo e il teorema ora enunciato risulta così dimostrato.
Si nota che, per come è strutturata quest'algebra, questa dimostrazione ha permesso di dimostrare a partire dagli assiomi che l'elemento neutroesiste ed è unico(l'esistenza non è quindi postulata e l'unicità è insita nell'esistenza essendo solo 2 i valori con cui sta lavorando, cosa non vera per altri tipi di algebra e altre strutture algebriche).
Negando due volte lo stesso elemento, si ottiene l'elemento stesso (logicaaristotelica: una doppia negazione corrisponde a un'affermazione).
Per dimostrarlo, basta considerare l'assioma di esistenza del complemento considerato su due elementiaeb=!a:
Essendo valida la proprietà commutativa e siccome il complemento esiste unico, se ne deduce facilmente che!a¯=a{\displaystyle !{\overline {a}}=a}, che è quello che si voleva dimostrare.
0 è l'elemento neutro della somma (disgiunzione logica, ∨, OR) e 1 è l'elemento neutro del prodotto (congiunzione logica, ∧, AND).
Per la dimostrazione, basta sfruttare la proprietà dell'assorbimento grazie alla quale si deduce che:
Ora, sfruttando la proprietà del massimo e minimo per la quale a*0=0 e a+1=1, si deduce facilmente che:
che è quello che si doveva dimostrare.
L'assorbimento del complemento dice che
Per dimostrarlo, basta applicare la proprietà distributiva secondo la quale:
dopodiché, notando che a+!a=1 e che 1 è l'elemento neutro del prodotto logico risulta dimostrato il teorema.
Per lalegge di dualitàsi capisce anche che esiste un teorema duale a questo che sarà:
Questo teorema può essere preso per vero accettando la validità della legge di dualità, oppure può essere dimostrato in modo del tutto analogo al precedente. Si nota che, nello scrivere l'espressione duale, si è dovuta rispettare la precedenza di applicazione delle operazioni e perciò le parentesi intorno ad a+!b della seconda espressione sononecessarie.
Sex+y=a{\displaystyle x+y=a}exy=0{\displaystyle xy=0}, allorayè unico (o anchexè unico perché si vede che, essendo valida la proprietà commutativa, il ruolo di x e y nelle espressioni è lo stesso).
Per la dimostrazione, si suppone per assurdo che esistano due valori distintiyezche soddisfano le due espressioni, e cioè
Essendo anche che
si è ottenuto che
Nell'ultimo passaggio, si è sfruttato ilprincipio di equivalenza delle eguaglianzee non si è semplificato lax, cosa che non è stata dimostrata e non può essere dimostrata in quest'algebra. Allora, quello che si ha ora è che
Moltiplicando membro a membro e utilizzando la proprietà distributiva, si ha:
cioè y=z e perciò l'elemento che soddisfa le due relazioni scritte sopra è unico.
Come si è accennato prima, nell'algebra di Boole non valgono i principi di eliminazione, cioènon valeche:
Vale chey=zsolamente se queste due espressioni ora scritte valgono contemporaneamente.
L'unica cosa che si può dire invece nel caso in cui valga solo la prima espressione è che:
L'algebra di Boole è la trattazione dell'algebra universalea due stati e dei modelli di tale teoria, dettialgebre booleane. L'algebra universale si occupa di studiare lafamigliadi operazioni su un insieme, dettoinsieme fondamentale della famiglia algebricae, nel caso dellastruttura algebricabooleana, questo contiene i soli valori 0 e 1.
In pratica le algebre booleane si occupano della trattazione delle funzioni booleane di cui ora si accennano le nozioni principali: lo studio di queste funzioni è fondamentale oggi per lo studio di circuiti e reti logiche, perciò se ne possono vedere subito gli scopi pratici, ma l'importanza di queste strutture algebriche non si limita solo a questo perché è anche fondamentale nello studio delle proposizioni e dell'insiemistica, che sono argomenti un po' più astratti ma altrettanto validi e importanti.
Il numero degli argomenti che richiede un'operazione definita sull'insieme fondamentale è dettoarietà(un'addizione ad esempio è un'operazione di arietà 2, anche dettaoperazione binaria): un'operazione su {0,1} di arietànpuò essere applicata a ognuno dei 2possibili valori dei suoinargomenti (cioè basta calcolare le disposizioni di 2 elementi su n posti), ad esempio se si ha un'operazione di arietà 3, dato che K={0,1}, gli argomenti possibili sono 000,001,010,011,100,101,110,111 che sono 8.
Per ogni scelta di argomenti l'operazione può produrre i soli risultati 0 e 1 e per questo ci sono 2operazioni dinargomenti: questo numero corrisponde quindi al numero totale di funzioni possibili dinvariabili nell'algebra booleana.
L'algebra a due stati possiede 2 operazioni con nessun argomento (2) che restituiscono i valori 0 e 1 senza considerare nessun argomento, e 4 operazioni con un solo argomento(2): le operazioni possibili sono due (2), l'identità e la negazione e perciò in totale le operazioni sono 4 in quanto si ha 0→0 (id.), 0→1 (neg.), 1→0 (neg.), 1→1 (id.). Vi sono poi 16operazioni binarie, 256 operazioni ternarie, 65.536 operazioni quaternarie e così via.
Siccome l'algebra di cui sta parlando è fondata su uninsieme finito, una funzione può essere rappresentata oltre che in forma algebrica (cioè composizione di AND, OR e NOT), informa tabellare, cioè con unatabellain cui a ogni composizione delle variabili "di input" (usando una terminologia più informatica) si fa corrispondere l'uscita (o anche le uscite): tutte le funzioni, anche di altre algebre, possono in teoria essere rappresentate tramite tabelle ma se l'insieme su cui è fondata l'algebra è infinito (ad esempio l'insieme deinumeri reali) non è un modo comodo per studiare la funzione; per l'algebra booleana usare le tabelle è un modo utile per studiare le funzioni e ad esempio permette facilmente la costruzione di circuiti e reti logiche nelle applicazioni elettroniche.
Un esempio di tabelle si ha considerando operazioni binarie che si è già visto essere 16:
Unafamiglia, detta ancheindice, è indicizzata da uninsieme di indici, che nel caso di una famiglia di operazioni costituenti un'algebra sono dettisimboli dell'operazionee costituiscono il linguaggio dell'algebra in oggetto. L'operazione indicizzata da un dato simbolo è dettainterpretazionedi tale simbolo, e ogni simbolo definisce il numero univoco di argomenti delle rispettive interpretazioni possibili. Nel caso considerato vi è una corrispondenza biunivoca tra simbolo e interpretazione. L'algebra di Boole ha tanti simboli quante sono le operazioni possibili dettisimboli di operazione booleana, anche se poche operazioni hanno simboli convenzionali, quali ! per la negazione, + per la congiunzione e * per la disgiunzione. In generale si indica confil'i-esimo simbolo dinargomenti.
Nell'ultimo esempio considerato invece si dà un simbolo per ognuna delle 16 funzioni possibili o anche è possibile esprimere ogni funzione come opportuna combinazione dei simboli convenzionali fondamentali, cioè AND (*), OR (+) e NOT (!).
Data una funzionef(x1,x2,…,xn){\displaystyle f(x_{1},x_{2},\dots ,x_{n})}in qualsiasi forma si definiscefunzione dualedif{\displaystyle f}e si indica conδf{\displaystyle \delta f}una funzione che ha per forma la forma duale dif{\displaystyle f}, ad esempio:
La forma duale deve rispettare le precedenze di applicazione dell'operazione della forma di partenza, per questo motivo, laddove non c'erano delle parentesi perché la AND ha precedenza sulla OR, nel momento in cui la AND diventa OR e la OR diventa AND, può esserci bisogno di parentesi.
Un'altra osservazione molto importante è che le variabili, e non le costanti 0 e 1, possono anche non essere negate perché comunque la variabile dovrà assumere tutti i valori possibili e perciò, che ci sia o meno la negazione, la funzione non cambia: nel caso visto prima allora la funzione duale può anche essere scritta come
dove si nota che la costante è stata negata. Questa osservazione può essere importante nel momento in cui si va a progettare unarete logicaperché significa risparmiare porte NOT, o anche in generale, nell'espressione algebrica è sempre utile avere operazioni in meno da fare.
Uninsieme funzionalmente completoè un insieme di operazioni la cui composizione permette di ottenere tutte le operazioni appartenenti all'algebra e a volte ci si riferisce a questi con il terminebase, usato in accezione diversa rispetto allebasi di spazi vettoriali. Le tre principali basi usate nell'algebra booleana sono:
Gli elementi comuni a reticolo e anello sono le costanti 0 e 1 e un'operazione binaria associativa e commutativa, che nella base del reticolo è dettaincontro, dal termine inglesemeet, e denotata tra due elementixeydal simbolox∧y, mentre nella base dell'anello è dettamoltiplicazionee denotataxy. La base del reticolo ha inoltre le operazioni algebriche diunionex∨yecomplemento¬x, mentre la base dell'anello ha l'ulteriore operazione (non aritmetica) diaddizionex⊕yox+y.
Nella base del reticolo a un'algebra booleana (A,∧{\displaystyle \wedge },∨{\displaystyle \vee }) si associa uninsieme parzialmente ordinato(A,≤{\displaystyle \leq }), definendo:
a≤b⇔a=a∧b{\displaystyle a\leq b\Leftrightarrow a=a\wedge b}
che è anche equivalente a
È possibile anche associare un'algebra booleana a unreticolo distributivo(A,≤{\displaystyle \leq }), considerato come insieme parzialmente ordinato, dotato di elemento minimo 0 e di elemento massimo 1, in cui ogni elementoxha un complementare¬x{\displaystyle \neg x}tale che
e
Qui∧{\displaystyle \wedge }e∨{\displaystyle \vee }sono usati per denotare l'infe ilsupdi due elementi. Se i complementi esistono, allora sono unici.
La base dell'anello della generica algebra booleana (A,∧{\displaystyle \wedge },∨{\displaystyle \vee }) è definita come (A, +, *), definendo a + b := (a∧¬{\displaystyle \wedge \neg }b)∨{\displaystyle \vee }(b∧¬{\displaystyle \wedge \neg }a). In tale 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à chea*a=aper ogniainA; gli anelli con questa proprietà sono chiamatianelli booleani.
Viceversa, assegnato un anello booleanoA, esso può essere trasformato in un'algebra booleana definendox∨{\displaystyle \vee }y=x+y−x⋅{\displaystyle \cdot }yex∧{\displaystyle \wedge }y=x⋅{\displaystyle \cdot }y. Poiché queste due operazioni sono l'una l'inversa dell'altra, si può affermare che ogni anello booleano è criptomorfo di un'algebra booleana e viceversa. Inoltre, una funzionef:A→{\displaystyle \rightarrow }Bè unomomorfismotra algebre booleane se e soltanto se è un omomorfismo tra anelli booleani. Lacategoriadegli anelli booleani e delle algebre booleane sono equivalenti.
Un anelloidealedell'algebra booleanaAè un sottoinsiemeItale che per ognix,yinIsi hax∨{\displaystyle \vee }yinIe per ogniainAa∧{\displaystyle \wedge }xinI. Questa nozione di ideale coincide con la nozione dianello idealenegli anelli booleani. Un idealeIdiAè dettoprimoseI≠{\displaystyle \neq }Ae sea∧{\displaystyle \wedge }binIimplica sempreainIobinI. Un idealeIdiAè dettomassimaleseI≠{\displaystyle \neq }Ae se l'unico ideale proprio contenenteIèAstesso. Questa notazione coincide con la notazione teorica dell'ideale primoeideale massimalenell'anello booleanoA.
Il duale di unidealeè unfiltro. Unfiltrodell'algebra booleanaAè un sottoinsiemeFtale che per ognix,yinFsi hax∧{\displaystyle \wedge }yinFe per ogniainAsea∨{\displaystyle \vee }x=aalloraaè inF.
L'operazione dicomplementazione* applicata ai sottoinsiemi manda dunque gli ideali in filtri e viceversa: seBè un'algebra booleana eI⊆B{\displaystyle I\subseteq B}un suo ideale (proprio), alloraI~={x∗:x∈I}{\displaystyle {\tilde {I}}=\{x^{*}:x\in I\}}è il filtro (proprio) duale diI. Se inveceF⊆B{\displaystyle F\subseteq B}è un filtro (proprio),F~={x∗:x∈F}{\displaystyle {\tilde {F}}=\{x^{*}:x\in F\}}l'ideale (proprio) duale diF.
La base Sheffer stroke o NAND si basa sulleoperazioniNOT e AND, tramite le quali è possibile ottenere tutte le operazioni booleane. Un'algebra booleana può essere definita sia da NOT e AND sia da NOT e OR, essendo possibile definire OR attraverso NOT e AND così come AND attraverso NOT e OR:
La collezione di tutti i sottoinsiemi di un datoinsieme, ovvero l'insieme delle partioinsieme ambiente, munita delle operazioni diunione,intersezioneecomplementazionedi insiemi, che giocano rispettivamente il ruolo di OR, AND e NOT, costituisce un'algebra booleana.
Più formalmente, se B è uninsiemeformato da almeno 2 elementi, l'algebra booleana avente B come supporto è la struttura algebrica costituita da B, da dueoperazioni binariesu B,OReAND, da un'operazione unariaNOTsu B e dall'elemento 0 di B, i quali godono delle seguenti proprietà:
L'insieme B è inoltre limitato inferiormente, essendo:
L'elemento 1 è definito come la negazione, o ilcomplementare, dello 0: 1 := NOT(0). L'insieme B è dunque limitato superiormente, essendo:
e in particolare
Si definisce inoltre, come operazione derivata dalle precedenti, l'operatore binarioOR esclusivo, denotato XOR:
In questa algebra all'operatore XOR corrisponde ladifferenza simmetrica:
In elettronica laporta logicaNAND è costituita da n ingressi e un'uscita che si porta a livello 0 solo se gli n ingressi si portano a livello 1. È corrispondente alla connessione in serie di una portaANDe di unaNOT.
Si è visto che gli operatori dell'algebra booleana possono essere rappresentati in vari modi, ma spesso sono scritti semplicemente come AND, OR e NOT che è la scrittura che utilizziamo ora per parlare degli operatori booleani. Nella descrizione dei circuiti, possono anche essere usatiNAND(NOT AND),NOR(NOT OR),XOR(OR esclusivo) eXNOR(NOT OR esclusivo).
Le diverse simbologie per rappresentare gli operatori sono scelte in base al campo in cui si lavora: i matematici usano spesso il simbolo + per l'OR, e × o * 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. Oppure in informatica si utilizza il simbolo | o || per l'OR, & o && per l'AND, e ~ o ! per NOT (es. A OR B AND NOT C equivale a A|B & ~C oppure a A+B*!C). Se ci riferisce agli operatori con i simboli di somma e moltiplicazione e poi intende la negazione come se fosse un'"elevazione a potenza", è facile da ricordare l'ordine di applicazione degli operatori: prima si applicano le negazioni, poi le AND e poi le OR.
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 vengono usati solo per rendere la notazione più semplice.
Operatori:
Valori:
In elettronica digitale viene definito vero un bit 1, sia in Input sia in Output, che di solito assume il valore di 5V, mentre viene definito falso un bit 0, sia in Input sia in Output, che assume il valore di 0V.
Di seguito sono indicati gli operatori più comuni e le rispettiveporte logiche:
L'operatore NOT restituisce il valore inverso a quello in entrata. Una concatenazione di NOT è semplificabile con un solo NOT in caso il numero di ripetizioni sia dispari o con nessuno nel caso il numero di ripetizioni sia pari. Inoltre la porta logica NOT tratta una sola variabile binaria.
Spesso, al fine di 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).
Il simbolo di una porta NOT è
Buffer è la negazione del risultato dell'operazione NOT, pertanto restituisce valore uguale a quello in entrata. Il Buffer non è un vero e proprio operatore, poiché in realtà non manipola l'informazione che riceve, bensì la lascia passare invariata; il Buffer dunque è semplificabile con un collegamento privo di operatori.
Il simbolo di una porta Buffer è:
composta da un NOT in serie a un altro NOT.
La ragione per cui si parla di questo elemento che non modifica il valore in ingresso è data da questioni disincronia dei segnali: quando si tratta di circuiti e reti logiche in modo più approfondito si rende necessario considerare anche il tempo in cui il segnale arriva, pertanto l'elementobufferviene interpretato in questi casi come un ritardo applicato a un certo segnale.
L'operazione AND restituisce come valore 1 se e solo se tutti gli elementi hanno valore 1, mentre restituisce 0 in tutti gli altri casi, come ad esempio quando una porta è alta mentre le altre sono basse e può essere messa in serie. Tale operazione è anche detta prodotto logico. Di seguito la tabella rappresenta l'operatore AND nel caso di due entrate, ma la definizione data ora è generalizzata aningressi:
Siccome questa operazione gode della proprietà associativa, è possibile realizzare un'operazione logica AND con un numero di proposizioni arbitrarie concatenando varie AND a due ingressi, per esempio:
p1∧(p2∧(p3∧p4)){\displaystyle p_{1}\wedge (p_{2}\wedge (p_{3}\wedge p_{4}))}
Neicircuiti digitali, la porta logica AND è un meccanismo comune per avere un segnale di verose e solo seun certo numero di altri segnali sono tutti veri.
Nellateoria degli insiemicorrisponde all'intersezione.
Il simbolo di unaporta ANDè:
L'operazione logica OR restituisce 1 se almeno uno degli elementi è 1, mentre restituisce 0 in tutti gli altri casi. Tale operazione è anche detta somma logica. Di seguito la tabella rappresenta l'operatore OR nel caso di due entrate, ma la definizione data ora è generalizzata aningressi:
Siccome questa operazione gode della proprietà associativa, è possibile realizzare un'operazione logica OR con più ingressi concatenando varie OR a due ingressi, per esempio:
(p1∨p2)∨(p3∨p4){\displaystyle (p_{1}\vee p_{2})\vee (p_{3}\vee p_{4})}
Neicircuiti digitali, la porta logica OR è un meccanismo comune per avere un segnale alto se almeno un segnale è alto e un segnale bassose e solo setutti i segnali sono bassi.
Nellateoria degli insiemicorrisponde all'unione.
Il simbolo di unaporta ORa due ingressi è:
L'operatore XOR, detto anche EX-OR,OR esclusivoosomma modulo 2, restituisce 1 se e solo se il numero degli operandi uguali a 1 èdispari, mentre restituisce 0 in tutti gli altri casi. La tabella rappresenta il caso in cui gli operatori siano 2, poi in generale ci si riferisce a questo operatore comeoperatore di disparità.
Nella teoria degli insiemi corrisponde alladifferenza simmetrica. Per passare nellaforma canonicaSP (somma di prodotti) basta applicare la regola:
A⊕B=A∗!B+!A∗B{\displaystyle =A*!B+!A*B}
dove ⊕ è il simbolo di XOR.
Il simbolo di una porta XOR è:
L'operatore NAND, la negazione del risultato dell'operazione AND, restituisce 0 se e solo se tutti gli elementi sono 1, mentre restituisce 1 in tutti gli altri casi.
Il simbolo di una porta NAND è:
La porta NAND è composta da una porta NOT in serie ad una AND.
Utilizzando leleggi di De Morgan, è possibile convertire una porta OR in NAND. Vale, dunque, la seguente relazione:A∨B=A¯∧B¯¯=A¯↑B¯{\displaystyle A\lor B={\overline {{\overline {A}}\land {\overline {B}}}}={\overline {A}}\uparrow {\overline {B}}}
L'operatore NOR, la negazione del risultato dell'operazione OR, restituisce 1 se e solo se tutti gli elementi sono 0, mentre restituisce 0 in tutti gli altri casi.
Il simbolo di una porta NOR è:
composta da un NOT in serie a un OR.
Utilizzando leleggi di De Morgan, è possibile convertire una porta AND in NOR. Vale, dunque, la seguente relazione:A∧B=A¯∨B¯¯=A¯↓B¯{\displaystyle A\land B={\overline {{\overline {A}}\lor {\overline {B}}}}={\overline {A}}\downarrow {\overline {B}}}
L'operatore XNOR, detto anche EX-NOR o EQU, è la negazione del risultato dell'operazione XOR; nella sua versione a due elementi restituisce 1 se tutti gli elementi sono uguali a 1 oppure se tutti gli elementi sono uguali a 0. Questo operatore viene generalizzato aningressi comeoperatore di parità, cioè è un'operazione che restituisce il valore 1 se il numero di 1 in ingresso èpari.
Il simbolo di una porta XNOR è:
composta da un NOT in serie a un XOR.
Come hanno mostrato già i primi studi pionieristici diJ. Piesch, l'Algebra di Boole si presta bene allo studio degli insiemi, delle proposizioni e dei circuiti. Ci si vuole soffermare su come quest'algebra diventa uno strumento per l'analisi e la sintesi delle reti dicommutazione(inelettrotecnicail termine viene usato per indicare un cambio d'ordine della chiusura di due o più contatti elettrici, intelecomunicazioniha un'accezione diversa).
L'algebra booleana consente di descrivere in forma algebrica le funzioni dei circuiti componenti e delle reti, fornendo altresì i metodi per la realizzazione del progetto logico: è stabilita quindi una corrispondenza biunivoca fra espressioni algebriche e reti di commutazione.
La corrispondenza è facilmente realizzabile avendo già parlato diOperatori booleani: si parte ad esempio da un'espressione algebrica per realizzare un circuito, basta sostituire a ogni operatore logico la corrispondente porta logica e applicare agli ingressi di queste opportunamente le variabili booleane in gioco; inoltre, avendo visto l'esistenza di porte logiche come ad esempio la XOR, che sono combinazioni degli operatori booleani elementari AND, OR e NOT, è possibile manipolare opportunamente un'espressione algebrica in modo da utilizzare il minor numero possibile di porte nella realizzazione del circuito. Viceversa un circuito può essere espresso da una funzione y=f(x1,x2,...xn) doveyè l'uscita, lexsono le entrate e la funzionefè una combinazione di porte logiche.
Nell'algebra dei circuiti si associa il valore 0 al livello logicobassoe il valore 1 al livello logicoalto. In una visione semplificata il valore 0 corrisponde nella pratica a unatensionedi 0 V mentre il valore 1 corrisponde a 5 V, oppure 3,5 V o addirittura 1,5 V: il motivo per cui si preferisce associare il valore alto a 5 V piuttosto che a 1,5 V è che la tensione nella pratica non è stabile e perciò il valore 0 si può "confondere" con il valore 1 causando unaperdita di informazione; d'altra parte però, una tensione di 1,5 V per indicare il valore alto significaminor dispendio di energiaed è un vantaggio molto significativo.
Volendo approfondire il discorso sui valori logici alto e basso e sulla loro realizzazione pratica, si può dire che, a seconda della tecnologia ci sono diversirangedi valori possibili: per esempio, latecnologia TTLassocia il valore logico 0 a una tensione compresa tra 0 V e 0,8 V, tra 0 e 2 V c'è unabanda vietata, cioè un insieme di valori che non devono essere assunti, e il valore logico 1 è associato al range di valori 1,5 V - 5 V. Come si è accennato, la tecnologia odierna spinge sull'abbassare la soglia dei 5 V cercando di stabilizzare sempre di più il potenziale.
Questa algebra ha applicazioni nellalogica, dove 0 è interpretato come "falso", 1 come "vero",∨{\displaystyle \vee }èOR,∧{\displaystyle \wedge }èANDe¬{\displaystyle \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 sonologicamente 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 unbitin uncircuito digitale, in genere bassa e altatensione.
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 stessafunzione di trasferimento. Ogni combinazione dei segnali in ingresso in uscita dal componente può essere rappresentata da un'adeguataespressione 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 (teorema del consenso) sono generalmente valide in ogni algebra booleana:
(a∨b)∧(¬a∨c)∧(b∨c)=(a∨b)∧(¬a∨c){\displaystyle (a\vee b)\wedge (\neg a\vee c)\wedge (b\vee c)=(a\vee b)\wedge (\neg a\vee c)}
(a∧b)∨(¬a∧c)∨(b∧c)=(a∧b)∨(¬a∧c){\displaystyle (a\wedge b)\vee (\neg a\wedge c)\vee (b\wedge c)=(a\wedge b)\vee (\neg a\wedge c)}
A= {ainR:a=aea⋅{\displaystyle \cdot }x=x⋅{\displaystyle \cdot }aper ognixinR}
L'insiemeAdiventa un'algebra booleana con le operazionia∨{\displaystyle \vee }b=a+b−a⋅{\displaystyle \cdot }bea∧{\displaystyle \wedge }b=a⋅{\displaystyle \cdot }b.
Unomomorfismotra due algebre booleaneAeBè unafunzionef:A→{\displaystyle \rightarrow }Btale che per ognia,binA:
Da queste proprietà segue anchef(¬{\displaystyle \neg }a) =¬{\displaystyle \neg }f(a) per ogniain A. Ogni algebra booleana, con la definizione di omomorfismo, forma unacategoria. UnisomorfismodaAsuBè un omomorfismo daAsuBche èbiiettivo. L'inverso di un isomorfismo è ancora un isomorfismo, e le due algebre booleaneAeBsi diconoisomorfe. Dal punto di vista della teoria dell'algebra booleana, due algebre booleane isomorfe non sono distinguibili, ma differiscono soltanto nella notazione dei loro elementi.
All'interno di ciascuna algebra di Boole, dato un insieme di variabili e le operazioni correlate, è possibile definire delle espressioni che vengono ad assumere un determinato valore ottenibile anche sotto forme diverse. Possono esistere cioè delle espressioni che, pur essendo differenti, si rivelino equivalenti. Oltre al fatto che le espressioni booleane assumono una particolare importanza per quanto riguarda ilcalcolo proposizionale, in cui le variabili sono proposizioni legate tramite congiunzioni, disgiunzioni, negazioni e altre operazioni più complesse, possono esistere moltissime altre espressioni, accomunate sempre dalle proprietà e dagli assiomi booleani, nelle quali si sostituisce spesso l'operazione + (comunemente detta somma) con ∨ e * (comunemente detta prodotto) con ∧ e in cui la complementazione è indicata col simbolo ' .
Per poter presentare nel modo più efficiente un'espressione booleana, la si riduce insomma di prodotti fondamentalioforma normale disgiuntiva. Un prodotto fondamentale è un prodotto in cui ciascuna variabile, o il suo complemento, appaia una sola volta e rigorosamente fuori da parentesi o complementazioni complesse.Ad esempio, date le variabili x, y, z all'interno di un'algebra di Boole, sono prodotti fondamentali
Mentre non sono prodotti fondamentali
È così possibile avere una somma di prodotti fondamentali, forma in cui ogni espressione può essere ridotta, ma che non è unica. Un esempio è: xy + xz + z'. Nel momento in cui ogni singola variabile, o il suo complemento, siano contenuti in tutti i prodotti fondamentali dellaforma normale disgiuntiva, si ha allora unasomma di prodotti fondamentali completaoforma normale disgiuntiva completa. Tale scrittura è unica, pertanto se due espressioni sono equivalenti avranno la stessa forma normale disgiuntiva completa.
Se si desidera invece che un'espressione sia scritta nel modo più corto possibile, allora la si esprime insomma di implicanti prime o minimali(Minimizzazione di Quine-McQluskey). Un'implicante prima(o minimale) rispetto a un'espressione è un prodotto fondamentale che non altera l'espressione se sommato per intero a essa, cioè restituisce un risultato equivalente a quella iniziale; sommando un prodotto strettamente contenuto nell'implicante, tuttavia, non si ottiene un'equivalenza.Per individuare tutte le implicanti prime, esistono varie tecniche, tra cui ilmetodo del consenso, che si basa sull'applicazione ciclica delle proprietà di assorbimento,idempotenza, involuttività e di De Morgan accompagnate a ogni passo dall'opportuna addizione di un consenso. Dati due prodotti fondamentali, se solo e solo se una variabile appare in uno di essi non negata e nell'altro negata si chiama consenso il risultato della moltiplicazione delle restanti variabili. Ad esempio:
Lasomma di implicanti primeè unica, pertanto due espressioni equivalenti avranno la stessa. Nel momento in cui, completando ogni singola implicante prima, l'apporto all'espressione di una o più di esse è inutile in quanto contenuta nelle altre, la si può eliminare ottenendo la più essenziale delle scritture, laforma minimale. Essa, pur essendo comoda, ha l'inconveniente di non essere unica, e dunque di non consentire l'individuazione di equivalenze tra più espressioni.
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 a unapotenza di 2.
Marshall Stoneha enunciato il celebreteorema di rappresentazione per le algebre booleanedimostrando cheognialgebra booleana "A" è isomorfa a tutte le algebre booleaneaperte-chiusein un certospazio topologicocompattonon connessodi Hausdorff.