Si consideri la tavola di verità per $H=(p\lor q)\land (r\lor \neg p)\rarr(q\land r)$:
Si osserva che, nelle colonne corrispondenti alle variabili proposizionali, sono presenti tutte le possibili triple di valori booleani (cioè in $\{0, 1\}$). Questa tabella definisce allora una corrispondenza che associa a ciascuna delle possibili triple di valori booleani, $\{0, 1\}$, il valore (anch’esso in $\{0, 1\}$) della formula $H$. Per evidenziare tale corrispondenza, è utile considerare solo le colonne “indispensabili” della tabella:
Perciò, la tabella può essere in1terpretata come la rappresentazione tabellare di una funzione $f:\{0, 1\}\rarr \{0, 1\}$, che associa a ogni tripla di valori booleani $\lang b_1, b_2, b_3\rang$ un valore booleano $f(b_1, b_2, b_3)$:
In generale, una funzione
$$ f:\{0, 1\} \rarr\{0, 1\} \ \ \ \ n\geq 1 $$
è detta funzione booleana.
La procedura appena vista fornisce un modo per associare una funzione booleana a una formula.
Data una formula $H$, con $\text{Var}(H)=\{p_1, ..., p_n\}$, la funzione booleana associata ad $H$ è la funzione
$$ f_H:\{0, 1\}^n\rarr\{0, 1\} $$
i cui valori sono definiti dalle possibili valutazioni di $H$: per ognuna delle n-uple booleane $\lang b_1, ..., b_n\rang\in \{0, 1\}^n$, si costruisce una valutazione $v$ che assegna alle variabili di $H$ i valori di tale n-upla,
$$ v(q)=\begin{cases} b_i &\text{se }q=p_i \\ 0 &\text{altrimenti} \end{cases} $$
e si pone
$$ f_H(b_1, ..., b_n)=v(H) $$
Ad esempio, tornando a considerare la formula