Funzione booleana

In matematica e in informatica, una funzione booleana a ${\displaystyle n}$ variabili è una funzione:

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

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

${\displaystyle 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:

${\displaystyle (a+{\overline {x}})\cdot (b+c).}$

Una funzione di tre variabili ${\displaystyle a,}$ ${\displaystyle b}$ e ${\displaystyle 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.

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

${\displaystyle 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, ${\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; 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 ${\displaystyle 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

${\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, ossia l'insieme dei valori che assume la sua ${\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

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

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