Программа учебного курса

«Математическая логика и теория алгоритмов»

Программа курса (дисциплины) «Математическая логика и теория алгоритмов» составлена

в соответствии с требованиями к обязательному минимуму содержания и уровню подготовки дипломированного бакалавра по циклу «Математических и естественнонаучных дисциплин» по специальности/направлению 230100.62 «Информатика и вычислительная техника», а также задачами, стоящими перед Новосибирским государственным университетом по реализации Программы развития НГУ.

Автор: д.ф.-м.н., доцент Пальчунов Д.Е.

Факультет информационных технологий Кафедра общей информатики 1. Цели освоения дисциплины (курса) Дисциплина (курс) «Математическая логика» имеет своей целью ознакомление студентов с основами теории множеств, теории моделей, теории доказательств и теории вычислимости. Основной целью освоения дисциплины является: приобретение студентами теоретических знаний и навыков решения задач по теории множеств, логике высказываний, логике предикатов, исчислению высказываний и исчислению предикатов, теории моделей, теории алгоритмов и теории вычислимости; приобретение студентами навыков и компетенций по формализации на строгом математическом языке знаний, относящихся к различным предметным областям, возникающих в этих областях проблем и задач; овладение методами построения дискретных моделей предметных областей.

2. Место дисциплины в структуре образовательной программы Дисциплина (курс) «Математическая логика и теория алгоритмов» относится к вариативной части цикла математических и естественнонаучных дисциплин ОП бакалавра.

Содержание дисциплины является обязательным минимум для последующих курсов: «Дискретная математика», «Введение в теорию кодирования», «Логические основы программирования», «Методы трансляции и компиляции», «Объектно-ориентированное программирование», «Объектно-ориентированный анализ и дизайн», «Операционные системы», «Цифровая схемотехника», «Логические методы в инженерии знаний», «Формальные методы программной инженерии», «Анализ алгоритмов», «Интеллектуальные системы».

3. Компетенции обучающегося, формируемые в результате освоения дисциплины:

Дисциплина направлена на выработку следующих компетенций:

ОК-1 владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения ОК-2 умеет логически верно, аргументировано и ясно строить устную и письменную речь ОК-6 стремится к саморазвитию, повышению своей квалификации и мастерства ОК-10 использует основные законы естественнонаучных дисциплин в профессиональной деятельности, применяет методы математического анализа и моделирования, теоретического и экспериментального исследования ОК-11 осознает сущность и значение информации в развитии современного общества; владеет основными методами, способами и средствами получения, хранения, переработки информации ПК-26 Владеет теоретическими основами программирования, основами логического и декларативного программирования ПК-28 Владеет понятиями синтаксиса и семантики формальных языков. Владеет навыками формального представления содержательных знаний средствами формальных языков ПК-65 Может разрабатывать интеллектуальные системы, включая агентов, действующих в вероятностной среде, систем принятия решений, аниматов ПК-66 Умеет применять методы теории информации и методы обработки изображений и сигналов в различных областях В результате освоения дисциплины обучающийся должен:

Знать основные понятия и теоремы из теории множеств, логики высказываний, логики предикатов, теории доказательств, теории моделей, теории алгоритмов и теории вычислимости;

Уметь решать задачи по математической логике, теории моделей теории доказательств, и теории алгоритмов, уметь переводить на формальный язык содержательные математические утверждения, уметь проверять истинность утверждений, записанных на формальном языке;

Владеть методами формализации на строгом математическом языке знаний, относящихся к различным предметным областям, возникающих в этих областях проблем и задач, владеть методами построения дискретных моделей предметных областей.

4. Структура и содержание дисциплины Общая трудоемкость дисциплины составляет 6 зачетных единиц, 216 часов.

Виды учебной работы, включая само- Формы текуРаздел стоятельную работу студентов и трудо- щего контроля № дисциплины емкость (в часах) успеваемости Неделя семестра п/п (по неделям сеСеместр местра) Форма промежуточной аттестации (по семестрам) Самостоятельная Экзамен Лекции Семинары работа 1 Основы теории 1 2 2 - множеств 2 Логика выска- 2-3 4 4 1 зываний 3 Логика преди- 4 2 2 - катов 4 Основы теории 5-6 4 4 1 алгоритмов 5 Отношения и 7 2 2 1 функции.

6 Мощность мно- 8 2 2 1 жества 7 Булевы алгебры 9-10 4 4 1 Секвенциальное 11-12 4 4 1 исчисление высказываний.

гильбертовского множества Содержание разделов и тем курса:

1 семестр Множества и операции над ними. Простейшие теоретико-множественные тождества.

Язык логики высказываний. Понятие формулы. Таблицы истинности. Эквивалентность формул.

Связь теоретико-множественных тождеств и тождеств логики высказываний. Основные тождества логики высказываний и теории множеств. Нормальные формы. Приведение формулы к СДНФ и СКНФ.

Понятие алгебраической системы, алгебры, модели. Примеры. Термы и формулы логики предикатов. Истинность формулы на модели. Тождественно истинные и выполнимые формулы. Семантическая эквивалентность формул. Основные тождества логики предикатов.

