Funzione booleana

funzione di dominio {0,1}^k per qualche k e codominio {0,1}

In matematica e in informatica, una funzione booleana a variabili è una funzione:

di variabili booleane che assumono valori nello spazio booleano , così come stessa. Con un insieme di 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. Poiché le variabili possono assumere solo i valori 0 o 1, una funzione booleana con variabili di input ha solo combinazioni possibili e può essere descritta attraverso una tabella, detta tabella di verità, con righe.

Espressioni Booleane: definizioni

modifica

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:

 

Questa è una clausola o termine elementare formato da tre letterali. Oppure possiamo avere dei fattori elementari che nel prossimo esempio sono messi in AND:

 

Una funzione di tre variabili     e   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.

 
 

la prima formula rappresenta la forma P, la seconda rappresenta la forma S

Le funzioni booleane elementari

modifica

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,  ), 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   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

modifica

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

 

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   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
Controllo di autoritàGND (DE4146281-6
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica