Curriculum
Fruizione: 20410451-1 LM410 -TEOREMI SULLA LOGICA 1 - MODULO A in Matematica LM-40 TORTORA DE FALCO LORENZO, MAIELI ROBERTO,
Programma
Modulo A:Parte 1: Alcune nozioni preliminari.
Relazioni d'ordine e alberi, definizioni induttive, dimostrazioni per induzione, assioma di scelta e lemma di Kőnig.
Parte 2: Dimostrabilità e soddisfacibilità
Linguaggio formale del primo ordine: alfabeto, termini , formule, sequenti. Strutture per un linguaggio del primo ordine: strutture, termini e formule a parametri in una struttura, valutazione di termini, formule e sequenti. Calcolo dei sequenti per la logica del primo ordine: il calcolo dei sequenti LK di Gentzen. Sequenti derivabili e derivazioni. Correttezza delle regole di LK. Analisi canonica e teorema fondamentale: costruzione dellanalisi canonica (con e senza tagli) e dimostrazione del teorema fondamentale dellanalisi canonica. Conseguenze del teorema fondamentale dell'analisi canocica: teoremi di completezza, eliminabilit del taglio, compattezza, L"owenheim-Skolem.
Parte 3: Verso la teoria della dimostrazione: il teorema di eliminazione del taglio.
La procedura di eliminazione del taglio. Definizione dei passi elementari di eliminazione del taglio. Prima strategia dimostrativa (riduzione a grandi passi). Seconda strategia dimostrativa (rovesciamento delle derivazioni). Cenni sulla complessit\`a della procedura di eliminazione del taglio. Qualche conseguenza immediata del teorema di eliminazione del taglio.
Modulo B: Verso la teoria dei modelli: alcune conseguenze del teorema di compattezza.
Dimostrazione del teorema di compattezza per linguaggi di cardinalità qualsiasi. Linguaggi con uguaglianza. Il teorema di compattezza per i linguaggi con uguaglianza. Correttezza e completezza per i linguaggi con uguaglianza. Il teorema di L"owenheim-Skolem per i linguaggi con uguaglianza (numerabili). Limiti espressivi del linguaggio del primo ordine. Equivalenza elementare, sottostrutture, sottostrutture elementari. Isomorfismo ed equivalenza elementare. La nozione di sottostruttura. Sottostrutture elementari e diagrammi. I teoremi di preservazione. Generalizzazioni del teorema di L"owenheim-Skolem. Completezza di una teoria.
Testi Adottati
V.M. Abrusci, L. Tortora de Falco, Logica Volume 1- Dimostrazioni e modelli al primoordine. Springer, (2014).
Modalità Erogazione
Il corso prevede Didattica frontale; Discussioni con gli studenti e dibattiti sugli argomenti trattati; Esercitazioni; La frequenza non è obbligatoria ma è vivamente raccomandata.Modalità Valutazione
Esame scritto e/o orale, di durata variabile, in media tra 60 e 80 minuti.Fruizione: 20410451-1 LM410 -TEOREMI SULLA LOGICA 1 - MODULO A in Matematica LM-40 TORTORA DE FALCO LORENZO, MAIELI ROBERTO,
Programma
Modulo A:Parte 1: Alcune nozioni preliminari.
Relazioni d'ordine e alberi, definizioni induttive, dimostrazioni per induzione, assioma di scelta e lemma di Kőnig.
Parte 2: Dimostrabilità e soddisfacibilità
Linguaggio formale del primo ordine: alfabeto, termini , formule, sequenti. Strutture per un linguaggio del primo ordine: strutture, termini e formule a parametri in una struttura, valutazione di termini, formule e sequenti. Calcolo dei sequenti per la logica del primo ordine: il calcolo dei sequenti LK di Gentzen. Sequenti derivabili e derivazioni. Correttezza delle regole di LK. Analisi canonica e teorema fondamentale: costruzione dellanalisi canonica (con e senza tagli) e dimostrazione del teorema fondamentale dellanalisi canonica. Conseguenze del teorema fondamentale dell'analisi canocica: teoremi di completezza, eliminabilit del taglio, compattezza, L"owenheim-Skolem.
Parte 3: Verso la teoria della dimostrazione: il teorema di eliminazione del taglio.
La procedura di eliminazione del taglio. Definizione dei passi elementari di eliminazione del taglio. Prima strategia dimostrativa (riduzione a grandi passi). Seconda strategia dimostrativa (rovesciamento delle derivazioni). Cenni sulla complessit\`a della procedura di eliminazione del taglio. Qualche conseguenza immediata del teorema di eliminazione del taglio.
Modulo B: Verso la teoria dei modelli: alcune conseguenze del teorema di compattezza.
Dimostrazione del teorema di compattezza per linguaggi di cardinalità qualsiasi. Linguaggi con uguaglianza. Il teorema di compattezza per i linguaggi con uguaglianza. Correttezza e completezza per i linguaggi con uguaglianza. Il teorema di L"owenheim-Skolem per i linguaggi con uguaglianza (numerabili). Limiti espressivi del linguaggio del primo ordine. Equivalenza elementare, sottostrutture, sottostrutture elementari. Isomorfismo ed equivalenza elementare. La nozione di sottostruttura. Sottostrutture elementari e diagrammi. I teoremi di preservazione. Generalizzazioni del teorema di L"owenheim-Skolem. Completezza di una teoria.
Testi Adottati
V.M. Abrusci, L. Tortora de Falco, Logica Volume 1- Dimostrazioni e modelli al primo
ordine. Springer, (2014).
Modalità Erogazione
Il corso prevede Didattica frontale; Discussioni con gli studenti e dibattiti sugli argomenti trattati; Esercitazioni; La frequenza non è obbligatoria ma è vivamente raccomandata.Modalità Valutazione
Esame scritto e/o orale, di durata variabile, in media tra 60 e 80 minuti.Fruizione: 20410451-1 LM410 -TEOREMI SULLA LOGICA 1 - MODULO A in Matematica LM-40 TORTORA DE FALCO LORENZO, MAIELI ROBERTO,
Fruizione: 20410451-1 LM410 -TEOREMI SULLA LOGICA 1 - MODULO A in Matematica LM-40 TORTORA DE FALCO LORENZO, MAIELI ROBERTO,
Programma
Modulo A:Parte 1: Alcune nozioni preliminari.
Relazioni d'ordine e alberi, definizioni induttive, dimostrazioni per induzione, assioma di scelta e lemma di Kőnig.
Parte 2: Dimostrabilità e soddisfacibilità
Linguaggio formale del primo ordine: alfabeto, termini , formule, sequenti. Strutture per un linguaggio del primo ordine: strutture, termini e formule a parametri in una struttura, valutazione di termini, formule e sequenti. Calcolo dei sequenti per la logica del primo ordine: il calcolo dei sequenti LK di Gentzen. Sequenti derivabili e derivazioni. Correttezza delle regole di LK. Analisi canonica e teorema fondamentale: costruzione dellanalisi canonica (con e senza tagli) e dimostrazione del teorema fondamentale dellanalisi canonica. Conseguenze del teorema fondamentale dell'analisi canocica: teoremi di completezza, eliminabilit del taglio, compattezza, L"owenheim-Skolem.
Parte 3: Verso la teoria della dimostrazione: il teorema di eliminazione del taglio.
La procedura di eliminazione del taglio. Definizione dei passi elementari di eliminazione del taglio. Prima strategia dimostrativa (riduzione a grandi passi). Seconda strategia dimostrativa (rovesciamento delle derivazioni). Cenni sulla complessit\`a della procedura di eliminazione del taglio. Qualche conseguenza immediata del teorema di eliminazione del taglio.
Modulo B: Verso la teoria dei modelli: alcune conseguenze del teorema di compattezza.
Dimostrazione del teorema di compattezza per linguaggi di cardinalità qualsiasi. Linguaggi con uguaglianza. Il teorema di compattezza per i linguaggi con uguaglianza. Correttezza e completezza per i linguaggi con uguaglianza. Il teorema di L"owenheim-Skolem per i linguaggi con uguaglianza (numerabili). Limiti espressivi del linguaggio del primo ordine. Equivalenza elementare, sottostrutture, sottostrutture elementari. Isomorfismo ed equivalenza elementare. La nozione di sottostruttura. Sottostrutture elementari e diagrammi. I teoremi di preservazione. Generalizzazioni del teorema di L"owenheim-Skolem. Completezza di una teoria.
Testi Adottati
V.M. Abrusci, L. Tortora de Falco, Logica Volume 1- Dimostrazioni e modelli al primoordine. Springer, (2014).
Modalità Erogazione
Il corso prevede Didattica frontale; Discussioni con gli studenti e dibattiti sugli argomenti trattati; Esercitazioni; La frequenza non è obbligatoria ma è vivamente raccomandata.Modalità Valutazione
Esame scritto e/o orale, di durata variabile, in media tra 60 e 80 minuti.Fruizione: 20410451-1 LM410 -TEOREMI SULLA LOGICA 1 - MODULO A in Matematica LM-40 TORTORA DE FALCO LORENZO, MAIELI ROBERTO,
Programma
Modulo A:Parte 1: Alcune nozioni preliminari.
Relazioni d'ordine e alberi, definizioni induttive, dimostrazioni per induzione, assioma di scelta e lemma di Kőnig.
Parte 2: Dimostrabilità e soddisfacibilità
Linguaggio formale del primo ordine: alfabeto, termini , formule, sequenti. Strutture per un linguaggio del primo ordine: strutture, termini e formule a parametri in una struttura, valutazione di termini, formule e sequenti. Calcolo dei sequenti per la logica del primo ordine: il calcolo dei sequenti LK di Gentzen. Sequenti derivabili e derivazioni. Correttezza delle regole di LK. Analisi canonica e teorema fondamentale: costruzione dellanalisi canonica (con e senza tagli) e dimostrazione del teorema fondamentale dellanalisi canonica. Conseguenze del teorema fondamentale dell'analisi canocica: teoremi di completezza, eliminabilit del taglio, compattezza, L"owenheim-Skolem.
Parte 3: Verso la teoria della dimostrazione: il teorema di eliminazione del taglio.
La procedura di eliminazione del taglio. Definizione dei passi elementari di eliminazione del taglio. Prima strategia dimostrativa (riduzione a grandi passi). Seconda strategia dimostrativa (rovesciamento delle derivazioni). Cenni sulla complessit\`a della procedura di eliminazione del taglio. Qualche conseguenza immediata del teorema di eliminazione del taglio.
Modulo B: Verso la teoria dei modelli: alcune conseguenze del teorema di compattezza.
Dimostrazione del teorema di compattezza per linguaggi di cardinalità qualsiasi. Linguaggi con uguaglianza. Il teorema di compattezza per i linguaggi con uguaglianza. Correttezza e completezza per i linguaggi con uguaglianza. Il teorema di L"owenheim-Skolem per i linguaggi con uguaglianza (numerabili). Limiti espressivi del linguaggio del primo ordine. Equivalenza elementare, sottostrutture, sottostrutture elementari. Isomorfismo ed equivalenza elementare. La nozione di sottostruttura. Sottostrutture elementari e diagrammi. I teoremi di preservazione. Generalizzazioni del teorema di L"owenheim-Skolem. Completezza di una teoria.
Testi Adottati
V.M. Abrusci, L. Tortora de Falco, Logica Volume 1- Dimostrazioni e modelli al primo
ordine. Springer, (2014).
Modalità Erogazione
Il corso prevede Didattica frontale; Discussioni con gli studenti e dibattiti sugli argomenti trattati; Esercitazioni; La frequenza non è obbligatoria ma è vivamente raccomandata.Modalità Valutazione
Esame scritto e/o orale, di durata variabile, in media tra 60 e 80 minuti.Fruizione: 20410451-1 LM410 -TEOREMI SULLA LOGICA 1 - MODULO A in Matematica LM-40 TORTORA DE FALCO LORENZO, MAIELI ROBERTO,
Fruizione: 20410451-2 LM410 -TEOREMI SULLA LOGICA 1 - MODULO B in Matematica LM-40 TORTORA DE FALCO LORENZO
Programma
Modulo A:Parte 1: Alcune nozioni preliminari.
Relazioni d'ordine e alberi, definizioni induttive, dimostrazioni per induzione, assioma di scelta e lemma di Kőnig.
Parte 2: Dimostrabilità e soddisfacibilità
Linguaggio formale del primo ordine: alfabeto, termini , formule, sequenti. Strutture per un linguaggio del primo ordine: strutture, termini e formule a parametri in una struttura, valutazione di termini, formule e sequenti. Calcolo dei sequenti per la logica del primo ordine: il calcolo dei sequenti LK di Gentzen. Sequenti derivabili e derivazioni. Correttezza delle regole di LK. Analisi canonica e teorema fondamentale: costruzione dellanalisi canonica (con e senza tagli) e dimostrazione del teorema fondamentale dellanalisi canonica. Conseguenze del teorema fondamentale dell'analisi canocica: teoremi di completezza, eliminabilit del taglio, compattezza, L"owenheim-Skolem.
Parte 3: Verso la teoria della dimostrazione: il teorema di eliminazione del taglio.
La procedura di eliminazione del taglio. Definizione dei passi elementari di eliminazione del taglio. Prima strategia dimostrativa (riduzione a grandi passi). Seconda strategia dimostrativa (rovesciamento delle derivazioni). Cenni sulla complessit\`a della procedura di eliminazione del taglio. Qualche conseguenza immediata del teorema di eliminazione del taglio.
Modulo B: Verso la teoria dei modelli: alcune conseguenze del teorema di compattezza.
Dimostrazione del teorema di compattezza per linguaggi di cardinalità qualsiasi. Linguaggi con uguaglianza. Il teorema di compattezza per i linguaggi con uguaglianza. Correttezza e completezza per i linguaggi con uguaglianza. Il teorema di L"owenheim-Skolem per i linguaggi con uguaglianza (numerabili). Limiti espressivi del linguaggio del primo ordine. Equivalenza elementare, sottostrutture, sottostrutture elementari. Isomorfismo ed equivalenza elementare. La nozione di sottostruttura. Sottostrutture elementari e diagrammi. I teoremi di preservazione. Generalizzazioni del teorema di L"owenheim-Skolem. Completezza di una teoria.
Testi Adottati
V.M. Abrusci, L. Tortora de Falco, Logica Volume 1- Dimostrazioni e modelli al primoordine. Springer, (2014).
Modalità Erogazione
Il corso prevede Didattica frontale; Discussioni con gli studenti e dibattiti sugli argomenti trattati; Esercitazioni; La frequenza non è obbligatoria ma è vivamente raccomandata.Modalità Valutazione
Esame scritto e/o orale, di durata variabile, in media tra 60 e 80 minuti.Fruizione: 20410451-1 LM410 -TEOREMI SULLA LOGICA 1 - MODULO A in Matematica LM-40 TORTORA DE FALCO LORENZO, MAIELI ROBERTO,
Programma
Modulo A:Parte 1: Alcune nozioni preliminari.
Relazioni d'ordine e alberi, definizioni induttive, dimostrazioni per induzione, assioma di scelta e lemma di Kőnig.
Parte 2: Dimostrabilità e soddisfacibilità
Linguaggio formale del primo ordine: alfabeto, termini , formule, sequenti. Strutture per un linguaggio del primo ordine: strutture, termini e formule a parametri in una struttura, valutazione di termini, formule e sequenti. Calcolo dei sequenti per la logica del primo ordine: il calcolo dei sequenti LK di Gentzen. Sequenti derivabili e derivazioni. Correttezza delle regole di LK. Analisi canonica e teorema fondamentale: costruzione dellanalisi canonica (con e senza tagli) e dimostrazione del teorema fondamentale dellanalisi canonica. Conseguenze del teorema fondamentale dell'analisi canocica: teoremi di completezza, eliminabilit del taglio, compattezza, L"owenheim-Skolem.
Parte 3: Verso la teoria della dimostrazione: il teorema di eliminazione del taglio.
La procedura di eliminazione del taglio. Definizione dei passi elementari di eliminazione del taglio. Prima strategia dimostrativa (riduzione a grandi passi). Seconda strategia dimostrativa (rovesciamento delle derivazioni). Cenni sulla complessit\`a della procedura di eliminazione del taglio. Qualche conseguenza immediata del teorema di eliminazione del taglio.
Modulo B: Verso la teoria dei modelli: alcune conseguenze del teorema di compattezza.
Dimostrazione del teorema di compattezza per linguaggi di cardinalità qualsiasi. Linguaggi con uguaglianza. Il teorema di compattezza per i linguaggi con uguaglianza. Correttezza e completezza per i linguaggi con uguaglianza. Il teorema di L"owenheim-Skolem per i linguaggi con uguaglianza (numerabili). Limiti espressivi del linguaggio del primo ordine. Equivalenza elementare, sottostrutture, sottostrutture elementari. Isomorfismo ed equivalenza elementare. La nozione di sottostruttura. Sottostrutture elementari e diagrammi. I teoremi di preservazione. Generalizzazioni del teorema di L"owenheim-Skolem. Completezza di una teoria.
Testi Adottati
V.M. Abrusci, L. Tortora de Falco, Logica Volume 1- Dimostrazioni e modelli al primoordine. Springer, (2014).
Modalità Erogazione
Il corso prevede Didattica frontale; Discussioni con gli studenti e dibattiti sugli argomenti trattati; Esercitazioni; La frequenza non è obbligatoria ma è vivamente raccomandata.Modalità Valutazione
Esame scritto e/o orale, di durata variabile, in media tra 60 e 80 minuti.Fruizione: 20410451-1 LM410 -TEOREMI SULLA LOGICA 1 - MODULO A in Matematica LM-40 TORTORA DE FALCO LORENZO, MAIELI ROBERTO,
Programma
Modulo A:Parte 1: Alcune nozioni preliminari.
Relazioni d'ordine e alberi, definizioni induttive, dimostrazioni per induzione, assioma di scelta e lemma di Kőnig.
Parte 2: Dimostrabilità e soddisfacibilità
Linguaggio formale del primo ordine: alfabeto, termini , formule, sequenti. Strutture per un linguaggio del primo ordine: strutture, termini e formule a parametri in una struttura, valutazione di termini, formule e sequenti. Calcolo dei sequenti per la logica del primo ordine: il calcolo dei sequenti LK di Gentzen. Sequenti derivabili e derivazioni. Correttezza delle regole di LK. Analisi canonica e teorema fondamentale: costruzione dellanalisi canonica (con e senza tagli) e dimostrazione del teorema fondamentale dellanalisi canonica. Conseguenze del teorema fondamentale dell'analisi canocica: teoremi di completezza, eliminabilit del taglio, compattezza, L"owenheim-Skolem.
Parte 3: Verso la teoria della dimostrazione: il teorema di eliminazione del taglio.
La procedura di eliminazione del taglio. Definizione dei passi elementari di eliminazione del taglio. Prima strategia dimostrativa (riduzione a grandi passi). Seconda strategia dimostrativa (rovesciamento delle derivazioni). Cenni sulla complessit\`a della procedura di eliminazione del taglio. Qualche conseguenza immediata del teorema di eliminazione del taglio.
Modulo B: Verso la teoria dei modelli: alcune conseguenze del teorema di compattezza.
Dimostrazione del teorema di compattezza per linguaggi di cardinalità qualsiasi. Linguaggi con uguaglianza. Il teorema di compattezza per i linguaggi con uguaglianza. Correttezza e completezza per i linguaggi con uguaglianza. Il teorema di L"owenheim-Skolem per i linguaggi con uguaglianza (numerabili). Limiti espressivi del linguaggio del primo ordine. Equivalenza elementare, sottostrutture, sottostrutture elementari. Isomorfismo ed equivalenza elementare. La nozione di sottostruttura. Sottostrutture elementari e diagrammi. I teoremi di preservazione. Generalizzazioni del teorema di L"owenheim-Skolem. Completezza di una teoria.
Testi Adottati
V.M. Abrusci, L. Tortora de Falco, Logica Volume 1- Dimostrazioni e modelli al primo
ordine. Springer, (2014).
Modalità Erogazione
Il corso prevede Didattica frontale; Discussioni con gli studenti e dibattiti sugli argomenti trattati; Esercitazioni; La frequenza non è obbligatoria ma è vivamente raccomandata.Modalità Valutazione
Esame scritto e/o orale, di durata variabile, in media tra 60 e 80 minuti.Fruizione: 20410451-1 LM410 -TEOREMI SULLA LOGICA 1 - MODULO A in Matematica LM-40 TORTORA DE FALCO LORENZO, MAIELI ROBERTO,
Fruizione: 20410451-2 LM410 -TEOREMI SULLA LOGICA 1 - MODULO B in Matematica LM-40 TORTORA DE FALCO LORENZO
Programma
Modulo A:Parte 1: Alcune nozioni preliminari.
Relazioni d'ordine e alberi, definizioni induttive, dimostrazioni per induzione, assioma di scelta e lemma di Kőnig.
Parte 2: Dimostrabilità e soddisfacibilità
Linguaggio formale del primo ordine: alfabeto, termini , formule, sequenti. Strutture per un linguaggio del primo ordine: strutture, termini e formule a parametri in una struttura, valutazione di termini, formule e sequenti. Calcolo dei sequenti per la logica del primo ordine: il calcolo dei sequenti LK di Gentzen. Sequenti derivabili e derivazioni. Correttezza delle regole di LK. Analisi canonica e teorema fondamentale: costruzione dellanalisi canonica (con e senza tagli) e dimostrazione del teorema fondamentale dellanalisi canonica. Conseguenze del teorema fondamentale dell'analisi canocica: teoremi di completezza, eliminabilit del taglio, compattezza, L"owenheim-Skolem.
Parte 3: Verso la teoria della dimostrazione: il teorema di eliminazione del taglio.
La procedura di eliminazione del taglio. Definizione dei passi elementari di eliminazione del taglio. Prima strategia dimostrativa (riduzione a grandi passi). Seconda strategia dimostrativa (rovesciamento delle derivazioni). Cenni sulla complessit\`a della procedura di eliminazione del taglio. Qualche conseguenza immediata del teorema di eliminazione del taglio.
Modulo B: Verso la teoria dei modelli: alcune conseguenze del teorema di compattezza.
Dimostrazione del teorema di compattezza per linguaggi di cardinalità qualsiasi. Linguaggi con uguaglianza. Il teorema di compattezza per i linguaggi con uguaglianza. Correttezza e completezza per i linguaggi con uguaglianza. Il teorema di L"owenheim-Skolem per i linguaggi con uguaglianza (numerabili). Limiti espressivi del linguaggio del primo ordine. Equivalenza elementare, sottostrutture, sottostrutture elementari. Isomorfismo ed equivalenza elementare. La nozione di sottostruttura. Sottostrutture elementari e diagrammi. I teoremi di preservazione. Generalizzazioni del teorema di L"owenheim-Skolem. Completezza di una teoria.
Testi Adottati
V.M. Abrusci, L. Tortora de Falco, Logica Volume 1- Dimostrazioni e modelli al primoordine. Springer, (2014).
Modalità Erogazione
Il corso prevede Didattica frontale; Discussioni con gli studenti e dibattiti sugli argomenti trattati; Esercitazioni; La frequenza non è obbligatoria ma è vivamente raccomandata.Modalità Valutazione
Esame scritto e/o orale, di durata variabile, in media tra 60 e 80 minuti.