Le funzioni booleane

Le funzioni booleane sono una parte fondamentale della matematica discreta e dell’informatica. Sono utilizzate per descrivere relazioni logiche tra variabili booleane, ovvero variabili che possono assumere solo due valori: vero o falso (o 1 o 0). In questo post esploreremo le caratteristiche delle funzioni booleane, come rappresentarle e proporremo alcuni esercizi per praticare il loro uso.

Caratteristiche delle funzioni booleane

Le funzioni booleane sono una generalizzazione delle operazioni logiche tra due variabili booleane (AND, OR e NOT) a un numero qualsiasi di variabili. Si tratta quindi di funzioni del tipo

f : B^n\mapsto B

con $B=\{0,1\}$ lo spazio booleano. Queste funzioni hanno alcune proprietà fondamentali che le rendono utili in molti contesti:

Sono non-lineari: le funzioni booleanhe possono avere relazioni complesse tra le loro variabili, il che le rende adatte per rappresentare problemi complessi.
Hanno un dominio e un range finiti: poiché le variabili booleane possono assumere solo due valori, la funzione booleana avrà un numero finito di possibili input e output. Ciò li rende facili da elaborare con algoritmi e circuiti digitali.
Sono commutative: l’ordine delle variabili in una funzione booleana non influisce sul risultato finale. Ad esempio, la funzione AND tra le variabili A e B è la stessa della funzione AND tra B e A.

Una operazione importante che si può realizzare data la definizione di una funzione booleana è quella di procedere alla sua semplificazione, utilizzando le regole dell’Algebra di Boole.

Rappresentazione delle funzioni booleane

Le funzioni booleane possono essere rappresentate in diversi modi

Tabella di verità

Una tabella che mostra tutti i possibili valori di input e il corrispondente valore di output. Ad esempio, la tabella di verità per la funzione AND tra due variabili A e B è:

A	B	A AND B
0	1	0
1	0	0
1	1	1
0	0	0

Espressione algebraica

Una rappresentazione più compatta della funzione booleana, che utilizza le operazioni logiche AND, OR e NOT per descrivere la relazione tra le variabili. Ad esempio, l’espressione algebraica per la funzione AND tra due variabili A e B è A AND B.