Funzione booleana

Da Wikipedia, l'enciclopedia libera.

In matematica, una funzione booleana è una funzione

F(b₁, b₂, ..., b_n)

di un numero n di variabili booleane b_i che assumono valori nello spazio booleano B = {0, 1}, cosi come F assume valori in B. Con un insieme di n variabili esistono 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.

Le funzioni booleane fondamentali sono la AND (solitamente indicata con il segno meno: - ), la OR (solitamente indicata con il segno più: +) e la NOT (solitamente indicata con il segno ¬ ); dalla combinazione delle funzioni boolene fondamentali si ottengono tutte le altre possibili funzioni. Poiché le variabili possono assumere solo i valori 0 o 1 una funzione booleana con n variabili di input ha solo 2ⁿ combinazioni possibili e può essere descritta dando una tabella, detta tabella di verità, con 2ⁿ righe.