Logica matematica/Calcolo delle proposizioni

Lo studio della logica matematica parte da una semplificazione della logica stessa: il calcolo delle proposizioni. In questo contesto non vengono analizzati oggetti e proprietà di questi: si considerano solo proposizioni; non osservando l'interno di una proposizione, cioè come minimo soggetto e predicato, una proposizione ha solo la caratteristica di essere vera o falsa (anche se non si può scegliere tra una di queste due possibilità e bisogna considerare entrambi i casi). Viceversa, anche senza conoscere una proposizione, possiamo collegarla ad altre proposizioni mediante congiunzioni logiche, e studiare il significato di questa proposizione composta.

L'alfabeto

Come ogni linguaggio formale, il calcolo delle proposizioni si basa su un alfabeto. Di esso fanno parte delle variabili per rappresentare le proposizioni, e alcuni "segni di punteggiatura" per costruire le proposizioni composte.

Definizione: Definizione dell'alfabeto proposizionale

• Una quantità numerabile di variabili, distinte dal pedice : $\phi _{1},\phi _{2},\dots \phi _{n}\dots$
• Connettivi logici : $\wedge \quad \vee \quad \rightarrow \quad \leftrightarrow \quad \neg \quad (\quad )\quad \bot$

Le formule

I simboli dell'alfabeto prima definito si possono accostare per giustapposizione; tuttavia solo alcune combinazioni hanno significato per la logica. Queste sequenze significative si chiamano formule, e sono definite ricorsivamente. Questo significa che ci sono alcune formule di base, cioè $\bot$ e quelle del tipo $\phi _{i}$, e che a partire da queste si costruiscono altre formule complesse, secondo alcune regole. Nella definizione dell'insieme delle formule, FORM, compaiono alcuni simboli che non fanno parte dell'alfabeto delle proposizioni: sono quelli della comune pratica matematica e fanno parte, assieme al linguaggio naturale, del metalinguaggio ovvero del linguaggio che si utilizza per descrivere il linguaggio formale. Tra questi simboli del metalinguaggio ci sono variabili ($\phi ,\psi ,\chi ,\eta ,...$) che rappresentano formule, ovvero elementi di FORM. A seconda dei casi, $\phi$ può valere $\bot ,\phi _{6},((\phi _{2}\wedge \phi _{7})\rightarrow \bot )$, etcetera.

Definizione: Definizione di FORM

L'insieme FORM delle formule è il più piccolo insieme X tale che

• $\bot \in X$
• per ogni naturale i, $\phi _{i}\in X$
• se $\phi \in X$ allora $(\neg \phi )\in X$
• se $\phi ,\psi \in X$ allora $(\phi \wedge \psi )\in X$
• se $\phi ,\psi \in X$ allora $(\phi \vee \psi )\in X$
• se $\phi ,\psi \in X$ allora $(\phi \rightarrow \psi )\in X$
• se $\phi ,\psi \in X$ allora $(\phi \leftrightarrow \psi )\in X$

Per precisare la definizione precedente, per più piccolo si intende chiaramente che l'insieme FORM è l'intersezione di tutti gli insiemi che rispettano le clausole dell'elenco successivo. La definizione sarebbe problematica se non esistesse nessun insieme che rispetta tutte le clausole. Ma uno almeno esiste, ed è l'insieme di tutte le possibili stringhe di simboli dell'alfabeto che possiamo ottenere per giustapposizione; certo è un insieme vasto (anche se numerabile) pieno di cose inutili. D'altro canto l'intersezione di tutti questi insiemi è non vuota, perché l'elemento $\bot$ appartiene sicuramente a tutti gli insiemi dell'elenco, quindi appartiene anche all'intersezione. Con ragionamenti analoghi sappiamo che all'intersezione appartengono anche tante altre formule (ed è chiaro che sono tutte e sole le formule di lunghezza finita che possiamo ottenere per costruzione).

Su questa definizione, e apparentemente senza assiomi, si dimostra un teorema fondamentale, che prende il nome onorifico di principio di induzione sulle proposizioni.

Teorema: Principio di induzione su FORM

Sia A una proprietà delle proposizioni. Se sono soddisfatte le seguenti condizioni

1. $A(\bot )$ è vera
2. $A(\phi _{i})$ è vera per ogni naturale $i$
3. se $A(\phi )$ è vera allora anche $A((\neg \phi ))$ è vera
4. se $A(\phi ){\mbox{ e }}A(\psi )$ sono vere allora anche $A((\phi \wedge \psi ))$ è vera
5. se $A(\phi ){\mbox{ e }}A(\psi )$ sono vere allora anche $A((\phi \vee \psi ))$ è vera
6. se $A(\phi ){\mbox{ e }}A(\psi )$ sono vere allora anche $A((\phi \rightarrow \psi ))$ è vera
7. se $A(\phi ){\mbox{ e }}A(\psi )$ sono vere allora anche $A((\phi \leftrightarrow \psi ))$ è vera

allora la proprietà A vale per tutte le formule in FORM.

La dimostrazione di questo fondamentale teorema è tuttavia molto semplice: sia $Y=\{\phi \in FORM\mid A(\phi ){\mbox{ è vera }}\}$ un insieme di proposizioni ( e quindi $Y\subseteq FORM$) che rispetta tutte le condizioni del precedente teorema; dunque, immediatamente, rispetta tutte le condizioni della definizione di FORM, quindi $FORM\subseteq Y$. Dalle due inclusioni, l'uguaglianza.

Un altro teorema fondamentale, basato sulla definizione di FORM che permette di definire funzioni ricorsivamente (garantendo la buona definizione) è il seguente:

Teorema: Definizioni ricorsive su FORM

Siano definite le funzioni $f_{at}:\{\bot ,\phi _{1},\phi _{2},\ldots \}\rightarrow A,f_{\neg }:A\rightarrow A,f_{\wedge }:A^{2}\rightarrow A,f_{\vee }:A^{2}\rightarrow A,f_{\rightarrow }:A^{2}\rightarrow A,f_{\leftrightarrow }:A^{2}\rightarrow A$. Esiste un'unica funzione $F:FORM\rightarrow A$ tale che

1. $F(\bot )=f_{at}(\bot )$
2. $F(\phi _{i})=f_{at}(\phi _{i})$
3. $F(\neg \phi )=f_{\neg }(F(\phi ))$
4. $F(\phi \wedge \psi )=f_{\wedge }(F(\phi ),F(\psi ))$
5. $F(\phi \vee \psi )=f_{\vee }(F(\phi ),F(\psi ))$
6. $F(\phi \rightarrow \psi )=f_{\rightarrow }(F(\phi ),F(\psi ))$
7. $F(\phi \leftrightarrow \psi )=f_{\leftrightarrow }(F(\phi ),F(\psi ))$