204SM - LOGICA 2015

Schema della sezione

• Seleziona sezione Programma 2015/2016 e indicazioni circa l'esame

  Programma 2015/2016 e indicazioni circa l'esame

  Minimizza tutto Espandi tutto

  • Seleziona attività Forum News

    

    Forum News
  • Seleziona attività Programma di massima del corso

    

    Programma di massima del corso File PDF

    Programma di massima del corso e obiettivi formativi. (I punti 2. e 6. del programma, se i tempi di erogazione della didattica non dovessero consentire approfondimenti, potrebbero ridursi a semplici cenni introduttivi).
    

  • Seleziona attività Un esempio di traccia d'esame scritto

    

    Un esempio di traccia d'esame scritto File PDF
• Seleziona sezione Cenni sulla Logica formale

  Cenni sulla Logica formale

  29 febbraio 2016, Aula 4C edificio H2bis, h.14:00--16:00

  • Seleziona attività Cenni sulla logica formale? (Lucidi)

    

    Cenni sulla logica formale? (Lucidi) File PDF
  • Seleziona attività Cosa intendiamo per Logica? (Dispensa)

    

    Cosa intendiamo per Logica? (Dispensa) File PDF
• Seleziona sezione Introduzione al Decimo problema di Hilbert

  Introduzione al Decimo problema di Hilbert

  1 marzo 2016, aula 5C edificio H2bis, h 16:00--18:00

  • Seleziona attività Prefazione al 10.o problema di Hilbert (Lucidi)

    

    Prefazione al 10.o problema di Hilbert (Lucidi) File PDF
• Seleziona sezione Introduzione alla logica proposizionale

  Introduzione alla logica proposizionale

  7 marzo 2016, aula 4B edificio H2bis, h 16:00--18:00

  • Seleziona attività Introduzione alla logica proposizionale (1.a parte: Sintesi)

    

    Introduzione alla logica proposizionale (1.a parte: Sintesi) File PDF

    Lucidi su lessico, sintassi, semantica e potere espressivo della logica proposizionale e sulla sintesi di enunciati proposizionali a partire da funzioni booleane 

• Seleziona sezione Sintesi e analisi, in logica proposizionale

  Sintesi e analisi, in logica proposizionale

  8 marzo 2016, aula 5C edificio H2bis, h 16:00--18:00
  

  • Seleziona attività Introduzione alla logica proposizionale (2.a parte: Analisi)

    

    Introduzione alla logica proposizionale (2.a parte: Analisi) File PDF

    Lucidi sul'analisi di tautologicita` (e soddisfacibilita`). Un apparato deduttivo alla Hillbert per la logica proposizionale.
    

• Seleziona sezione Codifica delle sequenze di enunciati tramite numeri naturali

  Codifica delle sequenze di enunciati tramite numeri naturali

  15 marzo, aula 5C edificio H2bis, h 16:00-18:00

  • Seleziona attività Dispensa sulla codifica di sequenze di enunciati proposizionali

    

    Dispensa sulla codifica di sequenze di enunciati proposizionali File PDF

    Non stampate questa versione della dispensa, perche` una versione estesa con la soluzione dell'esercizio con cui questa si conclude e` registrato sotto, al 23 marzo

• Seleziona sezione Riduzioni di problemi imperniate sulla soddisfacibilita` proposizionale

  Riduzioni di problemi imperniate sulla soddisfacibilita` proposizionale

  16 marzo 2016, aula 5C edificio H2bis, h 16:00-18:00

  • Seleziona attività Riscrittura di qualsiasi istanza di CNF-SAT come u...

    • Riscrittura di qualsiasi istanza di CNF-SAT come un problema di 'unificazione' insiemistica
    • Riscrittura di qualsiasi istanza del problema della  soddisfacibilità proposizionale come un'istanza di 3CNF-SAT
    • Riscrittura di qualsiasi istanza del problema 3CNF-SAT come istanza del X problema di Hilbert
    • -----
    • Elencazione di tutte le dimostrazioni della logica proposizionale 
      
      

  • Seleziona attività Cenni sull'unificazione insiemistica e la riduzione ad essa del problema della soddisfacililita` di enunciati proposizionali in forma normale congiuntiva

    

    Cenni sull'unificazione insiemistica e la riduzione ad essa del problema della soddisfacililita` di enunciati proposizionali in forma normale congiuntiva File PDF
• Seleziona sezione Che cos'e` una logica?

  Che cos'e` una logica?

  22 marzo 2016, aula 5C edificio H2bis, h 16:00-18:00

  • Seleziona attività Lucidi sulle nozioni di: logica, logica booleana, logica booleana minimale

    

    Lucidi sulle nozioni di: logica, logica booleana, logica booleana minimale File PDF

    Si tratta di lucidi collegati alla dispensa del 29 febbraio, che comprendono il teorema di Lindenbaum e il teorema di Post. Si concludono con un'anticipazione delle problematiche: correttezza ('soundness' in inglese) e completezza di un sistema deduttivo formale.

