Funzioni booleane
Una funzione booleana è una funzione matematica $ f(x,y) $ che accetta come input uno o più valori booleani (vero o falso, rappresentati tipicamente come 1 e 0) e restituisce un output booleano.
Le funzioni booleane sono costruite utilizzando operazioni logiche come AND (congiunzione), OR (disgiunzione), NOT (negazione), XOR (disgiunzione esclusiva), tra gli altri.
Esempio
Per illustrare meglio, consideriamo una semplice funzione booleana:
$$ f(x, y) = x \land \neg y $$
Questa funzione è composta da diversi letterali, variabili e operatori logici:
- \( x \) e \( y \) sono le variabili di input.
- \( \land \) rappresenta l'operatore AND.
- \( \neg y \) rappresenta la negazione di \( y \).
Se \( x \) è vero e \( y \) è falso, la funzione booleana \( f(x, y) \) restituisce vero, perché vero AND vero è vero (1).
Se, invece, uno qualsiasi degli input è falso, l'output è falso (0).
Per rappresentare tutte le combinazioni possibili delle variabili \( x \) e \( y \) e gli output della funzione booleana $ f(x, y) = x \land \neg y $ possiamo costruire la tavola di verità.
$$
\begin{array}{cc|c}
x & y & \neg y & x \land \neg y \\
\hline
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
\end{array}
$$
Nella tavola di verità le colonne \( x \) e \( y \) rappresentano le variabili di input, mentre la colonna \( f(x, y) \) mostra il risultato dell'operazione \( x \land \neg y \).
Il valore nella colonna \( f(x, y) \) è determinato applicando prima l'operatore di negazione a \( y \), e poi l'operatore AND tra \( x \) e il risultato di \( \neg y \).
Le funzioni booleane sono fondamentali nella progettazione e nell'analisi dei circuiti logici digitali. Sono impiegate anche in informatica per costruire espressioni condizionali e controlli di flusso nei programmi.
La semplificazione di una funzione booleana
L'espressione logica che caratterizza una funzione booleana può essere semplificata applicando le leggi dell'algebra booleana.
La semplificazione riduce notevolmente la complessità delle funzioni e diminuisce il numero di calcoli necessari per determinare il risultato di una funzione booleana, migliorandone al contempo la leggibilità.
Esempio. Vediamo come semplificare una funzione booleana utilizzando le leggi dell'algebra booleana. Prendiamo come esempio la seguente espressione:
$$ f(x, y) = (x \land y) \lor (x \land \neg y) $$La proprietà distributiva dell'AND rispetto all'OR $ x \land (y \lor z) = (x \land y) \lor (x \land z) $ ci permette di fattorizzare fuori \( x \) dall'espressione, poiché \( x \) è comune in entrambi i termini:
$$ f(x, y) = x \land (y \lor \neg y) $$
Notiamo che \( y \lor \neg y \) è una tautologia, che significa che sarà sempre vero indipendentemente dal valore di \( y \), poiché una variabile OR il suo complemento copre tutte le possibilità: $ y \lor \neg y = 1 $
$$ f(x, y) = x \land 1 $$
Il valore 1 è l'elemento neutro dell'operatore AND. In questi casi il risultato è la variabile stessa: $ x \land 1 = x $ Quindi, la funzione semplificata è:
$$ f(x, y) = x $$
La funzione originale \( f(x, y) = (x \land y) \lor (x \land \neg y) \) è stata semplificata a \( f(x,y) = x \). Se costruiamo le tabelle di verità per entrambe le funzioni, osserveremo che si comportano allo stesso modo e restituiscono gli stessi risultati.
$$
\begin{array}{cc|c}
x & y & x \land y & x \land \neg y & (x \land y) \lor (x \land \neg y) & x \\
\hline
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 & 1 & 1\\
1 & 1 & 1 & 0 & 1 & 1\\
\end{array}
$$
Questo esempio dimostra come l'utilizzo delle proprietà dell'algebra booleana, come la distributività e la riconoscimento di tautologie, possa semplificare notevolmente le espressioni booleane. La semplificazione non solo riduce la complessità ma migliora anche l'efficienza dell'implementazione della funzione booleana in contesti pratici come la programmazione informatica e la progettazione di circuiti logici.
