Математическая логика и теория алгоритмов (ФИТ)

Лекторы
(в скобках для каждой программы обучения, на которой лектор читает курс, — количество часов лекций по учебному плану)

Пальчунов Дмитрий Евгеньевич (информатика и вычислительная техника (бакалавриат) 64 час.)

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

Автор: зав.кафедрой общей информатики ФИТ НГУ, д.ф.-м.н. Пальчунов Д.Е.

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

Кафедра общей информатики

Contents


Цели освоения дисциплины

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

Место дисциплины в структуре образовательной программы

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

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

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

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

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

В результате освоения дисциплины обучающийся должен:

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

Структура и содержание дисциплины

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

Структура

Таблица

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

1 семестр

  • Основы теории множеств

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

  • Логика высказываний

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

  • Логика предикатов

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

  • Основы теории алгоритмов

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

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

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

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

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

  • Булевы алгебры

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

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

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

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

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

2 семестр

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

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

  • Секвенциальное исчисление предикатов

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

  • Теорема о полноте

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

  • Исчисление предикатов гильбертовского типа

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

  • Основы теории моделей

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

  • Машины Тьюринга

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

  • Универсальные рекурсивные функции

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

  • Клиниевская нумерация

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

  • Рекурсивные и рекурсивно-перечислимые множества

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

  • Алгоритмически разрешимые и неразрешимые проблемы

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

Образовательные технологии

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

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

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

Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспече-ние самостоятельной работы студентов

(ВНИМАНИЕ, возможно перемещение части вопросов из одного семестра в другой, в зависимости от фактически прочитанного объёма за 1-й семестр)

Вопросы к экзамену (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. Теорема Геделя о неполноте.

Учебно-методическое и информационное обеспечение дисциплины

а) основная литература

  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 с.
Добавить в избранное