Funzione booleana

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

$f(x_{1},\dots ,x_{n})\colon B^{n}\rightarrow B$

di variabili booleane $x_{i}$ che assumono valori nello spazio booleano $B=\{0,1\}$, così come $f$ stessa. Con un insieme di $n$ variabili esistono $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$ variabili di input ha solo $2^{n}$ combinazioni possibili e può essere descritta attraverso una tabella, detta tabella di verità, con $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\cdot {\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+{\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)=\ldots +a{\overline {b}}{\overline {c}}+\ldots$

$f(a,b,c)=\ldots \cdot (a+b+{\overline {c}})\cdot \ldots$

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, $\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; le sue funzioni elementari descrivono 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 a $n$ variabili mentre la NOT gode della proprietà di essere unaria, ossia 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(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, ossia l'insieme dei valori che assume la sua $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

• funzione booleana, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Eric W. Weisstein, Funzione booleana, su MathWorld, Wolfram Research.
• (EN) Funzione booleana, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.

Controllo di autorità	GND (DE) 4146281-6