• Seleziona sezione La nozione di insieme enumerabile ricorsivamente.

  La nozione di insieme enumerabile ricorsivamente.

  23 marzo 2016, aula 5C edificio H2bis h 16-18

  • Seleziona attività Qualche altro esercizio sulla logica proposizional...

    Qualche altro esercizio sulla logica proposizionale.

    • Esercizio 1 dell'appello d'esame dell'8/02/2016
    • Dimostrazione induttiva che quando un enunciato alpha e` derivabile da un insieme A di premesse (a partire dagli assiomi logici di Church o di Quine o di...), allora alpha risulta vero in tutti i modelli di A
    • Dimostrazione del teorema di Lindenbaum attraverso il lemma di Zorn
    • Enumerabilita` degli enunciati del linguaggio proposizionale
    • Enumerabilita` delle derivazioni
    • Enumerabilita` degli enuciati derivabili da un insieme decidibile di premesse

  • Seleziona attività Versione aggiornata della dispensa (registrata il 15 marzo) sull'enumerazione delle sequenze di parole. Qui vengono enumerate le *dimostrazioni* della logica proposizionale.

    

    Versione aggiornata della dispensa (registrata il 15 marzo) sull'enumerazione delle sequenze di parole. Qui vengono enumerate le *dimostrazioni* della logica proposizionale. File PDF
  • Seleziona attività Lucidi sulla nozione di insieme enumerabile ricorsivamente (Cenni)

    

    Lucidi sulla nozione di insieme enumerabile ricorsivamente (Cenni) File PDF

    Questi lucidi raccordano la materia di Logica a quella di Computabilita` ---insegnamento che non tutti hanno frequentato. Il loro studio e` facoltativo; tuttavia possono servire a meglio contestualizzare certe problematiche della Logica, specie per chi non abbia frequentato un insegnamento sulla  Computabilita`.

• Seleziona sezione Insiemi specificabili tramite equazioni diofantee polinomiali ed esponenziali

  Insiemi specificabili tramite equazioni diofantee polinomiali ed esponenziali

  30 marzo 2016, aula 5C edificio H2bis h 16-18
  

  • Seleziona attività Lucidi sugli insiemi 'definibili' tramite equazioni

    

    Lucidi sugli insiemi 'definibili' tramite equazioni File PDF
• Seleziona sezione Introduzione alla logica predicativa

  Introduzione alla logica predicativa

  5&6 aprile 2016, aula 5C edificio H2bis h 16-18
  

  
  
  

  • Seleziona attività Lucidi sui linguaggi predicativi del primo ordine, con cenni sulla semantica

    

    Lucidi sui linguaggi predicativi del primo ordine, con cenni sulla semantica File PDF

    (Per una versione piu` compatta---pertanto piu` facile da stampare---di questi lucidi, vedere nella cartella Dopbox condivisa. Il nome del PDF compattato reca il suffisso FLAT)
    

  • Seleziona attività Dispensa sugli assiomi della geometria elementare (esempio motivante)

    

    Dispensa sugli assiomi della geometria elementare (esempio motivante) File PDF
• Seleziona sezione Logica predicativa: apparato deduttivo e semantica

  Logica predicativa: apparato deduttivo e semantica

  12 aprile 2016, aula 5C edificio H2bis h 16-18
  

  Sono riportati sotto questa lezione una doppia serie di lucidi sulla logica predicativa, che guidera` anche le lezioni della prossima settimana.
  

  • Seleziona attività Calcolo Predicativo (Lucidi)

    

    Calcolo Predicativo (Lucidi) File PDF
  • Seleziona attività Semantica dei linguaggi predicativi del 1.o ordine

    

    Semantica dei linguaggi predicativi del 1.o ordine File PDF
• Seleziona sezione Esercizi sui linguaggi predicativi del 1.o ordine

  Esercizi sui linguaggi predicativi del 1.o ordine

  Evidenziato

  13 aprile 2016, aula 5C edificio H2bis h 16-18
  

  • Seleziona attività Due esercizi sulla formalizzazione in aritmetica e sulla modellazione di assiomi aritmetici

    

    Due esercizi sulla formalizzazione in aritmetica e sulla modellazione di assiomi aritmetici File PDF

    (Per una versione piu` compatta---pertanto piu` facile da stampare---di questi lucidi, vedere nella cartella Dopbox condivisa. Il nome del PDF compattato reca il suffisso FLAT)
    

  • Seleziona attività Esercizi (svolti) di dimostrazione in una geometria assiomatica elementare

    

    Esercizi (svolti) di dimostrazione in una geometria assiomatica elementare File PDF
• Seleziona sezione Ripianificazione di meta` corso

  Ripianificazione di meta` corso

  19 aprile 2016, aula 5C edificio H2bis h 16-18
  
• Seleziona sezione Esercitazione sull'uso di un'aritmetica del prim'ordine

  Esercitazione sull'uso di un'aritmetica del prim'ordine

  20 aprile 2016, aula 5C edificio H2bis h 16-18
  

  
  
  

  • Seleziona attività E` stato sviluppata la materia dei lucidi del 13 a...

    E` stato sviluppata la materia dei lucidi del 13 aprile:

    • Formulazione, in un'aritmetica elementare, della congettura di Goldbach (varie possibilita`)
      
    •  Modellazione non standard degli assiomi di una assiomatica (peraltro completa) per l'aritmetica del `successivo'

