Leggi generalizzate di De Morgan e distributive

Leggi per un numero qualsiasi di termini

La lezione su conseguenza ed equivalenza semantica ha stabilito le leggi di equivalenza per due termini: tra esse, la commutatività e l’associatività di $\wedge$ e di $\vee$, le leggi di De Morgan e le due distributività. Ora, una formula in forma normale disgiuntiva è una disgiunzione di congiunzioni, ciascuna con tanti termini quanti ne servono, e trasformare una formula in quella forma richiede di negare, raggruppare diversamente e distribuire congiunzioni e disgiunzioni di lunghezza qualsiasi. Se è così, le leggi binarie non bastano così come sono: occorre estenderle a $n$ termini, e farlo una volta per tutte per tutti gli $n$.

Per ogni $n$ fissato, la legge di De Morgan di $n$ termini potrebbe essere verificata con una tavola di verità di $2^n$ righe, scritta con $n$ variabili, e la sostituzione uniforme della lezione precedente, applicata alla doppia implicazione tra i due lati, la estenderebbe a formule qualsiasi. Ma i valori di $n$ sono infiniti, e nessuna quantità di tavole li esaurisce. Ne segue che l’affermazione «per ogni $n$» non è un’equivalenza tra due formule, ma un enunciato su infinite equivalenze, formulato nel metalinguaggio; la sua dimostrazione è, come quelle della lezione sull’induzione sui numeri naturali e sulle formule, una dimostrazione esterna, e il suo strumento è l’induzione sul numero dei termini. Anche la notazione $\bigwedge_{i=1}^{n} \varphi_i$ appartiene al metalinguaggio: non è un nuovo simbolo della lingua, ma un nome per una stringa di cerchi e dischi, così come lo è $(\varphi \wedge \psi)$.

Conviene fissare fin d’ora tre relazioni che non vanno confuse. L’uguaglianza $\alpha = \beta$ dice che $\alpha$ e $\beta$ sono la stessa stringa; le definizioni, che si scrivono con $:=$, introducono nomi per stringhe, e ciò che si ottiene sviluppando una definizione è uguale, non soltanto equivalente. L’equivalenza semantica $\alpha \eqsem \beta$ dice che $v(\alpha) = v(\beta)$ per ogni assegnazione $v$. L’equivalenza dimostrabile $\alpha \dashv\vdash \beta$ dell’unità sulla deduzione dice che ciascuna si deduce dall’altra. Questa lezione lavora con le prime due; la terza compare solo in un’osservazione.

Ciò che si usa

Dalla lezione sulla semantica della logica proposizionale si prendono le assegnazioni, funzioni dalle variabili $v_1, v_2, \ldots$ in $\{0, 1\}$, e la loro estensione a tutte le formule, che si scrive con la stessa lettera $v$; il valore dei connettivi derivati, calcolato a partire dalle abbreviazioni ufficiali: $v(\neg\varphi) = 1 - v(\varphi)$, $v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi)$, sicché la congiunzione vale $1$ se e solo se valgono $1$ i suoi due componenti, e $v((\varphi \vee \psi)) = 1$ se e solo se $v(\varphi) = 1$ o $v(\psi) = 1$; il lemma di coincidenza (se due assegnazioni coincidono sulle variabili di una formula, coincidono sulla formula); e le formule $\top$ e $\bot$, una tautologia e una contraddizione fissate. Dalla lezione su conseguenza ed equivalenza semantica si prendono il fatto che $\eqsem$ è riflessiva, simmetrica e transitiva, il teorema di sostituzione semantica e il catalogo delle leggi con i loro nomi: commutatività, $(\varphi \wedge \psi) \eqsem (\psi \wedge \varphi)$ e $(\varphi \vee \psi) \eqsem (\psi \vee \varphi)$; associatività, $(\varphi \wedge (\psi \wedge \chi)) \eqsem ((\varphi \wedge \psi) \wedge \chi)$ e la sua analoga per $\vee$; De Morgan, $\neg(\varphi \wedge \psi) \eqsem (\neg\varphi \vee \neg\psi)$ e $\neg(\varphi \vee \psi) \eqsem (\neg\varphi \wedge \neg\psi)$; distributività, $(\varphi \wedge (\psi \vee \chi)) \eqsem ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$ e $(\varphi \vee (\psi \wedge \chi)) \eqsem ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$; doppia negazione, $\neg\neg\varphi \eqsem \varphi$; idempotenza, $(\varphi \vee \varphi) \eqsem \varphi$; identità, $(\varphi \wedge \top) \eqsem \varphi$; e terzo escluso, $\models (\varphi \vee \neg\varphi)$. Le leggi valgono per formule qualsiasi $\varphi$, $\psi$, $\chi$, che sono metavariabili.

A ogni passo delle dimostrazioni che seguono si sostituisce una parte di una formula con un’altra equivalente. Il teorema di sostituzione semantica lo autorizza per un’occorrenza alla volta; il lemma seguente, che ne è un caso particolare, lo dà in una volta sola per le parti di una negazione, di una congiunzione o di una disgiunzione. Va osservato che non è una banalità sintattica: $\neg\alpha$ è la stringa $(\alpha \downarrow \alpha)$, in cui $\alpha$ compare due volte, e $(\alpha \wedge \beta)$ contiene quindi otto occorrenze di $\alpha$ e otto di $\beta$.