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.

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

Properties

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

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

Mode of examination

Immanent

Additional information

ETCS Breakdown:

6 ETCS = 150 hours

  • 38 hours:  lecture time (+ 8 hours repetitorium  for students not having a firm previous knowledge in logic)
  • 52 hours: 4 blocks of problems/exercises 
  • 60 hours: examination (preparation time)

The course will start Friday, October 4th, 10:00.

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Tue14:00 - 16:0001.10.2019 - 28.01.2020FAV Hörsaal 1 Logic and Computability
Thu11:00 - 13:0003.10.2019 - 12.12.2019FAV Hörsaal 1 Logic and Computability
Fri10:00 - 12:0004.10.2019 - 13.12.2019FAV Hörsaal 1 Logic and Computability
Logic and Computability - Single appointments
DayDateTimeLocationDescription
Tue01.10.201914:00 - 16:00FAV Hörsaal 1 Logic and Computability
Thu03.10.201911:00 - 13:00FAV Hörsaal 1 Logic and Computability
Fri04.10.201910:00 - 12:00FAV Hörsaal 1 Logic and Computability
Tue08.10.201914:00 - 16:00FAV Hörsaal 1 Logic and Computability
Thu10.10.201911:00 - 13:00FAV Hörsaal 1 Logic and Computability
Fri11.10.201910:00 - 12:00FAV Hörsaal 1 Logic and Computability
Tue15.10.201914:00 - 16:00FAV Hörsaal 1 Logic and Computability
Thu17.10.201911:00 - 13:00FAV Hörsaal 1 Logic and Computability
Fri18.10.201910:00 - 12:00FAV Hörsaal 1 Logic and Computability
Tue22.10.201914:00 - 16:00FAV Hörsaal 1 Logic and Computability
Thu24.10.201911:00 - 13:00FAV Hörsaal 1 Logic and Computability
Fri25.10.201910:00 - 12:00FAV Hörsaal 1 Logic and Computability
Tue29.10.201914:00 - 16:00FAV Hörsaal 1 Logic and Computability
Thu31.10.201911:00 - 13:00FAV Hörsaal 1 Logic and Computability
Tue05.11.201914:00 - 16:00FAV Hörsaal 1 Logic and Computability
Thu07.11.201911:00 - 13:00FAV Hörsaal 1 Logic and Computability
Fri08.11.201910:00 - 12:00FAV Hörsaal 1 Logic and Computability
Tue12.11.201914:00 - 16:00FAV Hörsaal 1 Logic and Computability
Thu14.11.201911:00 - 13:00FAV Hörsaal 1 Logic and Computability
Tue19.11.201914:00 - 16:00FAV Hörsaal 1 Logic and Computability
Course is held blocked

Examination modalities

  • solutions to 4 blocks of exercises - to be worked out self-reliantly
  • written exam
  • oral exam

Exams

DayTimeDateRoomMode of examinationApplication timeApplication modeExam
Fri09:30 - 10:3022.01.2021 192-5, Favoritenstr. 9-11, 3rd floor, staircase I or IIoral19.01.2021 16:00 - 21.01.2021 23:55TISS1st oral exam
Fri12:30 - 15:3022.01.2021 192-5, Favoritenstr. 9-11, 3rd floor, staircase I or IIoral19.01.2021 16:00 - 21.01.2021 23:55TISS1st oral exam
Tue12:00 - 14:0026.01.2021FAV Hörsaal 1 written02.01.2021 08:00 - 25.01.2021 23:00TISS1st written exam
Fri - 19.03.2021written04.03.2021 14:00 - 18.03.2021 23:59TISS2nd written exam
Mon10:00 - 15:0021.06.2021 GoToMeetingwritten25.05.2021 13:00 - 19.06.2021 13:00TISSWritten and Oral exam (Part I on line)
Wed10:00 - 13:0023.06.2021 GoToMeetingwritten25.05.2021 13:00 - 19.06.2021 13:00TISSWritten and Oral exam (Part I on line)
Wed14:00 - 19:0023.06.2021 GoToMeetingwritten25.05.2021 13:00 - 18.06.2021 13:00TISSWritten and Oral exam (Part II on line)
Thu11:00 - 14:0024.06.2021 GoToMeetingwritten25.05.2021 13:00 - 18.06.2021 13:00TISSWritten and Oral exam (Part II on line)

Course registration

Begin End Deregistration end
15.08.2019 12:00 08.12.2019 23:00 08.12.2019 23:00

Curricula

Study CodeSemesterPrecon.Info
066 931 Logic and Computation 1. 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