МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Филиал федерального государственного бюджетного образовательного учреждения
высшего профессионального образования
«Астраханский государственный университет»
в г. Знаменске Астраханской области
«УТВЕРЖДАЮ»
Директор филиала ФГБОУ ВПО АГУ
в г. Знаменске Астраханской области
__________________В.Н.Крамаренко
Дисциплина блока общие математические и есстественнонаучные дисциплины
(название блока учебного плана)
Компонент федеральный
Кафедра математики и информатики
(название кафедры)
Математическая логика и теория алгоритмов
(дисциплина)
учебно-методический комплекс
для специальности
230201.65 Информационные системы и технологии (Знаменск)
(название специальности/ей)
1, 2
(номер курса)
Автор- составитель:
Лобейко В.И.
(ФИО авторов)
e-mail:
znamensk@aspu.ru
(адрес электронной почты)
Математическая логика и теория алгоритмов
(название дисциплины)
учебно-методический комплекс
Автор составитель
д.т.н., профессор Лобейко В.И.
(звание, ФИО)
Ответственный редактор
Зав. кафедрой математики и информатики,
профессор, Лобейко В.И.
(звание, ФИО)
учебно-методический комплекс обсужден
на заседании кафедры математики и информатики
Протокол № __16_ от __30.08_2010 г.
РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Математическая логика и теория алгоритмов. Логические исчисления, модели: исчисление высказываний; аксиомы; правило вывода; произ-водные правила вывода; тождественная истин-ность выводимых формул; непротиворечивость исчисления высказываний; теорема о полноте ис-числения высказываний; предикаты; логические операции над предикатами и их теоретико-множественный смысл; кванторы; геометриче-ский смысл квантора существования; модели; формулы; свободные и связанные переменные; истинность формул в модели, на множестве; об-щезначимые формулы; эквивалентные формулы логики предикатов; правила преобразований формул в эквивалентные; нормальная форма; ис-числение предикатов; аксиомы; правила вывода; производные правила вывода; торжественная истинность выводимых формул; непротиворечивость исчисления предикатов; формулировка теоремы о полноте исчисления предикатов.
Теорема о полноте для случая одноместных предикатов.
Вычислимые функции: машины Тьюринга; вычислимые функции; тезис Черча; примеры вычислимых функций; рекурсивные, рекурсивно перечислимые множества и их алгоритмическая характеристика; теорема Поста; примеры алгоритмически неразрешимых проблем; неразрешимость проблем самоприменимости, применимости; теорема Поста – Маркова о существовании ассоциативного исчисления с алгоритмически неразрешимой проблемой равенства.
*Теорема о неразрешимости проблемы распознавания тождественно истинных формул исчисления предикатов; операции суперпозиции и примитивной рекурсии; примитивно-рекурсивные функции; операция минимизации; частично-рекурсивные функции; вычислимость частично-рекурсивных функций; частичная рекурсивность вычислимых функций; формула Клини.
Рабочая учебная программа включает в себя цели и задачи курса, тематический план с указанием аудиторных часов, содержание программы курса по темам, темы практических занятий, задания для самостоятельной работы, контрольные вопросы к экзамену, список литературы.
Цели и задачи курса
Пояснительная записка
Программа учебной дисциплины «Математическая логика и теория алгоритмов» составлена в соответствии Государственным образовательным стандартом высшего профессионального образования по специальности 010101.65 «Математика» (приложение 1).
Требования ГОС ВПО размещены в приложение 1.
Целью преподавания данной дисциплины является обучение студентов фундаментальным результатам и методам их получения в области математической логики и теории алгоритмов. Знания, умения и навыки , полученные студентами в результате усвоения материала дисциплины, могут быть использованы ими во всех видах деятельности в соответствии с Государственным образовательным стандартом высшего профессионального образования.
Данная дисциплина изучается в третьем семестре, в конце которого студент должен сдать экзамен.
Методика преподавания строится на сочетании лекций (36 часов), практических занятий (18 часов), самостоятельной и индивидуальной работы (46 часов). Планируется проведение двух контрольных работ.
№ п/п
|
Тема
|
Всего
|
Лек.
|
Сем.
|
Лаб
|
Сам
|
1
|
Булевы функции и логика высказываний.
|
|
4
|
4
|
|
|
2
|
Исчисление высказываний.
|
|
4
|
4
|
|
|
3
|
Логика предикатов.
|
|
4
|
3
|
|
|
4
|
Фильтры и фильтрованные произведения
|
|
3
|
4
|
|
|
5
|
Исчисление предикатов.
|
|
4
|
4
|
|
|
6
|
Элементы теории алгоритмов.
|
|
4
|
4
|
|
|
Итого часов:
|
70
|
35
|
35
|
|
26
|
Всего часов
|
96
|
СОДЕРЖАНИЕ ПРОГРАММЫ КУРСА ПО ТЕМАМ
Тема №1. Булевы функции и логика высказываний.
Основные бинарные отношения: эквивалентность и частичный порядок. Принципы трансфинитной индукции, максимума и теорема об эквивалентностях. Задание булевых функций, контактно-релейные схемы. Предложения о КНФ и ДНФ. Теорема об описании предполных классов Поста..
Тема №2. Исчисление высказываний.
Формулировка ИВ: алфавит, формулы, секвенции доказуемые и правила вывода, доказательство секвенций. Вспомогательные леммы и теоремы о полноте ИВ а узком и широком смыслах.
Тема №3. Логика предикатов.
Язык логики предикатов. Истинность формул в системах данной сигнатуры. Эквивалентные и конгруэнтные и формулы. Основные эквивалентности. Приведение формул к предваренному виду.
Тема №4. Фильтры и фильтрованные произведения.
Фильтры и ультрафильтры. Теорема о вложении фильтров в ультрафильтры и описание ультрафильтров. Понятие фильтрованного произведения систем. Теоремы об ультрапроизведениях и компактности. Предложения о нестандартных арифметиках и бесконечных моделях.
Тема №5. Исчисление предикатов.
Формулировка исчисления, предварительные результаты. Две леммы и теорема о существовании модели непротиворечивого множества формул. Теоремы о полноте ИП и независимости аксиом.
Тема №6. Элементы теории алгоритмов.
Машины Тьюринга. Частично рекурсивные функции и нормальные алгоритма Маркова. Тезис Чёрча. Классы рекурсивно перечислимых множеств. Неразрешимость проблем распознания тождественно истинных формул ИП, элементарной теории арифметики, существование ассоциативного исчисления с алгоритмически неразрешимой проблемой равенства.
УЧЕБНО-МЕТОДИЧЕСКАЯ ЛИТЕРАТУРА
Основная литература
АкритасА. Основы компьютерной алгебры с приложениями: пер. с англ. - М.: Мир,2008. - 544 с.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 2009. - 536 с.
Барендрегт Х. Ламбда-исчисление. Его синтаксис и семантика. - М.: Мир, 2005.-606с.
Де Боно Э. Латеральное мышление - СПб.: Питер Пвблишинг, 2007. -320с.
Гарднер М. А ну-ка, догадайся! М.: Мир, 2009.- 213 с.
Гарднер М. Математические досуги: Пер. с англ. - М.: Оникс, 2005.- 496с.
Грэй П. Логика, алгебра и базы данных: Пер. с англ.- М.: Машиностроение, 2009. - 359 с.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 2008.
Катленд Н. Вычислимость. Введение в теорию рекурсивных функций: Пер. с англ.- М.: Мир, 2011.-256 с.
Кац М., Улам С. Математика и логика. Ретроспектива и перспективы: Пер. с англ. - М.: Мир, 2009. - 254 с.
Дополнительная литература
Манин Ю. И. Вычислимое и невычислимое. - М.: Сов. радио. 2009. - 128 с.
Манин Ю. И. Доказуемое и недоказуемое. М.: "Советское радио",2009.
Мендельсон Э. Введение в математическую логику - М.: Наука, 2006.-320с.
Нефедов В. Н., Осипова В. А. Курс дискретной математики.М.,2008.
Никифоров А. Книга о логике. М.: "Гнозис", 2009
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. Пер. с англ. - М.: Мир, 2007. - 478 с.
Смаллиан Р. Как же называется эта книга? М.: Мир, 2008.
ВОПРОСЫ К ЭКЗАМЕНУ
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. NP-трудные и NP-полные задачи.
47. Логические парадоксы.
48. Многозначные логики.
КАЛЕНДАРНЫЙ ПЛАН ЛЕКЦИОННЫХ ЗАНЯТИЙ
Порядковый номер
|
Содержание занятия
|
Количество аудиторных часов
|
Объем материала
|
Форма контроля
|
Задания для самостоятельной работы студентов
|
|
Булевы функции и логика высказываний.
|
2
|
[3,стр. 3 — 5]
[4, стр. 3 — 10]
[6, стр. 5 - 10]
|
Фронтальный опрос
|
Изучить материалы лекции
|
|
Исчисление высказываний.
|
2
|
[1, стр. 15 — 25]
[2, стр. 20 — 25]
[4,стр 10 - 15]
|
Фронтальный опрос
|
Подготовить реферат по теме
|
|
Логика предикатов.
|
2
|
[2, стр. 20 — 30]
[3, стр. 10 — 15]
[5, стр 15 -20]
|
Фронтальный опрос
|
Изучить материалы лекции
|
|
Фильтры и фильтрованные произведения
|
2
|
[2, стр. 35 — 55]
[4, стр. 30 — 55] [1, стр. 45 — 55]
[6, стр 45 - 65]
|
Фронтальный опрос
|
Подготовка сообщений по теме
|
|
Исчисление предикатов.
|
2
|
[1, стр. 15 — 25]
[2, стр. 20 — 25]
[4,стр 10 - 15]
|
Фронтальный опрос
|
Подготовить реферат по теме
|
|
Элементы теории алгоритмов.
|
2
|
[1, стр. 15 — 25]
[2, стр. 20 — 25]
[4,стр 10 - 15]
|
Фронтальный опрос
|
Подготовить реферат по теме
|
КАЛЕНДАРНЫЙ ПЛАН ЛАБОРАТОРНЫХ ЗАНЯТИЙ
Порядковый номер
|
Содержание занятия
|
Количество аудиторных часов
|
Объем материала
|
Форма контроля
|
Задания для самостоятельной работы студентов
|
|
Булевы функции и логика высказываний.
|
2
|
[1, стр. 10 — 13]
[2, стр 13 -16]
|
Отчет по лабораторной работе.
|
Разработка различного класса алгоритма
|
|
Исчисление высказываний.
|
2
|
[2, стр. 20 — 35]
[5, стр 30 - 40]
|
Отчет по лабораторной работе.
|
Описание и представление, оценивание комбинаторных объектов.
|
|
Логика предикатов.
|
2
|
[3, стр 45- 55]
[5, стр 61 - 67]
|
Отчет по лабораторной работе.
|
Рассмотрение изоморфных объектов, составление сортировки на основе метода решета
|
|
Фильтры и фильтрованные произведения
|
2
|
[1. стр. 70 — 80]
[2, стр, 90 -100]
|
Отчет по лабораторной работе.
|
Разработка и усовершенствования, алгоритма с быстрым поиском. Осуществление логарифмического поиска в статистических и динамических таблицах,
|
|
Исчисление предикатов.
|
2
|
[2, стр. 20 — 35]
[5, стр 30 - 40]
|
Отчет по лабораторной работе.
|
Описание и представление, оценивание комбинаторных объектов.
|
|
Элементы теории алгоритмов.
|
2
|
[3, стр 45- 55]
[5, стр 61 - 67]
|
Отчет по лабораторной работе.
|
Рассмотрение изоморфных объектов, составление сортировки на основе метода решета
|
КРИТЕРИИ ОЦЕНКИ РЕЗУЛЬТАТОВ.
«5» («отлично») - уровень выполнения требований значительно выше удовлетворительного: использование дополнительного материала, самостоятельность суждений, отражение своего отношения к предмету обсуждения, отсутствие ошибок в изложении учебного материала, логичность и полнота изложения. Вопросы раскрыты на высоком уровне, выявлены полнота материала, систематичность и последовательность в изложении основных теоретических положений и вопросов; показаны умения четко и коротко излагать сущность вопросов, способность формулировать основные идеи темы, умение дискутировать. Представлен полный ответ на дополнительные вопросы. Обоснованы все ключевые моменты вопросов.
«4» («хорошо») - уровень выполнения требования выше удовлетворительного: полнота раскрытия вопроса; самостоятельность суждений; не более 1-2 недочетов; незначительные нарушения логики изложения материала. Вопросы раскрыты полностью, выявлены систематичность и последовательность в изложении основных теоретических вопросов, обоснованы все ключевые моменты темы. Не отражены при дискутировании умения четко и ясно излагать основные идеи темы, её результаты. Не на все дополнительные вопросы был дан полный ответ.
«3» («удовлетворительно») - достаточный минимальный уровень выполнения требований предъявляемых к работе: не более 1 ошибки или 2-3 недочетов; отдельные нарушения логики изложения материала. Вопросы раскрыты не полностью, обоснованы не все ключевые моменты вопросов. Представлена последовательность в изложении основных теоретических положений вопросов. Сущность темы не отражена в ответах на дополнительные вопросы. Возможны ошибки при изложении материала, не показано умение дискутировать.
«2» («неудовлетворительно») - уровень выполнения требования ниже удовлетворительного: наличие более 2 ошибок или 4 недочетов; нарушение логики, неполнота, нераскрытость обсуждаемого вопроса; отсутствие аргументации либо ошибочность её основных положений. Вопросы раскрыты не полностью, общая идея верная, но не выявлены систематичность и последовательность в изложении основных теоретических положений. Большинство ключевых моментов темы не обоснованы или имеются неверные обоснования. Возможны ошибки в схемах или чертежах. Ни на один дополнительный вопрос не получен ответ. Не выявлено умение дискутировать, не показано умение излагать материал четко и ясно.
Классификация ошибок и недочетов, влияющих на снижение оценки.
ОШИБКИ:
-неправильный ответ на поставленный вопрос;
-неумение ответить на поставленный вопрос;
-неправильное определение понятия, замена существенной характеристики понятия несущественной;
-незнание фактического материала, неумение привести самостоятельные примеры, подтверждающие высказанное суждение;
-неправильное раскрытие причин, закономерностей, условия протекания того или иного изученного явления.
НЕДОЧЕТЫ:
-неточный или неполный ответ на поставленный вопрос;
-при правильном ответе неумение полно обосновать его или проиллюстрировать примерами;
-неумение точно сформулировать ответ;
-неправильное произношение терминов;
-неточности в определении понятия, точности формулировки осуществляется после наводящих вопросов.
КРИТЕРИИ ОЦЕНКИ РЕЗУЛЬТАТОВ.
«Зачтено» - уровень выполнения требований выше удовлетворительного: полнота раскрытия вопроса, самостоятельность суждений. Допускаются отдельные неточности или незначительные нарушения логики в изложении материала. Не более 2-3 недочетов.
«Не зачтено» - уровень выполнения требований ниже удовлетворительного: неполнота, нераскрытость вопроса; отсутствие аргументации или ошибочность её основных положений; нарушение логики изложения. Более 2 ошибок или 4 недочетов.
Классификация ошибок и недочетов, влияющих на снижение оценки.
ОШИБКИ:
-неправильный ответ на поставленный вопрос;
-неумение ответить на поставленный вопрос;
-неправильное определение понятия, замена существенной характеристики понятия несущественной;
-незнание фактического материала, неумение привести самостоятельные примеры, подтверждающие высказанное суждение;
-неправильное раскрытие причин, закономерностей, условия протекания того или иного изученного явления.
НЕДОЧЕТЫ:
-неточный или неполный ответ на поставленный вопрос;
-при правильном ответе неумение полно обосновать его или проиллюстрировать примерами;
-неумение точно сформулировать ответ;
-неправильное произношение терминов;
-неточности в определении понятия, точности формулировки осуществляется после наводящих вопросов.
ТЕМЫ ЛАБОРАТОРНЫХ РАБОТ, ПРАКТИЧЕСКИХ ЗАНЯТИЙ, МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ИХ ПРОВЕДЕНИЮ
5. Задания для самостоятельной работы
Тема №1. Булевы функции и логика высказываний.
Построение по формуле таблиц истинности булевых функций.
Построение по булевой функции КНФ и ДНФ, упрощение их с использованием тождеств, составление релейно-контактных схем.
Тема №2. Исчисление высказываний.
Проверка допустимости правил вывода. Изучить ИВ и научиться доказывать секвенции.
Доказательство секвенций (не менее 20 штук), проверка их на тождественную истинность.
Тема №3. Логика предикатов.
Понять основные тождества ЛП.
Доказательство эквивалентностей и неэквивалентность двух формул с помощью построения подходящих моделей.
Тема №4. Фильтры и фильтрованные произведения.
Построение фильтров, задачи на главные ультрафильтры и центрированных систем.
Тема №5. Исчисление предикатов.
Примеры противоречивых и непротиворечивых множеств формул, аксиомы несложных теорий.
Тема №6. Элементы теории алгоритмов.
Доказательство примитивной рекурсивности ряда числовых функций. Написание программ машин Тьюринга для некоторых числовых функций.
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИЗУЧЕНИЮ
ДИСЦИПЛИНЫ И ОРГАНИЗАЦИИ САМОСТОЯТЕЛЬНОЙ
РАБОТЫ СТУДЕНТОВ
Самостоятельная работа студентов – совокупность всей самостоятельной деятельности обучаемых как в отсутствие преподавателя, так и в контакте с ним, в учебной аудитории и за ее пределами (в том числе и в ходе учебных занятий). При изучении данной дисциплины целесообразно использовать следующие формы учебной работы:
- обзорные лекции;
- самостоятельная работа студентов с учебной и методической литературой;
- выполнение контрольных заданий (упражнений, тестов, задач).
Планируя время на изучение дисциплины, студентам можно руководствоваться предложенным учебно-методическим планом, где указано распределение времени, отведенного на изучение дисциплины, между лекциями, семинарами и самостоятельной подготовкой.
В ходе самостоятельной работы студентам необходимо разбираться с изучаемым вопросом, используя учебники (смотри список основной литературы) и материалы лекций. Для подготовки докладов к семинарским занятиям, или для углубления знаний по той или иной теме, целесообразно воспользоваться дополнительной литературой (смотри список дополнительной литературы). Учебники и другую литературу можно взять в библиотеке.
При подготовке докладов, сообщений можно воспользоваться Интернет-ресурсами. При этом следует обратить внимание на то, чтобы используемая информация была актуальна и достоверна.
При подготовке докладов следует выписывать полные ссылки из тех источников, которыми воспользовались. Это позволит преподавателю проверить качество выполненной работы.
Для проверки знаний можно использовать тестовые материалы или вопросы для самостоятельной подготовки, предложенные в УМК.
Для контроля усвоения данной дисциплины учебным планом предусмотрен зачет. Вопросы к зачету приведены в разделе «Контрольные вопросы по дисциплине в целом».
НЕСКОЛЬКО ПРАКТИЧЕСКИХ СОВЕТОВ:
Не старайтесь записать дословно все, что говорит преподаватель — это невозможно, да и не нужно. Если вы будете к этому стремиться, в ваших записях неизбежны недописанные' предложения, пропуски, а значит — нарушения логики изложения материала, которые сделают конспект бесполезным. Учитесь формулировать мысли кратко и своими словами, записывая только самое существенное.
Учитесь «на слух» отделять главное от второстепенного. Но это не означает, что записывать нужно только основные положения и определения, которые без примеров и иллюстраций могут впоследствии, при чтении конспектов, оказаться непонятными. Поэтому факты, которые приводит лектор, также лучше отмечать; иногда для этого бывает достаточно нескольких ключевых слов.
Записи должны быть сжатыми, логично связанными, представлять собой нечто вроде развернутого плана лекции.
Если в лекции предлагаются схемы, таблицы, чертежи, обязательно полностью заносите их в тетрадь, выполняя аккуратно и внимательно.
По ходу лекции преподаватель обычно отмечает те или иные мысли, положения, поэтому сразу делайте соответствующие смысловые выделения в ваших записях. Для этого можно использовать не только разные виды подчеркиваний (прямая, волнистая линии, пунктир и т. п.), разноцветные выделения, но и различные значки, например:! — «важно», ? — «проверить, уточнить», NB (nota bene) — «обратить внимание» и др.
Оставляйте в тетради поля, которые можно использовать в дальнейшем для уточняющих записей, комментариев, дополнений и т. п.
Используйте красную строку для выделения смысловых частей в записях.
Постарайтесь выработать свою собственную систему сокращения часто встречающихся слов или их замены определенными знаками. Это даст вам возможность меньше писать, больше слушать и думать.
Сразу после лекции постарайтесь просмотреть записи и по свежим следам восстановить пропущенное, дописать недописанное, завершить выделение существенных моментов. |
