Description:
This course aims at introducing the basic concepts, results and tools from Classical Logic and Model Theory. The main focus will be on Classical First and Second Order Logics and on Modal Logics. We will formally define various metamathematical concepts such as syntax, semantics, truth, provability, completeness and complete axiomatizations, compactness, decidability, quantification and their relation to the concepts of theoretical computer science such as transition systems, bisimulation, operational semantics, concurrency. With some of these concepts the students are already familiar from more specific courses and they are already using some of them in their research. The role of this course is to present these concepts in a general framework and to clarify the spectrum of their use and applicability.
The students attending the course are expected to have basic working knowledge of discrete mathematics and theoretical computer science.
The structure of the course:
I. An introduction to Classical Logic and Model Theory
I.1. Formal Theories
I.2. Propositional Logic (PL)
I.2.1 Syntax and Semantics, truth tables
I.2.2 Conjunctive and disjunctive normal forms
I.2.3 Proof theories for PL
I.2.4. Completeness and compactness
I.3. First Order Logic (FOL)
I.3.1. Syntax and Semantics
I.3.2. Axiomatization
I.3.3. Completeness and Compactness
I.3.4. Lowenheim-Skolem Theorems
I.3.5. Henkin’s constants and the relation to PL
I.4. Monadic Second Order Logic and finite state machines
II. Modal Logic and its Model Theory
II.1. Kripke structures and transition systems
II.2. Bisimulations and zig-zag morphisms
II.3. The standard translation into FOL and SOL
II.4. Model constructions
II.5. Bisimulation and invariance
II.6. Classical truth-preserving constructions
II.7. Axiomatizations and Weak Completeness
II.7.1. Axiomatic systems
II.7.2. Finite model property
II.7.3. Canonical models and Strong Completeness
II.7.4. The filtration method
Organizer:
Radu Mardare, Associate Professor (Aalborg University), email: mardare@cs.aau.dk
Lecturers:
Radu Mardare, Associate Professor (Aalborg University)
ECTS:
2.5
Time:
11-15 November 2013
Place:
Aalborg University
Zip code:
9220
City:
Aalborg
Number of seats:
Deadline:
October 21, 2013
Important information concerning PhD courses
We have over some time experienced problems with no-show for both project and general courses. It has now reached a point where we are forced to take action. Therefore, the Doctoral School has decided to introduce a no-show fee of DKK 5,000 for each course where the student does not show up. Cancellations are accepted no later than 2 weeks before start of the course. Registered illness is of course an acceptable reason for not showing up on those days. Furthermore, all courses open for registration approximately three months before start. This can hopefully also provide new students a chance to register for courses during the year. We look forward to your registrations.