# Dependence logic, spring 2011

### Lecturer

### Scope

5 cu.

### Type

Advanced studies

### Description

Dependence logic adds the concept of dependence to first-order logic by the means of new atomic dependence formulas =(x_1,…,x_n,y),

meaning that the values of the variables x_1,…,x_n completely determine the values of the variable y. Dependence logic bases its semantics in the concept of a set X of assignments satisfying a formula (rather than an individual assignment satisfying a formula, as in first-order logic).

This course discusses dependence logic in the context of finite structures. Over finite structures, various extensions of first-order logic have been studied. It is known that many of these logics correspond to interesting complexity classes in computational complexity theory. In this course we discuss dependence logic from the complexity theoretic point of view. For example, we will show that dependence logic corresponds exactly to the complexity class nondeterministic polynomial time (NP).

### Prerequisites

Mathematical logic (Matemaattinen logiikka) and finite model theory (Äärellisten mallien teoria).

### Lectures

Weeks 11-18, Monday 12-14 and Thursday 12-14 in room B321.

Easter holiday 21.-27.4.

### Contents of lectures

Supplementary notes for selected lectures (updated 4.5)

### Exam

The **Exam** will be held on Wednesday 11.5 at 12-16 in room B321.

### Bibliography

- Jouko Väänänen: Dependence Logic.

A New Approach to Independence Friendly Logic.

Series: London Mathematical Society Student Texts (No. 70).

- Jarmo Kontinen: Coherence and Complexity in Fragments of Dependence Logic.

Doctoral thesis, University of Amsterdam, 2010. (available at http://www.illc.uva.nl/Publications/reportlist.php?Series=DS)

### Registration

Did you forget to register? What to do.

### Exercises

### Exercise groups

Group |
Day |
Time |
Place |
Instructor |
---|---|---|---|---|

1. |
Tuesday |
10-12 |
C130 |
Juha Kontinen |