Nsryjdtyk

In matematica e in informatica, una
funzione booleana a n variabili è una funzione:

f(x0,x1,…,xn):Bn→B{displaystyle f(x_{0},x_{1},dots ,x_{n}):B^{n}rightarrow B}

di variabili booleane xi{displaystyle x_{i}} che assumono valori nello spazio booleano B={0,1}{displaystyle B={0,1}}, così come f{displaystyle f} stessa. Con un insieme di n{displaystyle n} variabili esistono 22n{displaystyle 2^{2^{n}}} funzioni possibili.
Le funzioni booleane sono inoltre importanti poiché sono isomorfe ai circuiti digitali, cioè un circuito digitale può essere espresso tramite un'espressione booleana e viceversa; esse dunque svolgono un ruolo chiave nel progetto dei circuiti digitali, ma trovano anche applicazione nella crittografia e nelle telecomunicazioni.
Poiché le variabili possono assumere solo i valori 0 o 1, una funzione booleana con n{displaystyle n} variabili di input ha solo 2n{displaystyle 2^{n}} combinazioni possibili e può essere descritta attraverso una tabella, detta tabella di verità, con 2n{displaystyle 2^{n}} righe.

Espressioni Booleane: definizioni |

Una generica variabile booleana che compare all'interno di una funzione booleana è indicata con una lettera e per questo ci si fa riferimento chiamandola anche letterale. Il prodotto logico di due o più letterali, negati o meno, costituisce una clausola anche chiamata termine elementare. La somma logica di due o più letterali, negati o meno, costituisce un fattore elementare.

Facciamo degli esempi:

a⋅b¯⋅x{displaystyle acdot {overline {b}}cdot x}

Questa è una clausola o termine elementare formato da tre letterali.
Oppure possiamo avere dei fattori elementari che nel prossimo esempio sono messi in AND:

(a+x¯)⋅(b+c){displaystyle (a+{overline {x}})cdot (b+c)}

Una funzione di tre variabili a,b e c può essere espressa in due forme canoniche chiamate forma P che è una somma di prodotti e forma S che è un prodotto di somme: all'interno di queste due forme compaiono rispettivamente clausole con tutte e tre le variabili o fattori elementari con tutte e tre le variabili negate o meno: questi sono chiamati mintermine e maxtermine.

f(a,b,c)=...+ab¯c¯+...{displaystyle f(a,b,c)=...+a{overline {b}}{overline {c}}+...}

f(a,b,c)=...⋅(a+b+c¯)⋅...{displaystyle f(a,b,c)=...cdot (a+b+{overline {c}})cdot ...}

la prima formula rappresenta la forma P, la seconda rappresenta la forma S

Le funzioni booleane elementari |

Tutte le funzioni Booleane, cosiddette generalizzate, sono ottenute mediante la composizione di tre specifiche funzioni dette elementari o fondamentali.
Le funzioni booleane fondamentali sono la AND (solitamente indicata con il segno prodotto: x, ⋅{displaystyle cdot }), la OR (solitamente indicata con il segno più: +) e la NOT (solitamente indicata con il segno ¬ o ! o ancora con un trattino sopra la variabile da negare).
Essendo una funzione booleana la descrizione algebrica o meglio, logica, di un determinato circuito, anche le funzioni elementari descrivono i propri circuiti che in questo caso prendono il nome di porte elementari.
Inoltre le funzioni/porte AND e OR possono anche essere trattate come funzioni generalizzate ad n variabili mentre la NOT gode della proprietà di essere unaria, ovvero può avere in ingresso una sola variabile binaria.

Le funzioni Booleane e il processo di Minimizzazione |

In materia di circuiti digitali, soprattutto in ambito di progettazione logica dei circuiti ha un'importanza notevole il processo di Minimizzazione di una funzione booleana e del circuito che essa descrive, in termini di porte AND, OR e NOT.
In sostanza, si può dire che data una funzione booleana

y=f(x0,x1,…,xn){displaystyle y=f(x_{0},x_{1},dots ,x_{n})}

esistono molteplici sue rappresentazioni, nel senso che in accordo con i Teoremi di Dualità, De Morgan, e gli assiomi dell'Algebra di Boole, la funzione può assumere diverse forme, pur non cambiando il suo numero caratteristico, ovvero l'insieme dei valori che assume la sua y{displaystyle y}.
Minimizzare una funzione, quindi, significa trovare, tra tutte le sue rappresentazioni o forme, quella che ha il numero minimo di porte elementari.

Collegamenti esterni |

• 
  Software MIN per la minimizzazione delle funzioni Booleane (di Dario Mazzeo)

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica