Funzione booleana

Da Wikipedia, l'enciclopedia libera.

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.

Espressioni Booleane: definizioni[modifica | modifica sorgente]

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)=...+a \overline b \overline c +...

f(a,b,c)=...\cdot (a b \overline c) \cdot...

la precedente formula sembra essere sbagliata

Le funzioni Booleane Elementari[modifica | modifica sorgente]

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, 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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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