185.A45 Logic and Computability
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2023W, VU, 4.0h, 6.0EC, to be held in blocked form
TUWEL

Properties

  • Semester hours: 4.0
  • Credits: 6.0
  • Type: VU Lecture and Exercise
  • Format: Presence

Learning outcomes

After successful completion of the course, students are able to distinguish and to apply important concepts, techniques, and results of formal logic and computability theory. Moreover, students who pass the fianl exams should be able to understand and to explain connections between topics like incompleteness of arithmetical calculi, undecidabiltiy, formal provability and expressibility.

Subject of course

  • advanced aspects of classical first order logic as specification tool
  • proof systems for classical first order logic, including  soundness and completeness proofs 
  • elements of model theory (Löwenheim-Skolem, compactness, expressibility)
  • principles of automated theorem proving
  • methods for handling identity  
  • comparison of types of inference systems 
  • elements of modal logic: Kripke semantics, temporal logics 
  • elements of intuitionistic logic and constructive proofs
  •  computational aspects of logic
  • undecidabilty of first order logic and its consequences
  • models of computation (Turing machines, lambda calculus)
  • elementary recursion theory
  • Church-Turing thesis
  • incompleteness of arithmetic and its consequences 

Teaching methods

  • derivations in various different logical calculi
  • applying formal concepts to standard problem sets
  • mastering formal (mathematical) definitions
  • analysis of proofs of central results
  • mandatory exercises

Mode of examination

Immanent

Additional information

ETCS Breakdown:

6 ETCS = 150 hours

  • 38 hours:  lecture time (+ 6-8 hours repetitorium for students not having a firm previous knowledge in logic)
  • 10 hours: exercise sessions (MANDATORY)
  • 42 hours: 6  blocks of problems/exercises 
  • 60 hours: examination (preparation time)

The course will start Wednesday,  October 4th 2023, 11:00.

 

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Wed11:00 - 13:0004.10.2023 - 17.01.2024EI 5 Hochenegg HS Lecture
Thu13:00 - 15:0005.10.2023 - 14.12.2023EI 5 Hochenegg HS Lecture
Thu15:00 - 17:0005.10.2023 - 19.10.2023HS 14A Günther Feuerstein Repetitorium
Fri13:00 - 17:0013.10.2023Seminarraum FAV EG C (Seminarraum Gödel) Exercises
Fri13:00 - 17:0013.10.2023Seminarraum 384 Exercises
Thu15:00 - 17:0009.11.2023 - 21.12.2023EI 5 Hochenegg HS Exercise
Fri13:00 - 17:0010.11.2023Seminarraum 384 Exercises
Fri13:00 - 17:0024.11.2023 - 15.12.2023Seminarraum 384 Exercises
Thu13:00 - 15:0021.12.2023EI 5 Hochenegg HS Lecture
Logic and Computability - Single appointments
DayDateTimeLocationDescription
Wed04.10.202311:00 - 13:00EI 5 Hochenegg HS Lecture
Thu05.10.202313:00 - 15:00EI 5 Hochenegg HS Lecture
Thu05.10.202315:00 - 17:00HS 14A Günther Feuerstein Repetitorium
Wed11.10.202311:00 - 13:00EI 5 Hochenegg HS Lecture
Thu12.10.202313:00 - 15:00EI 5 Hochenegg HS Lecture
Thu12.10.202315:00 - 17:00HS 14A Günther Feuerstein Repetitorium
Fri13.10.202313:00 - 17:00Seminarraum FAV EG C (Seminarraum Gödel) Exercises
Fri13.10.202313:00 - 17:00Seminarraum 384 Exercises
Wed18.10.202311:00 - 13:00EI 5 Hochenegg HS Lecture
Thu19.10.202313:00 - 15:00EI 5 Hochenegg HS Lecture
Thu19.10.202315:00 - 17:00HS 14A Günther Feuerstein Repetitorium
Wed25.10.202311:00 - 13:00EI 5 Hochenegg HS Lecture
Wed08.11.202311:00 - 13:00EI 5 Hochenegg HS Lecture
Thu09.11.202313:00 - 15:00EI 5 Hochenegg HS Lecture
Thu09.11.202315:00 - 17:00EI 5 Hochenegg HS Exercise
Fri10.11.202313:00 - 17:00Seminarraum 384 Exercises
Thu16.11.202313:00 - 15:00EI 5 Hochenegg HS Lecture
Thu16.11.202315:00 - 17:00EI 5 Hochenegg HS Exercise
Wed22.11.202311:00 - 13:00EI 5 Hochenegg HS Lecture
Thu23.11.202313:00 - 15:00EI 5 Hochenegg HS Lecture
Course is held blocked

Examination modalities

  • solutions to 6 blocks of exercises - independent solutions expected
  • mandatory attendance in 6:exercise classes
  • written exam
  • oral exam

NOTE: This year, the participants are required to solve 6 blocks of exercises. The solutions are to be uploaded in TUWEL and might have to be presented on the blackboard.

Mandatory exercise sessions: October 13th, November 10th, November 24th, December 1rst, December 15th and December 21rst, 2023.

The exercise part has to completed postively in order to be admitted for the exam.

Exams

DayTimeDateRoomMode of examinationApplication timeApplication modeExam
Tue13:00 - 15:0028.05.2024EI 5 Hochenegg HS written03.04.2024 10:00 - 27.05.2024 23:59TISSL&C 3rd written exam

Course registration

Begin End Deregistration end
10.08.2023 12:00 03.12.2023 23:00 06.11.2023 23:00

Curricula

Study CodeObligationSemesterPrecon.Info
066 931 Logic and Computation Mandatory1. Semester

Literature

(see lecture slides for additional literature)

Previous knowledge

Knowledge of classical propositional logic and of basic concepts of classical first order logic (logical consequence, interpretations and model structures, satisfiability versus validity, acquaintance with various proof systems), a firm understanding of the syntax/semantic distinction, some experience with formal specification, acquaintance with a range of different programming paradigms (imperative, functional, logical),  and automata theory (finite automata, pushdown automata, Turing machines)


NB: If you don't have a firm background in logic yet, you are asked to join special repetitorium classes, which are open to all participants.

Preceding courses

Continuative courses

Language

English