Algebra di Boole: differenze tra le versioni

Versione delle 15:35, 25 mag 2024

Versione attuale delle 00:40, 6 ott 2025

(4 versioni intermedie di 3 utenti non mostrate)

Riga 5:

== 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 12:

Più precisamente, si parla di algebra di Boole in riferimento a un insieme K sul quale sono definite le operazioni di ''somma logica'' (+, OR) e ''prodotto logico'' (*, AND), cioè una terna <math>(K,+,*)</math>, che costituisce un reticolo in cui sono inoltre soddisfatte la proprietà distributiva, l'esistenza del ''minimo'' e del ''massimo'' e l'esistenza del ''complemento''.

Nel dettaglio, si ha un'algebra di BooooooooooooooooooooooooooooooooooleBoole quando su <math>(K,+,*)</math> sono soddisfatte le seguenti proprietà:

;Commutativa

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 145:

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.

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

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

Riga 432:

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

Riga 711:

== Voci correlate ==

{{Div col}}

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

* [[Algebra di insiemi]]

Riga 728 ⟶ 729:

* [[Teoria degli insiemi]]

* [[Algebra di Robbins]]

{{Div col end}}

== Altri progetti ==

Riga 734 ⟶ 736:

== Collegamenti esterni ==

* {{Collegamenti esterni}}

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

* {{cita web|https://www.isgroup.unimo.it/corsi/infogen/IntroAlgebraBool.pdf|Introduzione all’algebra Booleana}}

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