МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение высшего профессионального образования

«Новосибирский государственный университет» (НГУ)

Факультет информационных технологий

УТВЕРЖДАЮ

_

« _» _ 20_г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

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

НАПРАВЛЕНИЕ ПОДГОТОВКИ 230100 «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»

Квалификация (степень) выпускника Бакалавр Форма обучения очная Новосибирск Программа дисциплины «Математическая логика и теория алгоритмов» составлена в соответствии с требованиями ФГОС ВПО к структуре и результатам освоения основных образовательных программ бакалавриата по математическому и естественнонаучному циклу по направлению подготовки «Информатика и вычислительная техника», а также задачами, стоящими перед Новосибирским государственным университетом по реализации Программы развития НГУ.

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

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

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

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

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

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

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

Владеет навыками формального представления содержательных знаний средствами формальных языков ПК-65 Может разрабатывать интеллектуальные системы, включая агентов, действующих в вероятностной среде, систем принятия решений, аниматов ПК-66 Умеет применять методы теории информации и методы обработки изображений и сигналов в различных областях В результате освоения дисциплины обучающийся должен:

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

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

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

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

рии множеств сказываний рии алгоритмов функции.

множества ние высказываний.

секвенций.

секвенций.

алгебраических систем.

ние предикатов предикатов гильбертовского типа рии моделей сивные функции нумерация перечислимые множества чески разрешимые и неразрешимые проблемы Содержание разделов и тем курса:

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

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

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

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

Отношения и функции.

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

Мощность множества.

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

Булевы алгебры Множество-степень, понятие и основные свойства булевой алгебры. Примеры.

Атомные и безатомные элементы булевых алгебр. Конечные булевы алгебры, теорема Стоуна для конечных булевых алгебр.

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

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

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

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

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

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

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

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

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

Основы теории моделей Обогащение модели константами. Элементарная и полная диаграммы. Подмодели и расширения, связь с универсальными и экзистенциальными формулами. Элементарные расширения и подмодели, элементарные вложения. Критерий элементарности вложения. Теоремы Ливенгейма-Скулема. Парадокс Скулема. Аксиоматизируемые классы. Теория класса и класс теории. Конечно аксиоматизируемые классы. Характеризация классов, замкнутых относительно подмоделей и расширений. Интерполяционная теорема Крейга (без доказательства) и её следствия. Явная и неявная определимость. Теорема Бета об определимости (без доказательства).

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

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

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

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

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

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

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

Текущий контроль осуществляется в форме тестов – в течение 5 минут вначале каждого семинара студенты выписывают по памяти 3-4 определения по пройденной теме. Тесты стоятся на основе формулировок определений и теорем.

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

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

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

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

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

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

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

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

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

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

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

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

в) программное обеспечение и Интернет-ресурсы: не требуется.

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