Algebra di Boole: differenze tra le versioni

Versione delle 10:34, 3 giu 2019

Versione attuale delle 00:40, 6 ott 2025

(68 versioni intermedie di 47 utenti non mostrate)

Riga 1:

L{{'}}'''algebra di Boole''' (anche detta '''algebra booleana''', '''logica booleana''' o '''reticolo booleano'''), in [[matematica]] e [[logica matematica]], è il ramo dell'[[algebra]] in cui le [[variabile (matematica)|variabili]] possono assumere solamente i valori ''vero'' e ''falso'' ([[valore di verità|valori di verità]]), generalmente denotati rispettivamente come 1 e 0.

== Cenni storiciStoria ==

Ideata nel 1847 all'[[University College Cork]] da [[George Boole]] nel suo libro ''The Mathematical Analysis of Logic'' per scrivere in forma algebrica la [[logica proposizionale]] e da lui ulteriormente sviluppata nel 1854 in ''An Investigation of the Laws of Thought'', l'algebra di Boole è stata fondamentale nel campo dell'[[elettronica digitale]], dove nella progettazione dei [[Circuito elettronico|circuiti elettronici]] rivestono grande importanza i teoremi deducibili dagli assiomi che fondano l'algebra, come il [[Teorema di Shannon (elettronica)|teorema di Shannon]] del [[1940]] che mostra come scomporre una [[funzione booleana]] complessa in funzioni più semplici, o per ottenere un'[[Forma canonica#Algebra booleana|espressione canonica]] da una [[tabella della verità]]. L'algebra di Boole riveste un ruolo di fondamentale importanza nell'[[informatica]], tanto che ogni [[linguaggio di programmazione]] moderno definisce al suo interno gli operatori logici; è usata inoltre anche nella [[teoria degli insiemi]] e nella [[probabilità]].

== Descrizione ==

Le operazioni fondamentali non sono [[addizione]] e [[sottrazione]] ma gli [[connettivo logico|operatori logici]]: la congiunzione o prodotto logico, indicata con ∧ oppure [[Algebra di Boole#AND|AND]];, la disgiunzione o somma logica, indicata con ∨ oppure [[Algebra di Boole#OR|OR]];, e la negazione o complementazione, indicata con ¬ oppure [[Algebra di Boole#NOT|NOT]]. 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 qualsiasi [[Algebra di Boole#Funzioni booleane|funzione booleana]] e i tre operatori logici formano pertanto un ''insieme funzionalmente completo''.

== Definizione formale ==

Riga 25:

;Distributiva

:<math>a*(b+c)=(a*b)+(a*c) \qquad a+(b*c)=(a+b)*(a+c)</math>

:

'''Idempotenza'''

: <math>a+a=a \qquad a*a=a</math>

Riga 35:

:<math>a*\overline{a}=0 \qquad a+\overline{a}=1</math>

Il modo in cui sono elencate le proprietà vuole mettere in evidenza la simmetria che c'è tra i due operatori, che è poi all'origine della [[#Legge di dualità|''legge di dualità'']] e altre proprietà molto importanti. Nell'elencare gli assiomi, il complemento è stato indicato con un "!"trattino (puntosulla esclamativo)variabile antecedente(che allaè ''[[variabiletipograficamente booleana]]''difficile (notazioneda tipicarealizzare, dellaanche programmazionese inè Cla enotazione C++migliore); il complemento può anche essere indicato con un trattino"!" sulla(punto variabileesclamativo) (cheantecedente èalla tipograficamente''[[variabile difficilebooleana]]'' da(notazione realizzare,tipica anchedella seprogrammazione èin laC notazionee miglioreC++), con uno slash prima della variabile o addirittura con un segno meno antecedente a essa, quando non è una notazione equivoca. Il ''complemento'' corrisponde all'operazione logica ''NOT''.

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 <math>(K,+,*,!,0,1)</math>. Data la formulazione generale, da questo momento in poi ci si riferisce all'''algebra primordiale'', che considera <math>K=\{0,1\}</math>, cioè l'insieme su cui si basa l'algebra di Boole è composto solamente dal minimo e dal massimo.

Riga 53:

Si vede immediatamente che

:<math>1*0=0 \qquad 0+1+0=1</math>

applicando rispettivamente la proprietà del minimo e quella del massimo e il teorema ora enunciato risulta così dimostrato.

Riga 60:

=== Convoluzione ===

[[Negando]] due volte lo stesso elemento, si ottiene l'elemento stesso (logica [[Aristotelismo|aristotelica]]: una doppia negazione corrisponde a un'affermazione).

Per dimostrarlo, basta considerare l'assioma di esistenza del complemento considerato su due elementi ''a'' e ''b=!a'':

Riga 71:

=== Elementi neutri ===

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:

Riga 138:

== Funzioni booleane ==

{{vedi anche|Funzione booleana}}

L'algebra di Boole è la trattazione dell'[[algebra universale]] a due stati e dei modelli di tale teoria, detti ''algebre booleane''. L'algebra universale si occupa di studiare la [[Famiglia (matematica)|famiglia]] di operazioni su un insieme, detto ''insieme fondamentale della famiglia algebrica'', e, nel caso della [[struttura algebrica]] booleana, 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 una un'operazione definita sull'insieme fondamentale è detto [[arietà]] (un'addizione ad esempio è un'operazione di arietà 2, anche detta ''operazione binaria''): un'operazione su {0,1} di arietà ''n'' può essere applicata a ognuno dei 2^''n'' possibili valori dei suoi ''n'' argomenti (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 2^{<span>2ⁿ</span>} operazioni di ''n'' argomenti: questo numero corrisponde quindi al numero totale di funzioni possibili di ''n'' variabili nell'algebra booleana.

L'algebra a due stati possiede 2 operazioni con nessun argomento (2^2⁰) che restituiscono i valori 0 e 1 senza considerare nessun argomento, e 4 operazioni con un solo argomento(2^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→0ha {0,1} → {0,1} (id.), 0→1{0,1} → {1,0} (neg.), 1→0{0,1} → 0 (neg.falso), 1→1{0,1} → 1 (id.vero). Vi sono poi 16 [[Operazione binaria|operazioni binarie]], 256 operazioni ternarie, 65.536 operazioni quaternarie e così via.

Siccome l'algebra di cui sta parlando è fondata su un [[insieme finito]], una funzione può essere rappresentata oltre che in forma algebrica (cioè composizione di AND, OR e NOT), in ''forma tabellare'', cioè con una [[Tabella della verità|tabella]] in 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 dei [[Numero reale|numeri 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:

Riga 153:

!A

!B

!f0

!f1

!f2

Riga 168 ⟶ 169:

!f14

!f15

!f16

|-

|0

Riga 247:

|}

Una [[Famiglia (matematica)|famiglia]], detta anche ''indice'', è indicizzata da un [[insieme di indici]], che nel caso di una famiglia di operazioni costituenti un'algebra sono detti ''simboli dell'operazione'' e costituiscono il linguaggio dell'algebra in oggetto. L'operazione indicizzata da un dato simbolo è detta ''interpretazione'' di 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 detti ''simboli di operazione booleana'', anche se poche operazioni hanno simboli convenzionali, quali ! per la negazione, + per la congiunzione e * per la disugiunzionedisgiunzione. In generale si indica con ^''n''''f''_''i'' l'i-esimo simbolo di ''n'' argomenti.

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 (!).

Riga 253:

Data una funzione <math>f(x_1, x_2, \dots,x_n)</math> in qualsiasi forma si definisce ''funzione duale'' di <math>f</math> e si indica con <math>\delta f</math> una funzione che ha per forma la forma duale di <math>f</math>, ad esempio:

:<math>y=\overline a +b*(c+0) \qquad duale=a*( \overline b + \overline c *1)</math>

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.

Riga 261:

:<math>duale= \overline a *(b+c*1)</math>

dove si nota che la costante è stata negata. Questa osservazione può essere importante nel momento in cui si va a progettare una [[rete logica]] perché significa risparmiare porte NOT, o anche in generale, nell'espressione algebrica è sempre utile avere operazioni in meno da fare.

== Basi ==

Un ''insieme 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 termine '''base''', usato in accezione diversa rispetto alle ''[[Base (algebra lineare)|basi di spazi vettoriali]]''. Le tre principali basi usate nell'algebra booleana sono:

* Il [[Reticolo (matematica)|reticolo]], una base logica introdotta nel diciannovesimoXIX secolo da [[George Boole]], [[Charles Sanders Peirce]] e altri matematici che cercavano una formalizzazione algebrica dei processi logici.

* L'[[anello booleano]], una base (non aritmetica) introdotta nel ventesimoXX secolo da [[Ivan IvanovichIvanovič ZhegalkinŽegalkin]]<!--Жегалкин, Иван Иванович--> e [[Marshall Stone]] che proviene dall'[[algebra astratta]].

* La base [[NAND]], originata dal fatto che tramite l'operazione di NAND è possibile ottenere tutte le operazioni sull'insieme {0,1}. Tale base è utilizzata in particolare nella configurazione dei [[Circuito digitale|circuiti logici]] in [[elettronica digitale]].

Riga 293:

La base dell'anello della generica algebra booleana (''A'', <math>\wedge</math>, <math>\vee</math>) è definita come (''A'', +, *), definendo a + b := (''a'' <math>\wedge \neg</math> ''b'') <math>\vee</math> ( ''b'' <math>\wedge \neg</math> ''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à che ''a'' * ''a'' = ''a'' per ogni ''a'' in ''A''; gli anelli con questa proprietà sono chiamati [[anello booleano|anelli booleani]].

Viceversa, assegnato un anello booleano ''A'', esso può essere trasformarlotrasformato in un'algebra booleana definendo ''x'' <math>\vee</math> ''y'' = ''x'' + ''y'' − ''x'' <math>\cdot</math> ''y'' e ''x'' <math>\wedge</math> ''y'' = ''x'' <math>\cdot</math> ''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 funzione ''f'' : ''A'' <math>\rightarrow</math> ''B'' è un [[omomorfismo]] tra algebre booleane se e soltanto se è un omomorfismo tra anelli booleani. La [[Teoria delle categorie|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'' <math>\vee</math> ''y'' in ''I'' e per ogni ''a'' in ''A'' ''a'' <math>\wedge</math> ''x'' in ''I''. Questa nozione di ideale coincide con la nozione di [[Ideale (matematica)#Definizione|anello ideale]] negli anelli booleani. Un ideale ''I'' di ''A'' è detto ''primo'' se ''I'' <math>\neq</math> ''A'' e se ''a'' <math>\wedge</math> ''b'' in ''I'' implica sempre ''a'' in ''I'' o ''b'' in ''I''. Un ideale ''I'' di ''A'' è detto ''massimale'' se ''I'' <math>\neq</math> ''A'' e se l'unico ideale proprio contenente ''I'' è ''A'' stesso. Questa notazione coincide con la notazione teorica del dell'[[ideale primo]] e [[ideale massimale]] nell'anello booleano ''A''.

Il duale di un ''ideale'' è un ''filtro''. Un [[filtro (matematica)|filtro]] dell'algebra booleana ''A'' è un sottoinsieme ''F'' tale che per ogni ''x'', ''y'' in ''F'' si ha ''x'' <math>\wedge</math> ''y'' in ''F'' e per ogni ''a'' in ''A'' se ''a'' <math>\vee</math> ''x'' = ''a'' allora ''a'' è in ''F''.

Riga 342:

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 usati [[Algebra di Boole#NAND|NAND]] (NOT AND), [[Algebra di Boole#NOR|NOR]] (NOT OR), [[Algebra di Boole#XOR|XOR]] (OR esclusivo) e [[Algebra di Boole#XNOR|XNOR]] (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 una 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.

Riga 365:

=== NOT ===

{{vedi anche|Invertitore}}

L'operatore NOT restituisce il valore inverso a quello in entrata. Una concatenazione di NOT è semplificabile con un solo NOT in caso diil disparinumero di ripetizioni sia dispari o con nessuno nel caso il numero di ripetizioni sia pari. Inoltre la porta logica NOT possiedetratta una sola variabile binaria.

{| class=wikitable style="font-size:95%"

Riga 385:

=== Buffer ===

Buffer è la negazione del risultato dell'operazione NOT;, restituiscepertanto ilrestituisce 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.

{| class=wikitable style="font-size:95%"

Riga 402:

composta da un NOT in serie a un altro NOT.

La ragione per cui si parla di questo "pseudo-operatore"elemento che non modifica il valore in ingresso è data da questioni di ''sincronia 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, epertanto l'elemento ''buffer'' viene interpretato in questi casi come un ritardo applicato a un certo segnale.

=== AND ===

L'operazione AND restituisce come valore 1 se e solo se tutti gli operandielementi 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 a ''n'' ingressi:

{| class=wikitable style="font-size:95%"

Riga 430:

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:

<math> p_1 \wedge (p_2 \wedge (p_3 \wedge p_4))</math>

Nei [[circuito digitale|circuiti digitali]], la porta logica AND è un meccanismo comune per avere un segnale di vero [[se e solo se]] un certo numero di altri segnali sono tutti veri.

Nella [[teoria degli insiemi]] corrisponde all'[[Intersezione (insiemistica)|intersezione]].

Il simbolo di una [[porta AND]] è:

:[[File:AND ANSI.svg]]

=== OR ===

{{vedi anche|Disgiunzione logica}}

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 a ''n'' ingressi:

Riga 465 ⟶ 466:

Siccome questa operazione gode della proprietà associativa, è possibile realizzare un'operazione logica OR con più ingressi concatenando varie OR a due ingressi, per esempio:

<math> (p_1 \vee p_2) \vee (p_3 \vee p_4)</math>

Nei [[circuito digitale|circuiti digitali]], la porta logica OR è un meccanismo comune per avere un segnale alto se almeno un segnale è alto e un segnale basso [[se e solo se]] tutti i segnali sono bassi.

Nella [[teoria degli insiemi]] corrisponde all'[[Unione (insiemistica)|unione]].

Il simbolo di una [[porta OR]] a due ingressi è:

:[[File:OR ANSI.svg]]

=== XOR ===

{{Vedi anche|Disgiunzione esclusiva}}

L'operatore XOR, detto anche EX-OR, ''OR esclusivo'' o ''somma 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 come ''operatore di disparità''.

Riga 509 ⟶ 511:

=== NAND ===

{{vedi anche|Porta NAND|Operatore di Sheffer}}

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.

Riga 535 ⟶ 538:

:[[File:NAND ANSI.svg]]

La porta NAND è composta da ununa porta NOT in serie aad ununa AND.

Utilizzando le [[leggi di De Morgan]], è possibile convertire una porta OR in NAND. Vale, dunque, la seguente relazione: <math>A \lor B = \overline{ \overline A \land \overline B} = \overline A \uparrow \overline B</math>

Riga 600 ⟶ 603:

== Algebra dei circuiti ==

LCome hanno mostrato già i primi studi pionieristici di [[Johanna Piesch|J. Piesch]]<ref>{{de}} H. Piesch, H. Sequenz, ''Die Österreichischen Wegbereiter der Theorie der Elektrischen Schaltungen'' (I pionieri austriaci della teoria della commutazione elettrica), Elecktrotechnik & Maschinenbau, Vol. 75, pp. 241-245</ref>, 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 di [[Commutazione (telecomunicazioni)|commutazione]] (in [[elettrotecnica]] il termine viene usato per indicare un cambio d'ordine della chiusura di due o più contatti elettrici, in [[telecomunicazioni]] ha 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 di [[Operatori 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 elementatielementari 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) dove ''y'' è l'uscita, le ''x'' sono le entrate e la funzione ''f'' è una combinazione di porte logiche.

Nell'algebra dei circuiti si associa il valore 0 al livello logico ''basso'' e il valore 1 al livello logico ''alto''. In una visione semplificata il valore 0 corrisponde nella pratica a una [[Differenzatensione di potenziale elettricoelettrica|tensione]] di 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 una ''perdita di informazione''; d'altra parte però, una tensione di 1,5 V per indicare il valore alto significa ''minor dispendio di energia'' ed è 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 diversi ''range'' di valori possibili: per esempio, la [[Transistor-transistor logic|tecnologia TTL]] associa il valore logico 0 a una tensione compresa tra 0 V e 0,8 V, tra 0 e 2 V c'è una ''banda vietata'', cioè un insieme di valori che non devono essere asuntiassunti, 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.

== Esempi ==

Questa algebra ha applicazioni nella [[logica]], dove 0 è interpretato come "falso", 1 come ''"vero''", <math>\vee</math> è ''OR'', <math>\wedge</math> è ''AND'' e <math>\neg</math> è "''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 (informatica)|bit]] in un [[circuito digitale]], in genere bassa e alta [[tensione elettrica|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]]

Riga 642 ⟶ 645:

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 il [[calcolo 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 una un'espressione booleana, la si riduce in ''somma di prodotti fondamentali'' o ''forma 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.<br />Ad esempio, date le variabili x, y, z all'interno di un'algebra di Boole, sono prodotti fondamentali

* P(x,y,z) = xy

* P(x,y,z) = x'yz'

Riga 649 ⟶ 652:

* yy'z

* (xy)'

È 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 della [[forma normale disgiuntiva]], si ha allora una ''somma di prodotti fondamentali completa'' o ''forma 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 in ''somma di implicanti prime o minimali'' (Minimizzazione di Quine-McQluskey). <nowiki>Un'</nowiki>''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.<br />Per individuare tutte le implicanti prime, esistono varie tecniche, tra cui il ''metodo 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:

* dati P = xyz, Q = x'z il consenso sarà C = yzz = yz

* dati P = xy' Q= xy il consenso sarà C = xx = x

Riga 662 ⟶ 665:

[[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 [[Insieme chiuso-aperto|aperte-chiuse]] in un certo [[spazio topologico]] [[spazio compatto|compatto]] [[spazio connesso|non connesso]] [[spazio di Hausdorff|di Hausdorff]].

== Note ==

<references />

== Bibliografia ==

* {{Cita testo|titolo=Le basi dell'elettronica - L'algebra di Boole|url=https://archive.org/details/lebasidellelettronicalalgebradiboole|autore=Giuseppe Calabrese|editore=Editoriale Delfino|città=Milano|anno=1973|ISBN=}}

* Giuseppe Calabrese, ''L'algebra di Boole. La logica applicata agli automatismi'', Milano, Editoriale Delfino, 1974.

* {{Cita libro

| cognome = Givant

| nome = Steven

|nome2= Paul

|cognome2= Halmos

| anno = 2009

| titolo = Introduction to Boolean Algebras

|url = https://archive.org/details/introductiontobo0000giva

| editore = Undergraduate Texts in Mathematics, [[Springer Science+Business Media|Springer]]

| isbn= 978-0-387-40293-2

| lingua= en

}}

* {{Cita libro

| cognome = Boole

| nome = George

| wkautore = George Boole

| titolo = An Investigation of the Laws of Thought

|url = https://archive.org/details/lawsofthought0000bool

| editore = Prometheus Books

| annooriginale = 1854

| anno = 2003

|anno = 2003
|isbn = 978-1-59102-089-9

| lingua = en

}}

* {{Cita libro

| cognome = Givant

| nome = Steven

|nome2= Paul

|cognome2= Halmos

| anno = 2009

| titolo = Introduction to Boolean Algebras

|url = https://archive.org/details/introductiontobo0000giva

| editore = Undergraduate Texts in Mathematics, [[Springer Science+Business Media|Springer]]

| isbn= 978-0-387-40293-2

| lingua= en

}}

* {{Cita libro|autore=John A. Camara|titolo=Electrical and Electronics Reference Manual for the Electrical and Computer PE Exam|url=http://books.google.com/books?id=rfHWHeU0jfsC&pg=SA41-PA3|anno=2010|editore=wwwProfessional Publications Inc.ppi2pass.com|pagine=41|isbn=978-1-59126-166-7|lingua=en}}

== Voci correlate ==

{{Div col}}

* [[06-XX]], sezione primaria dello schema di classificazione [[MSC 2000]]

* [[Algebra di insiemi]]

Riga 716 ⟶ 728:

* [[Teoremi di De Morgan]]

* [[Teoria degli insiemi]]

* [[Algebra di Robbins]]

{{Div col end}}

== Altri progetti ==

{{interprogetto|preposizione=sull'|wikt=algebra di Boole}}

{{wikilibro|Paradossi}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

* {{FOLDOC|Boolean algebra|Boolean algebra}}

* {{cita web|httphttps://www.matematicamenteisgroup.unimo.it/staticfilescorsi/appuntiinfogen/A.Urso-Logica_booleanaIntroAlgebraBool.pdf|Introduzione alla logicaall’algebra Booleana}}

* {{cita web|http://wwwusers.di.uniroma1.it/~arc1/boole.pdf|Panoramica sull'Algebra Booleana}}

* {{cita web | 1 = http://www.ing.unisannio.it/dilucca/materiale/aa0809/Alg_boole.pdf | 2 = Facoltà di Ingegneria Energetica - Univ. del Sannio - Elementi di Informatica: Algebra di Boole 2008/2009 | accesso = 13 agosto 2012 | urlarchivio = https://web.archive.org/web/20121224050928/http://www.ing.unisannio.it/dilucca/materiale/aa0809/Alg_boole.pdf | dataarchivio = 24 dicembre 2012 | urlmorto = sì }}