# 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. Fissato un certo $n$ (ovvero l'arietà della funzione), esistono esistono $2^{2^{n}}$ possibili funzioni di questo tipo.
Le funzioni booleane, che prendono il nome da George Boole, sono 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.