##### Child pages
• Dependence logic, spring 2011
Go to start of banner

# Dependence logic, spring 2011

Juha Kontinen

5 cu.

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

Course Diary

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).

### Registration

Did you forget to register? What to do.

### Exercises

Problem set 1 (due 29.3)

Problem set 2

Problem set 3

Problem set 4

Problem set 5 (due 3.5)

Group

Day

Time

Place

Instructor

1.

Tuesday

10-12

C130

Juha Kontinen

• No labels