• Seleziona sezione Logica minimale e teorema di Post sulle tautologie

  Logica minimale e teorema di Post sulle tautologie

  26 aprile 2016, aula 5C edificio H2bis h 16-18

  • Seleziona attività Sono stati ripresi lucidi (e dispense) del 29 febb...

    Sono stati ripresi lucidi (e dispense) del 29 febbraio, per approfondire:

    • logica minimale su un insieme di enunciati,
    • teorema di Post 

    Sono stati inoltre ripresi lucidi del 12 aprile, per introdurre:

    • assiomi logici e regole d'inferenza per il calcolo predicativo del 1.o ordine

• Seleziona sezione l'ABC del calcolo predicativo

  l'ABC del calcolo predicativo

  27 aprile 2016, aula 5C edificio H2bis h 16-18

  Il calcolo predicativo e` una logica booleana: teorema dello scambio e teorema di deduzione.
• Seleziona sezione Teorema della premessa fantasma e Skolemizzazione

  Teorema della premessa fantasma e Skolemizzazione

  3 maggio 2016, aula 5C edificio H2bis h 16-18
  
• Seleziona sezione Verso il teorema di completezza per la logica predicativa del 1.o ordine

  Verso il teorema di completezza per la logica predicativa del 1.o ordine

  4 maggio 2016, aula 5C edificio H2bis h 16-18
  

  • Seleziona attività Si torni ai lucidi sul calcolo predicativo del 1.o...

    Si torni ai lucidi sul calcolo predicativo del 1.o ordine (registrati sotto la lezione del 12 aprile), che nel frattempo sono stati significativamente ampliati.

• Seleziona sezione Il teorema di completezza per la logica predicativa del 1.o ordine (senza uguaglianza)

  Il teorema di completezza per la logica predicativa del 1.o ordine (senza uguaglianza)

  10 maggio 2016, aula 5C edificio H2bis h 16-18
  
• Seleziona sezione Logica clausolare per la risoluzione dei problemi

  Logica clausolare per la risoluzione dei problemi

  11 maggio 2016, aula 5C edificio H2bis h 16-18
  

  • Seleziona attività Clausole di Horn e linguaggi clausolari (lucidi)

    

    Clausole di Horn e linguaggi clausolari (lucidi) File PDF

    (Per una versione piu` compatta---quindi piu` facile da stampare---di questi lucidi, vedere nella cartella Dopbox condivisa. Il nome del PDF compattato reca il suffisso FLAT)
    

• Seleziona sezione Logica clausolare per la risoluzione dei problemi (continuazione)

  Logica clausolare per la risoluzione dei problemi (continuazione)

  17 maggio 2016, aula 5C edificio H2bis h 16-18
  

  
  

  (Stessi lucidi della lezione dell'11 maggio)

  
  
• Seleziona sezione Clausole di Horn e computabilita`

  Clausole di Horn e computabilita`

  18 maggio 2016, aula 5C edificio H2bis h 16-19
  

  • Seleziona attività Lucidi ``Clausole di Horn e Computabilita`''

    

    Lucidi ``Clausole di Horn e Computabilita`'' File PDF

    (Per una versione piu` compatta---pertanto piu` facile da stampare---di questi lucidi, vedere nella cartella Dopbox condivisa. Il nome del PDF compattato reca il suffisso FLAT)

    Una dispensa che sviluppa la dimostrazione di completezza di Turing del linguaggio delle clausole di Horn e` anch'essa reperibile in Dropbox.

• Seleziona sezione Clausole di Horn e computabilita`

  Clausole di Horn e computabilita`

  24 maggio 2016, h.16--18, aula 5C edificio H2bis

  
  

  (E` in questa lezione che, in effetti, vengono presentati i lucidi esposti in Moodle il 18 maggio)
• Seleziona sezione Risultati limitativi riguardanti la logica predicativa del 1.o ordine

  Risultati limitativi riguardanti la logica predicativa del 1.o ordine

  25 maggio 2016, h.16--18, aula 5C edificio H2bis
  

  I risultati limitativi cui si riferisce il titolo di questa sezione sono:

  1. Indecidibilita` della logica predicativa diadica del prim'ordine (teorema di Church alla luce del lavoro seminale di Turing)
  2. Indecidibilita` essenziale dell'aritmetica di Peano (e anche di aritmetiche molto piu` deboli di essa) e di una teoria degli insiemi priva dell'assioma dell'infinito

  Solo il primo di questi due temi sara` trattato a lezione; i lucidi sul secondo vengono ripresi---solo per completezza---dal materiale dell'insegnamento di Logica 2014/2015  

  • Seleziona attività Il teorema di Church

    

    Il teorema di Church File PDF
  • Seleziona attività Indecidibilita` essenziale dell'aritmetica

    

    Indecidibilita` essenziale dell'aritmetica File PDF