# 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.
* 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.
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.
Sia A una proprietà delle proposizioni. Se sono soddisfatte le seguenti condizioni
* $A(\bot )$ è vera
* $A(\phi _{i})$ è vera per ogni naturale $i$
* se $A(\phi )$ è vera allora anche $A((\neg \phi ))$ è vera
* se $A(\phi ){\mbox{ e }}A(\psi )$ sono vere allora anche $A((\phi \wedge \psi ))$ è vera
* se $A(\phi ){\mbox{ e }}A(\psi )$ sono vere allora anche $A((\phi \vee \psi ))$ è vera
* se $A(\phi ){\mbox{ e }}A(\psi )$ sono vere allora anche $A((\phi \rightarrow \psi ))$ è vera
* se $A(\phi ){\mbox{ e }}A(\psi )$ sono vere allora anche $A((\phi \leftrightarrow \psi ))$ è vera
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:
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
* $F(\bot )=f_{at}(\bot )$
* $F(\phi _{i})=f_{at}(\phi _{i})$
* $F(\neg \phi )=f_{\neg }(F(\phi ))$
* $F(\phi \wedge \psi )=f_{\wedge }(F(\phi ),F(\psi ))$
* $F(\phi \vee \psi )=f_{\vee }(F(\phi ),F(\psi ))$
* $F(\phi \rightarrow \psi )=f_{\rightarrow }(F(\phi ),F(\psi ))$
* $F(\phi \leftrightarrow \psi )=f_{\leftrightarrow }(F(\phi ),F(\psi ))$