Основы теории алгоритмов Понятие алгоритма. Вычислимые функции, разрешимые и перечислимые множества. Счётность множества вычислимых функций, существование невычислимых функций и неразрешимых множеств. Машины Тьюринга. Функции, вычислимые на машинах Тьюринга. Примитивнорекурсивные, общерекурсивные и частично-рекурсивные функции.

Предпорядок, отношения эквивалентности и частичного порядка. Эквивалентность и разбиение, фактор-множество. Максимальные и минимальные, наибольшие и наименьшие элементы, точная верхняя и нижняя грани. Понятие решетки.

Теорема Кантора-Бернштейна, теорема Кантора. Счётные множества. Счётность множества слов в конечном алфавите. Континуум. Несчётность множества вещественных чисел. Равномощность множества вещественных чисел и множества всех подмножеств множества натуральных чисел.

Бесконечность класса бесконечных мощностей. Континуум-гипотеза и обобщённая континуумгипотеза. Ординальные и кардинальные числа.

Множество-степень, понятие и основные свойства булевой алгебры. Примеры. Атомные и безатомные элементы булевых алгебр. Конечные булевы алгебры, теорема Стоуна для конечных булевых алгебр.

Секвенциальное исчисление высказываний.

Секвенциальное исчисление высказываний. Понятие вывода. Допустимые правила вывода.

Семантика исчисления секвенций.

Теорема о корректности. Теорема о подстановке. Теорема о замене. Теорема о существовании КНФ. Теорема о полноте исчисления секвенций. Теорема об адекватности. Исчисление высказываний гильбертовского типа.

2 семестр Гомоморфизм и изоморфизм алгебраических систем.

Гомоморфизм и изоморфизм алгебраических систем. Подсистемы. Отношение конгруэнтности, фактор-система, общая формулировка теоремы о гомоморфизмах (без доказательства).

Секвенциальное исчисление предикатов Секвенциальное исчисление предикатов, аксиомы и правила вывода. Теорема о корректности. Допустимые правила вывода. Теорема о замене. Вывод основных эквивалентностей. Приведение формулы к предваренной нормальной форме.

Полные теории. Теорема о существовании модели. Теорема Гёделя о полноте и теорема компактности Мальцева. Теорема Мальцева о расширении. Понятие о нестандартных моделях. Существование нестандартной модели арифметики.

Исчисление предикатов гильбертовского типа Исчисление предикатов гильбертовского типа. Теорема о дедукции (без доказательства). Теорема об эквивалентности гильбертовского и секвенциального исчислений предикатов (без доказательства).

Основы теории моделей Обогащение модели константами. Элементарная и полная диаграммы. Подмодели и расширения, связь с универсальными и экзистенциальными формулами. Элементарные расширения и подмодели, элементарные вложения. Критерий элементарности вложения. Теоремы Ливенгейма-Скулема.

Парадокс Скулема. Аксиоматизируемые классы. Теория класса и класс теории. Конечно аксиоматизируемые классы. Характеризация классов, замкнутых относительно подмоделей и расширений.

Интерполяционная теорема Крейга (без доказательства) и её следствия. Явная и неявная определимость. Теорема Бета об определимости (без доказательства).

Правильно вычислимые функции на машинах Тьюринга. Теорема о правильной вычислимости частично-рекурсивных функций. Кодировка машин Тьюринга. Теорема о нормальной форме Клини. Эквивалентность классов вычислимых функций. Тезис Чёрча.

Универсальные рекурсивные функции Универсальные рекурсивные функции. Несуществование универсальной примитивно рекурсивной функции и универсальной общерекурсивной функции, существование универсальной частично рекурсивной функции.

Клиниевская нумерация Клиниевская нумерация. s-m-n теорема. Теорема о неподвижной точке. Теорема о рекурсии. Теорема Райса.

Рекурсивные и рекурсивно-перечислимые множества Операции над рекурсивными и рекурсивно перечислимыми множествами. Теорема Поста. Теорема о проекции. Теорема об эквивалентных определениях рекурсивно-перечислимых множеств.

Теорема о графике. Существование рекурсивно-перечислимого, но не рекурсивного множества.

Неразрешимость проблемы остановки программы.

Алгоритмически разрешимые и неразрешимые проблемы Формальная арифметика Пеано. Гёделевская нумерация. Представимость рекурсивных функций в арифметике Пеано. Теорема Гёделя о неполноте. Разрешимые и неразрешимые теории. Теорема Чёрча о неразрешимости логики предикатов. Теорема Гёделя о неразрешимости арифметики.

5. Образовательные технологии Рекомендуется перед посещением семинаров и лекций предварительно ознакомиться с программой курса и семинаров. Перед каждым семинаром желательно изучить материал последней лекции. Домашние задания выполняются в течение семестра после каждого семинара.

На семинарских занятиях используются технологии мониторинга качества образования студентов: опросные методы, анализ выполнения домашних заданий, тестирование.

6. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспечение самостоятельной работы студентов Вопросы к экзамену (1 семестр):

