204SM - LOGICA 2015

Section outline

• Select section Programma 2015/2016 e indicazioni circa l'esame

  Programma 2015/2016 e indicazioni circa l'esame

  Collapse all Expand all

  • Select activity Forum News

    

    Forum News
  • Select activity 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).
    

  • Select activity Un esempio di traccia d'esame scritto

    

    Un esempio di traccia d'esame scritto File PDF
• Select section Cenni sulla Logica formale

  Cenni sulla Logica formale

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

  • Select activity Cenni sulla logica formale? (Lucidi)

    

    Cenni sulla logica formale? (Lucidi) File PDF
  • Select activity Cosa intendiamo per Logica? (Dispensa)

    

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

  Introduzione al Decimo problema di Hilbert

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

  • Select activity Prefazione al 10.o problema di Hilbert (Lucidi)

    

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

  Introduzione alla logica proposizionale

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

  • Select activity 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 

• Select section Sintesi e analisi, in logica proposizionale

  Sintesi e analisi, in logica proposizionale

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

  • Select activity 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.
    

• Select section 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

  • Select activity 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

• Select section 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

  • Select activity 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 
      
      

  • Select activity 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
• Select section Che cos'e` una logica?

  Che cos'e` una logica?

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

  • Select activity 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.

• Select section La nozione di insieme enumerabile ricorsivamente.

  La nozione di insieme enumerabile ricorsivamente.

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

  • Select activity 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

  • Select activity 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
  • Select activity 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`.

• Select section 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
  

  • Select activity Lucidi sugli insiemi 'definibili' tramite equazioni

    

    Lucidi sugli insiemi 'definibili' tramite equazioni File PDF
• Select section Introduzione alla logica predicativa

  Introduzione alla logica predicativa

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

  
  
  

  • Select activity 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)
    

  • Select activity Dispensa sugli assiomi della geometria elementare (esempio motivante)

    

    Dispensa sugli assiomi della geometria elementare (esempio motivante) File PDF
• Select section 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.
  

  • Select activity Calcolo Predicativo (Lucidi)

    

    Calcolo Predicativo (Lucidi) File PDF
  • Select activity Semantica dei linguaggi predicativi del 1.o ordine

    

    Semantica dei linguaggi predicativi del 1.o ordine File PDF
• Select section Esercizi sui linguaggi predicativi del 1.o ordine

  Esercizi sui linguaggi predicativi del 1.o ordine

  Highlighted

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

  • Select activity 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)
    

  • Select activity Esercizi (svolti) di dimostrazione in una geometria assiomatica elementare

    

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

  Ripianificazione di meta` corso

  19 aprile 2016, aula 5C edificio H2bis h 16-18
  
• Select section 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
  

  
  
  

  • Select activity 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'

• Select section 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

  • Select activity 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

• Select section 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.
• Select section Teorema della premessa fantasma e Skolemizzazione

  Teorema della premessa fantasma e Skolemizzazione

  3 maggio 2016, aula 5C edificio H2bis h 16-18
  
• Select section 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
  

  • Select activity 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.

• Select section 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
  
• Select section Logica clausolare per la risoluzione dei problemi

  Logica clausolare per la risoluzione dei problemi

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

  • Select activity 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)
    

• Select section 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)

  
  
• Select section Clausole di Horn e computabilita`

  Clausole di Horn e computabilita`

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

  • Select activity 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.

• Select section 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)
• Select section 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  

  • Select activity Il teorema di Church

    

    Il teorema di Church File PDF
  • Select activity Indecidibilita` essenziale dell'aritmetica

    

    Indecidibilita` essenziale dell'aritmetica File PDF