Il Calcolo Proposizionale secondo Douglas Hofstadter

giovedì, Maggio 27th, 2021

Calcolo Proposizionale,Douglas Hofstadter,sistema formale

Introduzione

Il Calcolo Proposizionale secondo Douglas Hofstadter è un particolare sistema formale privo di assiomi (vedremo a breve come inizializzare il processo per la dimostrazione dei teoremi). Naturalmente abbiamo un alfabeto di simboli e un insieme di regole. Di seguito i simboli:

Definizione
Le stringhe ben formate sono tutte e sole le stringhe che danno luogo a enunciati semanticamente corretti. Ad esempio, i teoremi derivanti dagli assiomi di un qualunque sistema formale sono stringhe ben formate.

Definizione
Nell'alfabeto dei simboli, P,Q,R sono gli atomi del Calcolo Proposizionale. Naturalmente possono essere utilizzate altre lettere eventualmente dotate di apici. Gli atomi sono stringhe ben formate.

Passiamo alle regole.
Regola di Congiunzione. Se x e y sono teoremi del Calcolo Proposizionale, allora la stringa

è un teorema.
Abbiamo poi le seguenti regole che possono essere applicate ricorsivamente:
Regole di Formazione. Se x e y sono stringhe ben formate, allora sono ben formate le stringhe:

Altre regole:
Regola di Separazione. Assegnate le stringhe ben formate x e y, se

è un teorema, allora x e y sono teoremi.
Regola del doppio gancio. La stringa

può essere cancellata quando compare in un teorema.

Avevamo detto che il Calcolo Proposizionale è un sistema formale privo di assiomi. Nonostante ciò, i teoremi vengono dimostrati utilizzando la cosiddetta Regola di fantasia. Si parte da una stringa ben formata x scelta ad arbitrio. Si procede quindi per derivazione applicando le regole precedenti. Denotiamo con y l'ultima riga del processo di derivazione. Hofstadter chiama fantasia tutto ciò che si trova tra x e y (inclusi). Precisamente, x è la premessa della fantasia, mentre y ne è la conclusione. La fantasia mostra che:

Indipendentemente da ciò, la stringa ben formata

è un teorema. Per segnalare l'entrata in una fantasia ("push" in una fantasia) si utilizza la parentesi quadra [, mentre l'uscita ("pop" della fantasia) è simboleggiata da ]. Ad esempio, utilizziamo come stringa di partenza l'atomo P. Si noti che non è un teorema, ma ciò non ha importanza, nel senso che poi ci chiediamo: "che cosa succederebbe se lo fosse?".

La fantasia mostra che

In altri termini, solo quest'ultima riga è un teorema. Tutto il resto è fantasia.

Ricorsività della fantasia

Il lettore attento avrà intuito la natura ricorsiva della regola di fantasia. Possiamo quindi implementare fantasie dentro fantasie, fantasie con ricorsione n-pla, etc. Ciò implica l'esistenza di svariati «livelli di realtà» esattamente come nei film con altri film annidati. Quando si esegue un'uscita (pop) da un film-in-un-film, sembra per un momento di aver raggiunto il mondo reale, anche se ci si trova sotto di un piano rispetto al livello più alto. Allo stesso modo, quando si esce da un pop da una fantasia-in-una-fantasia, ci si trova in un mondo «più reale» del precedente, ma non ancora al livello più alto. A tal fine, abbiamo la seguente regola:

Regola del trasferimento. All'interno di una fantasia si può inserire e usare qualsiasi teorema appartenente alla «realtà» del livello immediatamente superiore.

Metaforicamente, è come se un cartello «Vietato fumare» in una sala cinematografica riguardasse non solo tutti gli spettatori, ma anche tutti gli attori del film e, iterando, la stessa idea, riguardasse anche i personaggi dei film annidati all'interno del film proiettato (con l'avvertenza che non è possibile invertire il percorso).

Il significato dei simboli

Dagli esempi risulta chiaro che secondo il linguaggio naturale, il simbolo

sta per "e", mentre

sta per "o". Il gancio, invece, esprime una negazione. Le parantesi angolari svolgono un ruolo simile alle parentesi dell'algebra ordinaria. Riguardo agli atomi, questi vengono interpretati alla stregua di un enunciato utilizzando il linguaggio naturale. In fig. alcuni esempi suggestivi:

Posted in Logica Matematica | No Comments »

[¯|¯] Una partita al gioco MU

lunedì, Febbraio 11th, 2019

gioco mu,sistema formale,douglas hofstadter

Douglas Hofstadter nel suo besmoretseller Gödel, Escher, Bach: un'eterna ghirlanda brillante propone un gioco molto istruttivo il cui scopo è quello di illustrare il concetto di sistema formale.

Ecco di cosa si tratta.

Siamo abituati a vedere i teoremi come enunciati dimostrabili attraverso una successione finita di argomentazioni logiche. Tuttavia nel paradigma dei sistemi formali, i teoremi altro non sono che il risultato della "composizione" di un numero finito di assiomi, rispettando una serie di regole, e partendo da un "alfabeto di simboli". Il gioco MU è un sistema formale, in cui l'unico assioma è la stringa MI, mentre l'alfabeto è composto dalle lettere M, I, U. Hofstadter chiama sistema MIU il predetto sistema formale, le cui regole sono:

Regola 1
A una qualunque stringa che termina con una I, si può aggiungere una U alla fine.
Esempio: la stringa MI può diventare MIU, ma la stringa IM non può diventare IMU, giacchè le stringhe sono set ordinati di simboli.
(altro…)