1. Множества, операции над множествами.

2. Логика высказываний: таблицы истинности, понятия формулы, тождественно истинной, тождественно ложной, выполнимой и опровержимой формулы.

3. Логика высказываний: таблицы истинности, понятия формулы, эквивалентности формул.

4. Выражение теоретико-множественных операций через логические связки 5. ДНФ, КНФ, СДНФ, СКНФ 6. Понятие алгебраической системы 7. Термы и формулы логики предикатов 8. Истинность формул на модели 9. Семантическая эквивалентность формул 10. Предваренная нормальная форма 11. Отношения и функции 12. Свойства бинарных отношений 13. Отношения эквивалентности.

14. Отношения порядка. Упорядоченные множества 15. Точная нижняя грань и точная верхняя грань. Решетки.

16. Определение булевой алгебры. Примеры булевых алгебр.

17. Свойства булевых алгебр.

18. Атомные и безатомные булевы алгебры 19. Теорема Стоуна для конечной булевой алгебры.

20. Равномощные множества. Теорема Кантора-Бернштейна.

21. Конечные и бесконечные множества. Теорема Кантора.

22. Счетные множества 23. Континуальные множества 24. Континуум гипотеза 25. Ординалы и кардиналы.

26. Машина Тьюринга 27. ЧРФ, ПРФ, ОРФ.

28. Канторовская нумерация.

29. Секвенциональное исчисление высказываний 30. Семантика исчисления секвенций. Теорема о корректности.

31. Теорема о замене в исчислении высказываний 32. Теорема о полноте секвенционального исчисления высказываний 33. Исчисление высказываний гильбертовского типа.

34. Гомоморфизмы, изоморфизмы.

35. Подмодель.

36. Теорема о существовании наименьшей подмодели 37. Теорема о модели, порожденной множеством замкнутых термов 38. Сохранение истинности формул на подмоделях 39. Отношение конгруэнции. Теорема о факторизации 40. Теорема о сильных эпиморфизмах 41. Основная теорема о гомоморфизмах 42. Секвенциональное исчисление предикатов 43. Семантика исчисления секвенций. Теорема о корректности 44. Теорема о замене в исчислении предикатов.

45. Приведение формулы к предваренной нормальной форме 46. Противоречивые, непротеречивые множества формул. Теории, полные теории Вопросы к экзамену (2 семестр):

1. Противоречивые, непротиворечивые множества формул. Теории, полные теории.

2. Теорема о существовании модели. Случай с равенством.

3. Теорема о существовании модели. Случай без равенства 4. Теорема Мальцева о компактности 5. Теорема о полноте 6. Теорема Мальцева о расширении 7. Теорема о нестандартной арифметике 8. Исчисление предикатов гильбертовского типа.

9. Нумерация машин Тьюринга 10. Основная теорема о вычислимых функциях 11. Тезис Черча 12. Универсальные функции 13. Не существование универсальной ПРФ и ОРФ.

14. Существование универсальной ОРФ 15. Клиниевские универсальные функции 16. s-m-n-теорема 17. Теорема о неподвижной точке 18. Теорема Райса.

19. Рекурсивные и рекурсивно перечислимые множества. Операции над РМ и РПМ.

20. Теорема Поста 21. Теорема об эквивалентных определениях РПМ 22. Теорема о существовании РПМ не РМ 23. Теорема о составном определении.

24. Геделевская нумерация термов и формул сигнатуры Пеано 25. Предложение о перечислимости тождественно истинных формул 26. Предложение о перечислимости множества доказуемых формул 27. Теорема о полной перечислимой теории 28. Формальная арифметика Пеано 29. Теорема о представимости ОРФ в арифметике Пеано 30. Теорема Геделя о неразрешимости 31. Теорема Черча о неразрешимости 32. Теорема Геделя о неполноте.

7. Учебно-методическое и информационное обеспечение дисциплины а) основная литература:

Ершов Ю.Л., Палютин Е.А. Математическая логика, М.: Наука. 1987. –336 с.

2. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов, М.: Физмалит. 2001. 256 с.

б) дополнительная литература:

1. Гончаров С.С., Дроботун Б.Н., Никитин А.А. Методические аспекты изучения алгебраических систем высшем учебном заведении. Новосибирск: НГУ, 2007.

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

3. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем.

4. Мендельсон Э. Введение в математическую логику. М.:Наука, 1984. 319 с.

5. Верещагин Н.К., Шень А. Языки и исчисления. 2004.

6. Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. 2004.

7. Лавров И.А. Математическая логика. Учебное пособие для вузов. М.: Академия, 2006.

8. Колмогоров А.Н., Драгалин А.Г. Математическая логика. Серия "Классический университетский учебник". Изд.3, 2006, 240 с.

в) программное обеспечение и Интернет-ресурсы: 8. Материально-техническое обеспечение дисциплины _ (Указывается материально-техническое обеспечение данной дисциплины (модуля)).

Рецензент (ы) _ Программа одобрена на заседании (Наименование уполномоченного органа вуза (УМК, НМС, Ученый совет) от _ года.