Funzioni Booleane e Tabelle di verità

Una Funzione Booleane è una semplice “relazione” che definisce un’uscita (output) per ogni possibile combinazione di ingressi (input).

Definizione formale di Funzione Booleana

$f:A^n↦A$ Quella soprastante è una funzione booleana $f$ dove $A^n$ è il dominio e $A$ è il codominio. Poiché il nostro contesto è l’Algebra di Commutazione, l’insieme $A$ è sempre e solo $\{0, 1\}$, quindi la nostra definizione diventa: $f : \{0, 1\}^n ↦ \{0, 1\}$ In un linguaggio più semplice: Una funzione booleana prende $n$ variabili (che possono essere $0$ o $1$) e restituisce un singolo valore ($0$ o $1$).

Tabelle di verità

Il modo più semplice e completo per descrivere una funzione booleana è attraverso la sua tabella di verità.

Una Tabella di verità:

• Ha $n$ colonne per gli ingressi/input (dominio).
• Ha una colonna per l’uscita/output (codominio).
• Ha $2^n$ righe, per rappresentare ogni singola configurazione possibile degli ingressi.

Esempio:

• Funzione: $f(x, y, z)$
  • Gli ingressi sono 3 ($x, y, z$), quindi la tabella di verità ha 3 colonne, quindi $n = 3$.
  • Essendo $n=3$ allora le righe saranno $2^3$, ossia 8, quindi la tabella avrà 8 righe.
• La funzione restituisce in output $1$ solo se 2 variabili qualsiasi valgono $1$.

Ma quindi alla fine quante combinazioni di funzioni esistono?

Per spiegarlo rendendolo comprensibile in modo semplice e veloce, è possibile ricorrere alle tabelle di verità come analogia per le funzioni booleane.

1. In una tabella di verità ci sono $2^n$ righe (possibili configurazioni di input)
2. Per ogni riga, l’output $f$ può essere $0$ oppure $1$ (2 possibilità).

Quindi possiamo dedurre che il numero totale di output (funzioni $f$) sia 2 elevato al numero di righe/input ($2^n$).

Quindi il numero totale di possibili funzioni booleane con $n$ variabili di ingresso/input, sia $(2^2)^n$.

Esempio:

Con una sola variabile $x$ di ingresso ($n=1$), ci sono $(2^2)^n = 2^2 = 4$ funzioni possibili:

• Costante $0$: $f(x) = 0$ <— Dove l’output è sempre 0.
• Proiezione dell’input: $f(x) = x$ <— Dove l’output è la copia dell’input.
• Negazione dell’input: $f(x) = x^{\prime}$ <— Dove l’output è la negazione dell’input.
• Costante $1$: $f(x) = 1$ <— Dove l’output è sempre 1.

Funzioni non completamente specificate:

Immagina una tabella di verità dove per alcune righe, l’output è indifferente. Questi casi vengono segnati con una X o con un -.

Perché? 2 motivi:

1. Impossibile: La combinazione di input non può capitare.
2. Irrilevante: Non ci interessa cosa succede in quel caso.

Noi possiamo trarre un vantaggio in questi casi: Quando andiamo a semplificare la formula della funzione, possiamo trattare l’output di una funzione non completamente specificata come $0$ o $1$, a seconda di quale dei due riteniamo più di nostro aiuto nella semplificazione dell’espressione booleana.

Esempio:

• $f(x_1, x_2)$
  • Assume valore $1$ se $x_1 = 0$ e $x_2 = 0$.
  • Assume valore $0$ se le variabili sono diverse ($x_1 \neq x_2$).

Ehh fratè, si tu che stai leggendo, non ti accorgi che manca qualcosa? E se $x_1 = 1$ e $x_2 = 1$? <--- Eccoci al caso mancante.

Tabella di verità:

Continua con… Le Espressioni Booleane.