TU Wien:Logic and Computability VU (Ciabattoni)

Daten

Zuordnungen

Masterstudium Logic and Computation

Modul Logic and Computability (Pflichtfach)

Inhalt

Teil 1: Aussagelogik, PL1, Natürliches schließen, Herbrand Kalkül, Sequenzenkalkül

Teil 2: Automated Deduction, Modallogik, Intuitionistic Logic

Teil 3: Berechnungsmodelle (Turing Maschinen, Lambda Kalkül, rekursive Funktionen), Berechenbarkeit

Teil 4: Unvollständigkeit (Gödel's Unvollständigkeitssatz)

Ablauf

Von Oktober an zwei Mal pro Woche Vorlesung. Jede Vorlesung kann 60-120 Minuten dauern. Die Länge hängt hier immer sehr stark vom Thema und der Laune des Vortragenden ab.

Zusätzlich gibt es drei Übungsblätter (für Teil 1 bis 3) die alleine gelöst werden sollen. Eine Ausarbeitung in Latex bzw. Word wird verlangt.

Abgaben und Kommunikation mit den Vortragenden erfolgt per Email. Man kann auch Fragen zum Stoff per Email stellen. Es wird in der Regel schnell geantwortet.

Benötigte/Empfehlenswerte Vorkenntnisse

Grundkenntnisse über Logik etwa von TIL sind empfehlenswert. Prinzipiell wird aber alles erklärt. Wenn TIL nicht besucht wurde, gibt es im Laufe des Kurses noch ein Repetitorium zum Stoff von TIL.

Vortrag

Teils auf den Folien, Teils auf der Tafel (Beweise, Beispiele etc.). Vortrag ist bemüht und will interaktiv sein.

Teil 1 + 3 (Ciabattoni): Die Folien reichen zum Lernen alleine nicht aus. Es gibt aber für Teil 1 ein (sehr gutes) und für Teil 3 ein (mittelmäßig gutes) Skript.

Teil 2 + 4 (Fermüller): Die zwei Vorlesungen zum 4. Teil zu besuchen ist sehr empfehlenswert, sonst wird das Lernen des Themas echt hart.

Übungen

3 Übungsblätter für die jeweils 2-3 Wochen Zeit ist Bewertung ist sehr human. Man bekommt aber kein Feedback zugeschickt, sondern es gibt in einer der letzten Einheiten ein Q&A wo man ausführlich individuelles mündliches Feedback zur Abgabe erhält und die Bewertung erfährt.

Prüfung, Benotung

Schriftliche Prüfung, an die Übungsbeispiele angelehnt. Dann noch zwei mündliche Prüfungen (bei beiden Vortragenden getrennt). Es kann praktisch sein, da ein paar Tage dazwischen zu haben, um sich den Stoff bei Lernen aufteilen zu können.

January 2022: Notification about passing the written part was after 3 days. The first oral exam date was 7 days after the written exam. Prof. Fermüllers oral exam was directly after Ciabattoni's oral exam.

Ciabattoni:

• Asked for clarifications about two answers (of the computability part) that I gave in the written exam
• I apparently did bad in the computability theory part, so questions from the question catalog were only about computability:
  • Proof Equivalence between r.e. sets and semi-decidable sets
  • Proof of Rice Theorem (talking about the additional steps that she mentioned in the lecture video seemed well received)
  • Proof of Post theorem
  • It was important to know the theorems precisely

Fermüller:

• Also asked for clarifications about the ADRF answer that I gave in the exam. Small errors in the automated deduction part in written exam were not too important.
• Questions about what was not covered in exam: Intuitionistic logic & Incompleteness
  • Prove (G & F) -> (F v H) in BHK semantics. It is good to use the right words, not "it holds" (this is classical logic), talk about pairs & indicators for the OR, he often mentioned "there is an algorithm, a _concrete_ program that takes and transforms something"
  • Difference between Gödel-incompleteness (sentence that is neither in set of provable nor in set of refutable sentences) and incompleteness (we know the sentence is true, but not it is not provable). It was important to use precisely the definition from the slides. Talking about the definition from another course hasn't helped.

I messed up on the r.e./semi-decidability proof but think I did really good on the other proofs and Ciabattoni proposed a 3 because she still had the feeling that I haven't studied that part. Doing exceptionally well on the Fermüller part would have made it a 2, but doing "OK" left it at 3. So I think written and oral exam were not really separate grades as it seemed in the grading schema.

May 2023: The impression that they get from the written exam is important to them. If you have a good written exam, the oral exam should be simpler. Especially in Fermüller's part in the oral exam, he is not very much into the definitions and formal notation, but he is very much into discussing the topics and the general ideas. He asked me the same question of :

• Difference between Gödel-incompleteness (sentence that is neither in set of provable nor in set of refutable sentences) and incompleteness (we know the sentence is true, but not it is not provable). It was important to use precisely the definition from the slides. Talking about the definition from another course hasn't helped.

It seems to be important for them to define them like this. I wanted to do it based on the notation and he just wanted to hear those sentences.

They stick to the question sheet that they provided us before the oral exam. Ciabattoni provided a paper and asked for the proof of the post theorem and that any r.e set is also semi-decidable + the Soundness and Completeness of the Propositional Sequent Calculus. I also got the impression if you do well in oral exams with only one of them, you can be graded 2 or even 1 with a very normal written exam.

Dauer der Zeugnisausstellung

10 Min nach der mündlichen Prüfung (war aber der letzte).

Zeitaufwand

Hängt sehr stark vom Vorwissen und der Affinität für Logik und formale Themen ab, sollte aber auch ohne große Vorkenntnisse unter den 6 ECTS liegen.

Meine Erfahrung (mit Vorwissen und Interesse): 3*5h für die Übgungsblätter, 15 Stunden Lernen für die Prüfung für ein S1.

Andere Meinung (WS2022): Der vom LVA-Team so angegebene geschätzte Aufwand von 20h pro Übungsblatt ist durchaus realistisch und meiner Meinung nach als untere Schranke zu verstehen - das 1,5-fache zu brauchen sicher auch locker möglich. Vorbereitungszeit für die Prüfung verhält sich ähnlich, ich denke ohne spezifisches Talent auf diesem Gebiet sind - zumindest wenn man sich nicht vollständig auf die eine LVA konzentrieren kann - 2 Wochen mindestens notwendig.

Weitere Meinung (WS2023, Bachelor an TU Wien absolviert): I did rather well in TIL (it had this course 2 years ago at the point I wrote this exam), but needed to revise quite a lot to again get an understanding of the materials. I guess it really helps to revise semantics/syntactics of FOL before the course. The subjects (intuitionistic logic, modal logic and gödel incompleteness) are new anyways so you don't need any previous knowledge. For the written exam you do not really need to understand Gödels incompleteness (it suffices to know how ADRF works - try some composed functions for your self!) - for the oral exam you should understand it rather well. In total I studied roughly a week (pretty focused) and went to most of the lectures. I think the 6 ECTs are pretty well deserved - but they grade very generously - so just "passing" should be doable in less time.

Unterlagen

Gutes Einführungsvideo zum 4. Teil: https://www.youtube.com/watch?v=O4ndIDcDSGc

• Materialien

Tipps

• Es werden immer mehr oder weniger gute Abgaben von Studierenden als "Musterlösung" im TISS veröffentlicht. Da sich die Übungsaufgaben manchmal wiederholen, hilft es, mal im TISS in alte Semester zu schauen.
• Es kommen immer alle Teilen zur mündlichen Prüfung. Einen Teil auslassen ist keine gute Idee.
• Beim 3. Teil liegt der Schwerpunkt eindeutig auf dem was im Skript steht. Foliensatz 2 und 3 (Turing Maschinen und Lambda Kalkül wurden nicht geprüft.)
• Übungsblätter selber machen, hilft für die schriftliche Prüfung.
• Bei Teil 1 und 3 gibt es eine Liste von Beweisen die zur mündlichen Prüfung kommen. Die verlangten Beweise lernen.

Verbesserungsvorschläge / Kritik

• Die Kommunikation mit den Studierenden könnte etwas verbessert werden. (Bei TISS und Email geht leider leicht was unter)
• Anmeldung zur Prüfung: man darf sich zur mündlichen Prüfung im TISS nur anmelden, wenn man die schriftliche bestanden hat und auch nur beim entsprechenden Termin. Das wurde aber schlecht kommuniziert und TISS lässt aber alle anmelden.

Materialien

Neues Material hinzufügen

E

• Exam 2022-09-13

O

• Oral Exam Questions 2023WS
• Oral Exam Questions 2022SS
• Oral Exams

S

• Solutions to old exams (details)

W

• Written Exam 2020-01
• Written Exam 2017-05