Програма „математическа логика професионално направление 5 Математика

1. 
   Теория на множествата  аксиоматична система на Цермело-Фрепкел. Частични и линейни наредби. Сравняване на множествата по мощност. Теорема на Кантор за степенното множество и теорема на Кантор-Шрьодер-Бернщайн.
   

2. 
   Добре наредени множества и принцип за доказване на техните свойства. Ординални числа, трансфинитна индукция и дефиниране чрез трансфинитна рекурсия. Аксиома за избора  теорема на Цермело, лема на Цорн.
   

3. 
   Класическо съждително смятане  синтаксис и семантика. Формална система от Хилбертов тип. Теорема за коректност и пълнота. Компактност на логическото следване.
   

4. 
   Класическо предикатно смятане  синтаксис и семантика. Подструктури, термално породени подструктури, ербранови структури. Достатъчност на ербрановите структури за множества от затворени универсални формули.
   

5. 
   Пренексна нормална форма. Разширения на езици и обогатяване на структури. Скулемова нормална форма. Теорема на Ербран.
   

6. 
   Формална система от Хилбертов тип за класическото предикатно смятане. Теорема на Гьодел за пълнота. Теорема за компактност и теорема на Льовенхайм-Скулем.
   

7. 
   Метод на резолюцията за класическото предикатно смятане  описание и пълнота.
   

8. 
   Примитивно рекурсивни функции. Примитивна рекурсивност на някои аритметични функции. Едновременна и възвратна рекурсия.
   

9. 
   Частично рекурсивни функции.  теорема. Теореми за универсалната функция и нормалния вид на ч. р. ф. Втора теорема за рекурсията.
   

10. 
    Рекурсивни и рекурсивно номеруеми множества. Неразрешими проблеми. Теорема на Райс-Успенски. Теорема на Раис-Шапиро.
    

11. 
    Рекурсивни оператори. Първа теорема на рекурсията.
    

12. 
    Формална аксиоматична система на Робинсън за теорията на естествените числа. Представимост на rem, qt и   функцията на Гьодел.
    

13. 
    Представимост на частично рекурсивните функции в системата на Робинсън.
    

14. 
    Гьоделева номерация на термовете и формулите в системата на Робинсън. Рекурсивна номеруемост на кодовете на изводимите в системата формули. Теорема на Гьодел за непълнота.
    

15. 
    Аритметично представими множества и функции. Теорема на Тарски за множеството от кодовете на формулите, верни в стандартния модел на аритметиката.
    

16. 
    Модални логики. Семантика на Крипке. Теореми за модалната определимост и неопределимост.
    

17. 
    Пълнота и разрешимост на минималната модална логика и някои нейни разширения.
    

ЛИТЕРАТУРА:

1. 
   Ръкопис на Тинко Тинчев по теория на множествата.
   
2. 
   Учебник по математическа логика (ръкопис). Д. Вакарелов, Т. Тинчев.
   
3. 
   Справочная книга по математической логике, I част  Теория моделей, (под редакцией Дж. Барвайса). Наука, Москва, 1982.
   
4. 
   Г. Кейслер, Ч. Чн. Теория моделей. Мир, Москва, 1977.
   
5. 
   Иван Сосков и Ангел Дичев. Теория на програмите. УИ “Св. Климент Охридски”, София, 1996.
   
6. 
   Э. Мендельсон. Введение в математическую логику. Наука, Москва, 1971.
   
7. 
   П. Петков. Елементи на математическата логика в задачи. УИ “Св. Климент Охридски”, София, 1986.
   
8. 
   И. Лавров, Л. Максимова. Задачи по теории множеств, математической логике и теории алгоритмов. Наука, москва, 1984.
   

Д2. С. Клини. Математическая логика. Мир, Москва, 1973.

Д3. Н. Катленд. Вычислимость. Введение в теорию рекурсивных функций. Мир, Москва, 1983.

Д4. Ч. Чэнь, Р. Ли. Математическая логика и автоматическое доказательство теорем. Наука, Москва, 1983.

Д5. Справочная книга по математической логике (в четырех частях, под редакцией Дж. Барвайса). Наука, Москва, 1982  1983.

Д6. Александра Соскова и Стела Николова. Теория на програмите в задачи. Софтех, София, 1997.

Д7. Димитър Скордев. Записки по математическа логика. http://fmi.uni-sofia.bg/fmi/logic/skordev/ln/ml

Изпитът е писмен и устен. На писмения изпит се дава един въпрос от конспекта и една задача. Устният изпит е събеседване по задачите и въпосите от конспекта.

Типовете и трудността на даваните задачи се илюстрират от тези в книгите:
[7]  § 2 (зад. 53  56, 58  59), § 3 (зад. 61, 93  98), § 5 (зад. 3  4, 17, 29  32), § 7 (зад. 25  26).

[8]  част II § 5 (зад. 11  14, 22  44), § 9 (зад. 5  13, 15  22), част III § 3 (зад. 18  20), § 4 (зад. 10  13, 28, 34  36).