Completezza funzionale

Funzioni di verità

La lezione sulla semantica della logica proposizionale ha attribuito a ogni formula, in ogni assegnazione, un valore di verità, e ha mostrato che tale valore dipende solo dai valori delle variabili che vi compaiono; donde ogni formula con $n$ variabili ha una tavola di verità di $2^{n}$ righe. La domanda di questa lezione è quella inversa. Data una tavola qualsiasi, cioè una colonna di uni e zeri scritta arbitrariamente accanto alle $2^{n}$ righe, esiste una formula che l’abbia come tavola? Se è così per ogni tavola, il linguaggio non ha lacune espressive: tutto ciò che si può dire sul valore di verità di $n$ enunciati, in funzione dei loro valori, si dice con una formula. E poiché in questo corso ogni formula composta è una negazione congiunta, la risposta dirà anche se un solo connettivo basta per dire tutto.

Ciò che si usa dalle lezioni precedenti

Un’assegnazione è una funzione $v$ dall’insieme delle variabili $\{v_1, v_2, \ldots\}$ in $\{0, 1\}$, dove $1$ è il vero e $0$ il falso; la sua estensione a tutte le formule, che si scrive anch’essa $v$, è definita per ricorsione: $v((\varphi \downarrow \psi)) = 1$ se e solo se $v(\varphi) = 0$ e $v(\psi) = 0$. Dalle abbreviazioni ufficiali, la stessa lezione ha calcolato, nel teorema dei valori dei connettivi derivati, il valore di ogni connettivo; scritti con somme e prodotti, sono i seguenti, per ogni assegnazione $v$ e tutte le formule $\varphi$ e $\psi$:

Inoltre, $v((\varphi \leftrightarrow \psi)) = v(\varphi)\,v(\psi) + (1 - v(\varphi))\,(1 - v(\psi))$, che vale $1$ se e solo se $v(\varphi) = v(\psi)$, e $v((\varphi \veebar \psi)) = v(\varphi) + v(\psi) - 2\,v(\varphi)\,v(\psi)$, che vale $1$ se e solo se $v(\varphi) \neq v(\psi)$. Poiché i valori sono $0$ o $1$, il quadrato di un valore è il valore stesso, $v(\varphi)\,v(\varphi) = v(\varphi)$, e un prodotto di valori vale $1$ se e solo se ogni fattore vale $1$; entrambe le osservazioni si useranno senza ripeterle. Si usa anche il lemma di coincidenza: se due assegnazioni coincidono sulle variabili di $\varphi$, cioè sulle variabili che sono sottoformule di $\varphi$, danno a $\varphi$ lo stesso valore. Dalla lezione su conseguenza ed equivalenza semantica si prende l’equivalenza semantica: $\varphi \eqsem \psi$ quando $v(\varphi) = v(\psi)$ per ogni assegnazione $v$. Infine, vale la convenzione delle lettere della lezione sulla formalizzazione: $p$, $q$ e $r$ designano le variabili $v_1$, $v_2$ e $v_3$.

Le funzioni di verità e il loro numero

Sia $n$ un numero naturale. Una riga di $n$ valori è una successione $a = (a_1, \ldots, a_n)$ in cui ogni $a_i$ è $0$ o $1$; l’insieme di tutte le righe si denota $\{0, 1\}^{n}$. Una funzione di verità di $n$ argomenti è una funzione

che assegna a ogni riga un valore di verità. Si presenta come una tavola: le righe si scrivono nell’ordine della tavola, a partire da quella in cui tutti i valori sono $1$ (per due argomenti, $1\,1$, $1\,0$, $0\,1$, $0\,0$), e accanto a ogni riga si scrive il suo valore. Una funzione di verità è dunque una tavola di verità senza formula: la colonna di destra, senza nulla scritto nella sua intestazione.

Formule che rappresentano funzioni

Una formula e una funzione di verità si collegano nel modo seguente. Se $\varphi$ è una formula le cui variabili sono tra $v_1, \ldots, v_n$, si dice che $\varphi$ rappresenta la funzione di verità $f$ di $n$ argomenti quando, per ogni assegnazione $v$,

cioè quando la tavola di $\varphi$, scritta con le variabili $v_1, \ldots, v_n$, è la tavola di $f$. La condizione sulle variabili non è un dettaglio: la formula $(p \wedge q)$ non rappresenta nessuna funzione di un argomento, perché il suo valore non dipende solo da quello di $p$.

Ci sono infinite formule con variabili tra $v_1, \ldots, v_n$ e solo $2^{2^{n}}$ funzioni; quindi molte formule rappresentano la stessa funzione, e la proposizione dice che sono esattamente quelle equivalenti tra loro. Resta da sapere se ogni funzione è rappresentata da qualche formula, o se alcune tavole restano senza una formula che le abbia.