Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«Новосибирский государственный университет» (НГУ)
Факультет информационных технологий
Кафедра общей информатики
ПРОГРАММА
ДИСЦИПЛИНЫМатематическая логика
ЦИКЛ* ЕН — Общие математические и естественнонаучные дисциплины
НАПРАВЛЕНИЕ ПОДГОТОВКИ БАКАЛАВРОВ 230100.62 «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»
Автор Пальчунов Дмитрий Евгеньевич, д.ф.-м.н., доцент
(ФИО, ученая степень, ученое звание)
Новосибирск 2009
* Наименование цикла дисциплин в соответствии с ГОС ВПО
Программа дисциплины «Математическая логика» составлена в соответствии с требованиями к обязательному минимуму содержания и уровню подготовки бакалавра по циклу «Общих математических и естественнонаучных дисциплин» Федеральных государственных образовательных стандартов высшего профессионального образования по направлению 230100.62 «Информатика и вычислительная техника».
Цели и задачи дисциплины (курса)
Дисциплина (курс) «Математическая логика» имеет своей целью ознакомление студентов с основами теории множеств, теории моделей и теории вычислимости. Основной целью освоения дисциплины является приобретение студентами теоретических знаний и навыков решения задач по теории множеств, логике высказываний, логике предикатов, теории моделей, теории алгоритмов и теории вычислимости, а также компетенций по формализации дискретных задач а математическом языке.
Для достижения поставленной цели выделяются задачи курса:
1) изучение теоретической части курса в соответствии с программой
2) решение цикла задач по курсу в соответствии с программой
3) сдача коллоквиума
4) выполнение контрольных работ
5) сдача экзаменов в соответствии с учебным планом.
Требования к уровню освоения содержания дисциплины
В результате освоения дисциплины студент должен:
Иметь представление о месте и роли изучаемой дисциплины среди других наук;
Знать содержание программы курса, основные понятия и теоремы теории множеств, теории моделей, теории алгоритмов
Уметь решать задачи по математической логике, теории моделей и теории алгоритмов.
Объем дисциплины и виды учебной работы
| Вид учебной работы | Всего часов | Семестры | |
| 1 | 2 | ||
| Общая трудоемкость дисциплины | |||
| Аудиторные занятия, в том числе: | |||
| Лекции | |||
| Семинары | |||
| Лабораторные работы | - | - | - |
| Самостоятельная работа, в том числе: | |||
| Курсовой проект | |||
| Реферат | |||
| Расчетные работы | |||
| Другие виды самостоятельной работы | |||
| Выполнение домашних заданий | |||
| Подготовка к контрольным работам | |||
| подготовка к коллоквиуму | |||
| Вид промежуточного контроля | экзамен | экзамен |
Содержание дисциплины
4.1. Новизна курса (научная, содержательная; сравнительный анализ с подобными курсами в России и за рубежом).
Программа курса, содержание и методика изложения материала являются новыми. Они ориентированы на будущих специалистов в области информационных технологий. При объёме материала не меньшем, чем на механико-математическом факультете, акцент делается не на приобретение навыков получения новых математических результатов, а на применение теоретических результатов при решении сложных прикладных задач.
4.2. Тематический план курса (распределение часов по видам учебной работы).
Семестр 1
| № п/п | Наименование тем и разделов | ВСЕГО (часов) | Аудиторные занятия (часов), в том числе | Самостоятельная работа (часов) | ||
| Лекции | Семинары | Лаб. работы | ||||
| Основы теории множеств | ||||||
| Логика высказываний | ||||||
| Логика предикатов | ||||||
| Основы теории алгоритмов | ||||||
| Отношения и функции. | ||||||
| Мощность множества | ||||||
| Булевы алгебры | ||||||
| Секвенциальное исчисление высказываний. | ||||||
| Семантика исчисления секвенций. | ||||||
| Семантика исчисления секвенций. | ||||||
| Гомоморфизм и изоморфизм алгебраических систем. | ||||||
| Итого по курсу: |
Семестр 2
| № п/п | Наименование тем и разделов | ВСЕГО (часов) | Аудиторные занятия (часов), в том числе | Самостоятельная работа (часов) | ||
| Лекции | Семинары | Лаб. работы | ||||
| Секвенциальное исчисление предикатов | ||||||
| Теорема о полноте | ||||||
| Исчисление предикатов гильбертовского типа | ||||||
| Основы теории моделей | ||||||
| Машины Тьюринга | ||||||
| Универсальные рекурсивные функции | ||||||
| Клиниевская нумерация | ||||||
| Рекурсивные и рекурсивно-перечислимые множества | ||||||
| Алгоритмически разрешимые и неразрешимые проблемы | ||||||
| Скулемовские и эрбрановы нормальные формы. Теорема Эрбрана | ||||||
| Итого по курсу: | - |
4.3. Содержание разделов и тем курса.
Семестр
- Основы теории множеств
Множества и операции над ними. Простейшие теоретико-множественные тождества.
- Логика высказываний
Язык логики высказываний. Понятие формулы. Таблицы истинности. Эквивалентность формул. Связь теоретико-множественных тождеств и тождеств логики высказываний. Основные тождества логики высказываний и теории множеств. Нормальные формы. Приведение формулы к СДНФ и СКНФ.
- Логика предикатов
Понятие алгебраической системы, алгебры, модели. Примеры. Термы и формулы логики предикатов. Истинность формулы на модели. Тождественно истинные и выполнимые формулы. Семантическая эквивалентность формул. Основные тождества логики предикатов.
- Основы теории алгоритмов
Понятие алгоритма. Вычислимые функции, разрешимые и перечислимые множества. Счётность множества вычислимых функций, существование невычислимых функций и неразрешимых множеств. Машины Тьюринга. Функции, вычислимые на машинах Тьюринга. Примитивно-рекурсивные, общерекурсивные и частично-рекурсивные функции.
- Отношения и функции.
Предпорядок, отношения эквивалентности и частичного порядка. Эквивалентность и разбиение, фактор-множество. Максимальные и минимальные, наибольшие и наименьшие элементы, точная верхняя и нижняя грани. Понятие решетки.
- Мощность множества.
Теорема Кантора-Бернштейна, теорема Кантора. Счётные множества. Счётность множества слов в конечном алфавите. Континуум. Несчётность множества вещественных чисел. Равномощность множества вещественных чисел и множества всех подмножеств множества натуральных чисел. Бесконечность класса бесконечных мощностей. Континуум-гипотеза и обобщённая континуум-гипотеза. Ординальные и кардинальные числа.
- Булевы алгебры
Множество-степень, понятие и основные свойства булевой алгебры. Примеры. Атомные и безатомные элементы булевых алгебр. Конечные булевы алгебры, теорема Стоуна для конечных булевых алгебр.
· Секвенциальное исчисление высказываний.
Секвенциальное исчисление высказываний. Понятие вывода. Допустимые правила вывода.
- Семантика исчисления секвенций.
Теорема о корректности. Теорема о подстановке. Теорема о замене. Теорема о существовании КНФ. Теорема о полноте исчисления секвенций. Теорема об адекватности
- Исчисление высказываний гильбертовского типа.
Теорема о дедукции (без доказательства). Теорема об эквивалентности гильбертовского и секвенциального исчислений высказываний (без доказательства).
· Гомоморфизм и изоморфизм алгебраических систем.
Гомоморфизм и изоморфизм алгебраических систем. Подсистемы. Отношение конгруэнтности, фактор-система, общая формулировка теоремы о гомоморфизмах (без доказательства).
2 семестр
- Секвенциальное исчисление предикатов
Секвенциальное исчисление предикатов, аксиомы и правила вывода. Теорема о корректности. Допустимые правила вывода. Теорема о замене. Вывод основных эквивалентностей. Приведение формулы к предваренной нормальной форме.
- Теорема о полноте
Полные теории. Теорема о существовании модели. Теорема Гёделя о полноте и теорема компактности Мальцева. Теорема Мальцева о расширении. Понятие о нестандартных моделях. Существование нестандартной модели арифметики.
- Исчисление предикатов гильбертовского типа
Исчисление предикатов гильбертовского типа. Теорема о дедукции (без доказательства). Теорема об эквивалентности гильбертовского и секвенциального исчислений предикатов (без доказательства).
- Основы теории моделей
Обогащение модели константами. Элементарная и полная диаграммы. Подмодели и расширения, связь с универсальными и экзистенциальными формулами. Элементарные расширения и подмодели, элементарные вложения. Критерий элементарности вложения. Теоремы Ливенгейма-Скулема. Парадокс Скулема. Аксиоматизируемые классы. Теория класса и класс теории. Конечно аксиоматизируемые классы. Характеризация классов, замкнутых относительно подмоделей и расширений. Интерполяционная теорема Крейга (без доказательства) и её следствия. Явная и неявная определимость. Теорема Бета об определимости (без доказательства).
- Машины Тьюринга
Правильно вычислимые функции на машинах Тьюринга. Теорема о правильной вычислимости частично-рекурсивных функций. Кодировка машин Тьюринга. Теорема о нормальной форме Клини. Эквивалентность классов вычислимых функций. Тезис Чёрча.
- Универсальные рекурсивные функции
Универсальные рекурсивные функции. Несуществование универсальной примитивно рекурсивной функции и универсальной общерекурсивной функции, существование универсальной частично рекурсивной функции.
- Клиниевская нумерация
Клиниевская нумерация. s-m-n теорема. Теорема о неподвижной точке. Теорема о рекурсии. Теорема Райса.
- Рекурсивные и рекурсивно-перечислимые множества
Операции над рекурсивными и рекурсивно перечислимыми множествами. Теорема Поста. Теорема о проекции. Теорема об эквивалентных определениях рекурсивно-перечислимых множеств. Теорема о графике. Существование рекурсивно-перечислимого, но не рекурсивного множества. Неразрешимость проблемы остановки программы.
- Алгоритмически разрешимые и неразрешимые проблемы
Формальная арифметика Пеано. Гёделевская нумерация. Представимость рекурсивных функций в арифметике Пеано. Теорема Гёделя о неполноте. Разрешимые и неразрешимые теории. Теорема Чёрча о неразрешимости логики предикатов. Теорема Гёделя о неразрешимости арифметики.
4.4. Перечень примерных контрольных вопросов и заданий для самостоятельной работы.
- Дайте определение конечной булевой алгебры. Докажите теорему Стоуна для конечных булевых алгебр.
- Докажите теорему об эквивалентных определениях Рекурсивно-перечислимых множеств.
- Докажите теорему о существовании модели, случай с равенством.
- Докажите теорему о существовании модели, случай без равенства.
4.5. Примерная тематика рефератов, курсовых работ.
Не предусмотрено.
Учебно-методическое и информационное обеспечение дисциплины (курса)
5.1. Примерный перечень вопросов к зачету (экзамену) по всему курсу.
Вопросы для подготовки к экзамену совпадают с темами занятий, указанными в тематическом плане. На экзамене студент получает два вопроса. В ходе приема экзамена студенту могут быть заданы дополнительные вопросы, относящиеся к другим темам. Ниже приводятся образцы экзаменационных вопросов:
1. Теорема Геделя о полноте и теорема компактности Мальцева.
2. Оператор ограниченной минимизации.
3. Секвенциальное исчисление высказываний. Теорема о полноте исчисления секвенций.
4. Существование частичной универсальной вычислимой функции.
5.2. Основная литература*.
- Ершов Ю.Л., Палютин Е.А. Математическая логика, М.: Наука. 1987. –336 с.
- Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов, М.: Физмалит. 2001. 256 с.
5.3. Дополнительная литература.
1. Гончаров С.С., Дроботун Б.Н., Никитин А.А. Методические аспекты изучения алгебраических систем высшем учебном заведении. Новосибирск: НГУ, 2007.