Преподаватель Таланова В.А.

I.ВВЕДЕНИЕ

Цель дисциплины - дать студентам необходимые конкретные сведения из математической логики, сформировать терминологический запас, необходимый для дальнейшего изучения математических и теоретико-программистских дисциплин.

Требования к знаниям и умениям по завершению изучения дисциплины.

Студент должен:

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

Период прохождения курса (2 курс, 3 семестр, зачет)

II.СОДЕРЖАНИЕ ДИСЦИПЛИН
Лекционный материал (38 часов)

1.       Лекция 1.  Высказывания. Формулы. Логическое следование и логическая эквивалентность. Подстановки. Формальные теории.  Общезначимость и непротиворечивость. Полнота, независимость, разрешимость.

2.       Лекция 2-3.  Исчисление высказываний. Классическое определение исчисления высказываний.  Правила вывода. Основные теоремы исчисления высказываний.

3.       Лекция 4-5. Исчисление предикатов. Основные определения. Логическое следование и логическая эквивалентность. Формальная арифметика. Общезначимость. Полнота исчисления предикатов.

4.       Лекция 6. Понятие алгоритма. Основные требования к алгоритмам. Блок-схемы алгоритмов. Подходы к уточнению понятия "алгоритм".

5.       Лекция 7. Машина Поста. Некоторые операции над машинами Поста.

6.       Лекция 8. Машина Тьюринга. Некоторые операции над машинами Тьюринга.

7.       Лекция 9. Универсальная машина Тьюринга. Тезис Тьюринга, проблема остановки.

8.       Лекция 10. Нормальные алгоритмы Маркова.

9.       Лекция 11-12.    Рекурсивные функции. Примитивно-рекурсивные функции. Определение, примеры. Примитивно-рекурсивные операторы.

10.   Лекция 13-14. Общерекурсивные и частично-рекурсивные функции. Тезис Черча. Связь рекурсивных функций с машинами Тьюринга.

11.   Лекция 15-16. Контекстная грамматика. Контекстно свободная грамматика. Грамматический разбор арифметических выражений.

12.   Лекция 17. Контекстно свободные языки. Нормальная форма Хомского. Контекстно свободный язык как решение уравнения.

13.   Лекция 18. Основные понятия и определения. Изоморфизм и эквивалентность автоматов. Примеры автоматов.

14.   Лекция 19. Частичные автоматы и их минимизация. Интерпретация автоматов. Основные проблемы абстракгной теории автоматов.

Практические занятия (19часов)

1.       Операции над высказываниями. Отношение эквивалентности.

2.       Закон двойственности. Функции алгебры логики. Нормальные формы

3.       Язык и формулы алгебры предикатов. Понятие модели. Значение формулы алгебры предикатов.

4.       Машины Поста и операции над ними, функции, вычислимые на машинах Поста.

5.       Машины Тьюринга и операции над ними, функции, вычислимые на машинах Тьюринга. Нормальные алгоритмы  Маркова.

6.       Вычислимые и рекурсивные функции

7.       Введение в грамматики, контекстно свободные языки. 4часа

III. РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА ПО ДИСЦИПЛИНЕ (изданная через центральные издательства и внутривузовским способом)

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

3.       Введение в дискретную математику. Наука. Москва. 1986.

4.       Дискретная математика (часть I). Солон Б.Я. Учебное пособие. Иваново, ИГХТУ1997.

5.       Дискретная математика/Таланова В.А. Методические указания. Иваново, ИГХТУ 2004.

Дополнительная

1.       Элементы математической логики, Новиков СП. Москва. НаукаЛ973.

2.       Сборник задач по дискретной математике./ Гаврилов Г.П., Сапоженко А. Москва. Наука 1977.