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.

lezione
lezione
Logica matematica/Calcolo delle proposizioni
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Logica matematica

L'alfabeto

modifica

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 :  
  • Connettivi logici :  


Le formule

modifica

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è   e quelle del tipo  , 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 ( ) che rappresentano formule, ovvero elementi di FORM. A seconda dei casi,   può valere  , etcetera.

Definizione: Definizione di FORM

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

  •  
  • per ogni naturale i,  
  • se   allora  
  • se   allora  
  • se   allora  
  • se   allora  
  • se   allora  


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   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.   è vera
  2.   è vera per ogni naturale  
  3. se   è vera allora anche   è vera
  4. se   sono vere allora anche   è vera
  5. se   sono vere allora anche   è vera
  6. se   sono vere allora anche   è vera
  7. se   sono vere allora anche   è vera
allora la proprietà A vale per tutte le formule in FORM.


La dimostrazione di questo fondamentale teorema è tuttavia molto semplice: sia   un insieme di proposizioni ( e quindi  ) che rispetta tutte le condizioni del precedente teorema; dunque, immediatamente, rispetta tutte le condizioni della definizione di FORM, quindi  . 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  . Esiste un'unica funzione   tale che

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.