Funzione booleana

In matematica, una funzione booleana a n variabili è una funzione:

$f(x_0, x_1, \dots, x_n): 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 dando una tabella, detta tabella di verità, con $2^n$ righe.

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 ¬ ). 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(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$. 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