Conseguenza ed equivalenza semantica

Ciò che si usa della lezione precedente

La lezione sulla semantica della logica proposizionale ha dato significato alle formule, e questa lezione lo dà per acquisito. Un’assegnazione è una funzione $v\colon V \to \{0, 1\}$, che attribuisce a ogni variabile un valore di verità, $1$ (vero) o $0$ (falso). Per il teorema di definizione per ricorsione sulle formule, della lezione sull’induzione, ogni assegnazione si estende in un unico modo a tutte le formule mediante la clausola della negazione congiunta, l’unica necessaria, perché la lingua ha un solo connettivo:

Per l’unicità dell’estensione, si scrive $v(\varphi)$ anche per il valore dell’estensione; la lettera $v$ senza indice designa sempre un’assegnazione (e $v'$, $w$, $u$, altre), mentre le variabili portano sempre il loro indice. Come nella lezione sulla formalizzazione, $p$, $q$, $r$, $s$ e $t$ nominano le variabili da $v_1$ a $v_5$, e $V(\varphi)$ è l’insieme delle variabili di $\varphi$. Si dice che $v$ soddisfa $\varphi$, e si scrive $v \models \varphi$, quando $v(\varphi) = 1$, e che la falsifica, $v \not\models \varphi$, quando $v(\varphi) = 0$. Una formula è valida (o tautologia), e si scrive $\models \varphi$, se ogni assegnazione la soddisfa; soddisfacibile, se qualche assegnazione la soddisfa; insoddisfacibile (o contraddizione), se nessuna la soddisfa; contingente, se è soddisfacibile senza essere valida. Un’assegnazione soddisfa un insieme $\Gamma$ di formule, $v \models \Gamma$, quando soddisfa ciascuna di esse, e $\Gamma$ è soddisfacibile se qualche assegnazione lo soddisfa e insoddisfacibile in caso contrario. Infine, $\top := (v_1 \rightarrow v_1)$ e $\bot := \neg\top$, di modo che $v(\top) = 1$ e $v(\bot) = 0$ per ogni assegnazione.

Di quella lezione si usano inoltre due risultati. Il primo è il lemma di coincidenza: se due assegnazioni coincidono sulle variabili di $\varphi$, coincidono su $\varphi$; per esso, il valore di una formula con $n$ variabili dipende solo da $2^{n}$ combinazioni, e la sua tavola di verità è finita. Il secondo è il teorema dei valori dei connettivi derivati, che calcola a partire dalle abbreviazioni ufficiali il valore di ogni connettivo come un polinomio nei valori dei componenti. Se $a = v(\varphi)$ e $b = v(\psi)$:

Le dimostrazioni di questa lezione consistono, quasi tutte, nel confrontare valori di verità, e questi polinomi permettono di farlo con un calcolo invece che con un esame dei casi. La loro unica regola aggiuntiva è che $0$ e $1$ sono gli unici numeri che coincidono con il proprio quadrato: se $x$ vale $0$ o $1$, allora $x^{2} = x$ e $x(1 - x) = 0$. Conviene inoltre avere a portata di mano altre tre scritture degli stessi valori, che si ottengono svolgendo i prodotti:

La prima è la clausola della negazione congiunta (il prodotto di $1 - a$ e $1 - b$ vale $1$ esattamente quando $a = b = 0$); la seconda dice che la disgiunzione vale $0$ solo se entrambi i componenti valgono $0$; la terza, che la doppia implicazione vale $1$ se $a = b$ (perché $1 - 2a + 2a^{2} = 1$) e $0$ se $a \neq b$ (perché allora $a + b = 1$ e $ab = 0$).