Forme normali

Nelle lezioni precedenti di questa unità si è dato significato alle formule: la lezione sulla semantica della logica proposizionale ha esteso ogni assegnazione a tutte le formule; la lezione su conseguenza ed equivalenza semantica ha definito l’equivalenza $\varphi \eqsem \psi$ e ha dimostrato la sostituzione semantica; la lezione sulle leggi generalizzate di De Morgan e distributive ha esteso quelle leggi a congiunzioni e disgiunzioni di $n$ formule; e la lezione sulla completezza funzionale ha mostrato che ogni funzione di verità è rappresentata da qualche formula. Ora, una funzione di verità è rappresentata da infinite formule, che possono essere molto diverse tra loro: $(v_1 \rightarrow v_2)$, $\neg(v_1 \wedge \neg v_2)$ e $(((v_1 \downarrow v_1) \downarrow v_2) \downarrow ((v_1 \downarrow v_1) \downarrow v_2))$ sono tre nomi della stessa cosa. Se è così, conviene scegliere in ogni classe di equivalenza un rappresentante di forma fissa, che si legga senza sforzo e con il quale certe domande trovino risposta guardando. Questo sono le forme normali.

Letterali, clausole e forme normali

Si ricordi, dalla lezione sulle leggi generalizzate, la notazione della congiunzione e della disgiunzione di $n$ formule, definita per ricorsione e associando a sinistra; quella di una sola formula è la formula stessa.

Nella stessa lezione si è dimostrato che l’ordine e il raggruppamento dei termini non alterano la formula a meno di equivalenza (associatività generalizzata e indipendenza dall’ordine e dalle ripetizioni); per questo scriveremo anche $\varphi_1 \wedge \varphi_2 \wedge \cdots \wedge \varphi_n$ senza parentesi, intendendo il raggruppamento a sinistra.

Un letterale è una variabile $v_n$, che si chiama letterale positivo, o la negazione $\neg v_n$ di una variabile, che si chiama letterale negativo. L’opposto di un letterale $\ell$, che scriviamo $\ell^{*}$, è il letterale della stessa variabile e dell’altro segno:

Dalla definizione segue che $(\ell^{*})^{*} = \ell$. Due letterali formano una coppia complementare se l’uno è l’opposto dell’altro, come $v_3$ e $\neg v_3$.

Una clausola è una disgiunzione di letterali, $\bigvee_{j=1}^{k} \ell_j$, e una congiunzione elementare è una congiunzione di letterali, $\bigwedge_{j=1}^{k} \ell_j$, con $k \geq 1$ in entrambi i casi; un letterale da solo è quindi allo stesso tempo una clausola e una congiunzione elementare. Si dice che un letterale sta in una clausola o in una congiunzione elementare se è uno dei suoi $\ell_j$.

Una formula è in forma normale disgiuntiva se è una disgiunzione di congiunzioni elementari, e in forma normale congiuntiva se è una congiunzione di clausole; cioè, se è, rispettivamente, di una delle due forme seguenti, dove $m$ e $k_1, \ldots, k_m$ sono numeri naturali e ogni $\ell_{i,j}$ è un letterale:

Diremo che $\Phi$ è una forma normale disgiuntiva di $\varphi$ se è in forma normale disgiuntiva e $\varphi \eqsem \Phi$, e lo stesso per la congiuntiva. Le lunghezze $k_i$ possono variare da una congiunzione (o clausola) all’altra: esigere lo stesso numero di letterali in tutte obbligherebbe a riempire con ripetizioni e non aggiungerebbe nulla.

Conviene soffermarsi su che cosa significhi «essere in forma normale». È una proprietà della stringa di cerchi e dischi, non del suo significato: la lezione sull’induzione sui numeri naturali e sulle formule ha dimostrato la leggibilità unica, di modo che chiedere se una formula è una disgiunzione, e di che cosa, ha una sola risposta. Ora, le abbreviazioni ufficiali fanno sì che alcune formule siano in forma normale senza sembrarlo. L’implicazione $(v_1 \rightarrow v_2)$ si definisce come $(\neg v_1 \vee v_2)$: non è che equivalga a quella clausola, ma è quella stessa stringa, e perciò è già in forma normale. Più sorprendente è la doppia negazione. Per le definizioni di $\neg$ e di $\vee$, la stringa $(\varphi \vee \varphi)$ è $\neg(\varphi \downarrow \varphi)$, cioè $\neg\neg\varphi$; quindi $\neg\neg v_1$ non è un letterale, ma è, simbolo per simbolo, la clausola $(v_1 \vee v_1)$.

Il valore delle congiunzioni e delle disgiunzioni

Dalla lezione sulla semantica si prendono i valori dei connettivi derivati: $v(\neg\varphi) = 1 - v(\varphi)$; $v(\varphi \wedge \psi) = v(\varphi)\,v(\psi)$, che vale $1$ se e solo se entrambe valgono $1$; e $v(\varphi \vee \psi) = 0$ se e solo se entrambe valgono $0$. La lezione sulle leggi generalizzate di De Morgan e distributive li ha estesi a $n$ formule, per induzione sul numero dei termini, nel lemma del valore: per ogni assegnazione $v$, la congiunzione $\bigwedge_{i=1}^{n} \varphi_i$ vale $1$ in $v$ se e solo se ogni $\varphi_i$ vale $1$ in $v$, e la disgiunzione $\bigvee_{i=1}^{n} \varphi_i$ vale $1$ in $v$ se e solo se qualche $\varphi_i$ vale $1$ in $v$. Questo lemma, che qui si cita senza ripeterne la dimostrazione, è lo strumento con cui si calcola il valore di qualsiasi forma normale.

Il secondo caso è facile da trascurare: negando una forma normale si tende a scrivere $\neg\ell_{i,j}$ invece di un letterale, e $\neg\neg v_n$ non lo è. È la doppia negazione a riportare il risultato nello stampo.