Zur Seitennavigation oder mit Tastenkombination für den accesskey-Taste und Taste 1 
Zum Seiteninhalt oder mit Tastenkombination für den accesskey und Taste 2 

ONLINE im WS 2020/21: Logik und Beweisbarkeit - Einzelansicht

  • Funktionen:
Grunddaten
Veranstaltungsart Vorlesung/Übung Langtext
Veranstaltungsnummer 9718 Kurztext FMI-IN0082
Semester WS 2020 SWS 5
Teilnehmer 1. Platzvergabe 20 Max. Teilnehmer 2. Platzvergabe 30
Rhythmus Jedes 2. Semester Studienjahr
Credits für IB und SPZ
E-Learning-Plattform Moodle  
Hyperlink
Weitere Links
Informationen, Skript, Folien, Übungsblätter https://users.fmi.uni-jena.de/~mundhenk/LB.html
Sprache Deutsch
Belegungsfrist Standardbelegung Wintersemester ab Mitte August/ Sommersemester ab Mitte Februar
Abmeldefristen B1 - Belegung ohne Abmeldung    31.08.2020 09:00:00 - 21.10.2020 07:59:59   
Nach Zulassung ist eine Abmeldung nur durch den Dozenten möglich.
B2 - Belegung mit Abmeldung 6 Wochen    21.10.2020 08:00:00 - 14.12.2020 23:59:59    aktuell
Nach Zulassung ist eine Abmeldung auch durch den Teilnehmer möglich.
B3 - Belegung ohne Abmeldung    15.12.2020 00:00:01 - 22.02.2021 07:59:59   
Nach Zulassung ist eine Abmeldung nur durch den Dozenten möglich.
Termine Gruppe: 1-Gruppe iCalendar Export für Outlook
  Tag Zeit Rhythmus Dauer Raum Lehrperson (Zuständigkeit) Status Bemerkung fällt aus am Max. Teilnehmer 2. Platzvergabe
Einzeltermine anzeigen Di. 14:00 bis 16:00 w. 03.11.2020 bis
09.02.2021
    findet statt  
Einzeltermine anzeigen Do. 14:00 bis 16:00 w. 05.11.2020 bis
11.02.2021
    findet statt  
Gruppe 1-Gruppe:



Zugeordnete Person
Zugeordnete Person Zuständigkeit
Mundhenk, Martin, Universitätsprofessor, Dr. verantwortlich
Module / Prüfungen
Modul Prüfungsnummer Titel VE.Nr. Veranstaltungseinheit
FMI-IN3164 Mastermodul Algorithmik/Theoretische Informatik IV - 6 LP
P-Nr. : 352141 Mastermodul Algorithmik/Theoretische Informatik IV - 6 LP: mündl. o. schriftl. Prüfung
352143 Mastermodul Algorithmik/Theoretische Informatik IV - 6 LP: Vorlesung/Übung/Praktikum
FMI-IN3163 Mastermodul Algorithmik/Theoretische Informatik III - 6 LP
P-Nr. : 352131 Mastermodul Algorithmik/Theoretische Informatik III - 6 LP: mündl. o. schriftl. Prüfung
352133 Mastermodul Algorithmik/Theoretische Informatik III - 6 LP: Vorlesung/Übung/Praktikum
FMI-IN3162 Mastermodul Algorithmik/Theoretische Informatik II - 6 LP
P-Nr. : 352121 Mastermodul Algorithmik/Theoretische Informatik II - 6 LP: mündl. o. schriftl. Prüfung
352123 Mastermodul Algorithmik/Theoretische Informatik II - 6 LP: Vorlesung/Übung/Praktikum
FMI-IN3161 Mastermodul Algorithmik/Theoretische Informatik I - 6 LP
P-Nr. : 352111 Mastermodul Algorithmik/Theoretische Informatik I - 6 LP: mündl. o. schriftl. Prüfung
352113 Mastermodul Algorithmik/Theoretische Informatik I - 6 LP: Vorlesung/Übung/Praktikum
50824 Logik und Beweisbarkeit: Übung
FMI-IN0082 Logik und Beweisbarkeit
P-Nr. : 50821 Logik und Beweisbarkeit: Klausur oder mündliche Prüfung
50823 Logik und Beweisbarkeit: Vorlesung/Übung
Zuordnung zu Einrichtungen
Theoretische Informatik
Fakultät für Mathematik und Informatik
Inhalt
Kommentar

Kann man alle wahren arithmetischen Aussagen (z.B.(?): es gibt unendlich viele Primzahlzwillinge) formal beweisen?
Kurt Gödel hat mit seinen Unvollständigkeitssätzen gezeigt, dass das nicht geht.
In dieser Vorlesung werden wir uns ansehen, was geht und was nicht geht, und warum es so ist.

Wir beginnen mit dem einfachen Fall der Aussagenlogik, gehen dann über die variablenfreie Arithmetik zur ∑1-Arithmetik (das ist der Teil der Arithmetik ohne unbeschränkte Allquantoren).Für diese Logiken werden wir Vollständigkeitssätze für entsprechende Beweissysteme zeigen.

Damit haben wir gesehen, was geht. Weiter geht's mit dem, was nicht geht. Dafür brauchen wir als Fundament etwas Berechenbarkeitstheorie und verbinden dann – etwas verblüffend – die Begriffe Berechnung und Beweis. Auf diesem Fundament ist der Beweis des Gödelschen Unvollständigkeitssatzes recht einfach.

Zum Abschluss werden wir noch in die Original-Arbeit von Gödel schauen und sehen, was er anders gemacht hat.

Literatur
  • Gödel, K.: Über formal unentscheidbare Sätze der Pricipia Mathematica und verwandter Systeme I. Monatshefte der Mathematik und Physik, 38: 173-198, 1931.
  • van Dalen, D.: Logic and Structure. Springer Verlag, 2004.
  • Smith, P.: An Introduction to Gödel's Theorems. Cambridge University Press, 2013.
  • Cutland, N.J.: Computability. Cambridge University Press, 1980.
  • Wolf, R.S.: A Tour Through Mathematical Logic. The Mathematical Association of America, 2005.
Lerninhalte
  • Formale Aussagenlogik und formale Arithmetik
  • Formales Beweisen mittels Natürlichem Schließen
  • Vollständigkeitssatz für Natürliches Schließen in der Aussagenlogik
  • Vollständigkeitssatz für Natürliches Schließen mit den Robinson-Axiomen in der ∑1-Arithmetik
  • Berechenbarkeitstheorie: entscheidbare und semi-entscheidbare Mengen
  • Semi-entscheidbare Mengen sind genau die durch ∑1-Formeln beschriebenen Mengen
  • Unvollständigkeitssätze von Gödel
Strukturbaum
Die Veranstaltung wurde 7 mal im Vorlesungsverzeichnis WiSe 2020/21 gefunden:
Vertiefung Informatik  - - - 2
Mathematik  - - - 3
Informatik  - - - 4

Impressum | Datenschutzerklärung