# 185.A45 Logic and Computability This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2023W 2022W 2021W 2020W 2019W 2018W 2017W 2016W 2015W 2014W 2013W 2012W 2012S

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

## Properties

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

## 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

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 Tuesday, October 4th 2022, 15:00. If you cannot join this first meeting, please send us an email.

## Course dates

DayTimeDateLocationDescription
Tue15:00 - 17:0004.10.2022 - 24.01.2023EI 5 Hochenegg HS Lecture
Thu13:00 - 15:0006.10.2022 - 15.12.2022EI 5 Hochenegg HS Lecture
Thu15:00 - 17:0006.10.2022 - 15.12.2022EI 5 Hochenegg HS Exercise
Logic and Computability - Single appointments
DayDateTimeLocationDescription
Tue04.10.202215:00 - 17:00EI 5 Hochenegg HS Lecture
Thu06.10.202213:00 - 15:00EI 5 Hochenegg HS Lecture
Thu06.10.202215:00 - 17:00EI 5 Hochenegg HS Exercise
Tue11.10.202215:00 - 17:00EI 5 Hochenegg HS Lecture
Thu13.10.202213:00 - 15:00EI 5 Hochenegg HS Lecture
Thu13.10.202215:00 - 17:00EI 5 Hochenegg HS Exercise
Tue18.10.202215:00 - 17:00EI 5 Hochenegg HS Lecture
Thu20.10.202213:00 - 15:00EI 5 Hochenegg HS Lecture
Thu20.10.202215:00 - 17:00EI 5 Hochenegg HS Exercise
Tue25.10.202215:00 - 17:00EI 5 Hochenegg HS Lecture
Thu27.10.202213:00 - 15:00EI 5 Hochenegg HS Lecture
Thu27.10.202215:00 - 17:00EI 5 Hochenegg HS Exercise
Thu03.11.202213:00 - 15:00EI 5 Hochenegg HS Lecture
Thu03.11.202215:00 - 17:00EI 5 Hochenegg HS Exercise
Tue08.11.202215:00 - 17:00EI 5 Hochenegg HS Lecture
Thu10.11.202213:00 - 15:00EI 5 Hochenegg HS Lecture
Thu10.11.202215:00 - 17:00EI 5 Hochenegg HS Exercise
Thu17.11.202213:00 - 15:00EI 5 Hochenegg HS Lecture
Thu17.11.202215:00 - 17:00EI 5 Hochenegg HS Exercise
Tue22.11.202215:00 - 17:00EI 5 Hochenegg HS Lecture
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
Thu11:00 - 13:0027.06.2024EI 1 Petritsch HS written06.06.2024 00:00 - 26.06.2024 23:59TISSLast (4th) written exam
Wed - 15.01.2025written20.12.2024 10:00 - 13.01.2025 12:00TISSFirst written exam

## Course registration

Begin End Deregistration end
11.08.2022 12:00 04.12.2022 23:00 04.12.2022 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.

English