УТВЕРЖДЕНО                                                          УТВЕРЖДАЮ

   Ученым советом                                                    Декан факультета

     факультета

Протокол №        от                                                 _____________ 

"______ " ___________  2008   г.                            "______ " ___________  2008   г.

Программа учебной дисциплины
" Математическая логика и теория алгоритмов "
по направлению подготовки бакалавров  
 "Информатика и вычислительная техника", "Информационные системы и технологии",  

          по направлению подготовки специалистов

 

552800 Информатика и вычислительная техника.

 230200  Информационные системы и технологии. 

Составитель рабочей программы:

Доцент , к.ф.- м. н., доцент   Бодренко А.И. _____________

Волгоград  2008 г.

 

 

 

 

 

 

I. Аннотация.

 

Рабочая программа составлена на основании государственного образовательного стандарта высшего профессионального образования и учебных планов факультета по направлению подготовки бакалавров «ИВТ, ИСТ, АСОИОУ».

 

Дисциплина «Математическая логика и теория алгоритмов» изучается в 6-ом  семестре. Программа курса рассчитана на 36 часов лекций и 36 часов практики в первом семестре. Курс завершается экзаменом.

 

Преподавание дисциплины «Математическая логика и теория алгоритмов»  имеет целью формирование у студентов общей математической культуры, формализации понятий алгоритма и логического обоснования.

 

Контроль текущей работы  студентов в семестре осуществляется путем выполнения ими трех контрольных работ.

 

В разделе III данной программы учебной дисциплины представлена программа экзамена.

 

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

 

II. Содержание учебной дисциплины.

 

1.     Объем дисциплины и виды учебной работы

 

 

№ п/п	Вид учебной работы	Всего часов
1.	Аудиторные занятия (всего)	72
1.1.	Лекции	36
1.2.	Практические занятия	36
2.	Самостоятельная работа (всего)	28
3.	Общая трудоемкость дисциплины	100
4.	Вид итогового контроля	Экзамен

 

 

 

 

 

 

 

 

 

2.     Тематический план дисциплины.

№ п/п		Кол-во часов
		Лекции	Практ. Занятия
1.	ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ	12	12
2.	ИСЧИСЛЕНИЕ ПРЕДИКАТОВ	12	12
3.	ТЕОРИЯ АЛГОРИТМОВ	12	12
	Всего часов	36	36

 

 

 

3.     Содержание лекций и практических занятий

 

Тема 1 Лекции -12 ч., практики 12 ч., контрольная работа 1

Логические исчисления, модели: исчисление высказываний (ИВ); аксиомы; правило вывода; тождественная истинность. Непротиворечивость ИВ; теорема о полноте ИВ.

 

Тема 2 Лекции-12 ч., практики 12 ч., контрольная работа 1.

Исчисление предикатов (ИП); логические операции над предикатами и их теоретико-множественный смысл; кванторы; модели; формулы; свободные и связанные переменные. Истинность формул в модели, на множестве; общезначимые формулы; эквивалентные формулы ИП. Правила преобразований формул в эквивалентные; нормальная форма; тождественная истинность формул; непротиворечивость ИП; формулировка теоремы о полноте ИП. Теорема Поста -Маркова о существовании ассоциативного исчисления с алгоритмически неразрешимой проблемой равенства. 

 

 

Тема 3 Теория алгоритмов

Лекции-12 ч., практики 12 ч., контрольная работа 1.

Вычислимые функции: машины Тьюринга; вычислимые функции; тезис Черча; примеры вычислимых функций; рекурсивные, рекурсивно-перечислимые множества и их алгоритмическая характеристика. Теорема Поста; примеры алгоритмически неразрешимых проблем; неразрешимость проблем самоприменимости, применимости. Операции суперпозиции и примитивной рекурсии; примитивно-рекурсивные функции; Операции суперпозиции и примитивной рекурсии; примитивно-рекурсивные функции; операция минимизации; частично-рекурсивные функции; вычислимость частично-рекурсивных функций; частичная рекурсивность вычислимых функций; формула Клини.

 

План практических занятий по курсу “ Математическая логика и теория алгоритмов”

[1] Игошин В.И.  “Задачи и упражнения по математической логике и  теории алгоритмов” ,

 М.: Издательский  центр «Академия», 2007. — 304 с.

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

 [3] Игошин В.И.  “Математическая логика и теория алгоритмов“,  М.: Издательский центр «Академия», 2008. — 448 с.

Тема 1. АЛГЕБРА ВЫСКАЗЫВАНИЙ.  Задачи  [2] Часть 2 §1. 1-47,  §3. 1-48,

1.1-1.71  [1] стр.6-40; (1-3-ая неделя)                                                                                                                                                                      1. Основные понятия алгебры высказываний.
2. Высказывания и операции над ними.

3. Формулы алгебры высказываний.

4. Тавтологии алгебры высказываний.

5.  Логическое следование. 

6. Равносильность формул.

7.  Упрощение систем высказываний.
 Тема 2. ФОРМАЛИЗОВАННОЕ ИСЧИСЛЕНИЕ  ВЫСКАЗЫВАНИЙ. 

Задачи  8.1-8.27  [1] стр.143-161; (4-8-ая неделя)                                                                                                                                                                     

1. Построение формализованного исчисления высказываний

и исследование системы аксиом на независимость.

2. Построение выводов из аксиом.

3. Построение выводов из гипотез.

4. Теорема о дедукции и её применение.

5. Производные правила вывода и их применение.

6.  Независимость системы аксиом.

Тема 3. ЛОГИКА ПРЕДИКАТОВ

Задачи  [2] Часть 2 §4. 1-47

9.1-9.71  [1] стр.162-204; (9-13-ая неделя)                                                                                                         1. Основные понятия логики предикатов.

2. Понятие предиката и операции над предикатами.

3. Множество  истинности предиката.

4. Равносильность и следование предикатов.

5. Формулы логики предикатов, их интерпретация и классификация.

6. Равносильность формул логики предикатов.

7. Тавтологии логики предикатов. 

8. Равносильные преобразования формул.

9. Проблемы разрешимости для общезначимости и выполнимости формул.

10. Логическое следование формул логики предикатов.

Тема 4.   ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ.

Задачи  12.1-12.38, 13.1-13.16, 14.1-14.29  [1] стр.221-256; (14-18-ая неделя)                                                             

1. Машины Тьюринга.

2. Применение машин Тьюринга к словам.

3. Конструирование машин Тьюринга.

4.  Вычислимые по Тьюрингу функции.

5. Рекурсивные функции.

6. Примитивно рекурсивные функции.

7. Примитивно рекурсивные предикаты.

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

9. Марковские подстановки.

10. Нормальные алгоритмы и их применение к словам.

11. Нормально вычислимые функции.

 

 

4 Решение задач

 

Контрольная работа 1.

1)      Построить вывод теоремы  в ИВ.

2)      Является ли формула теоремой ИВ

3)      Является ли выражение формулой ИВ

 

Контрольная работа 2.

 

1) Является ли формула ИП:

общезначимой

2)  Является ли формула ИП: общезначимой.

 

3)  Постройте вывод формулы в ИП.

 

Решение задач 3.

 

1)      Постройте машину Тьюринга, вычисляющую оператор копирования

2)      Покажите примитивную рекурсивность множества четных  чисел.

3)      Является ли множество теорем исчисления высказываний рекурсивным.

 

 

 

III.           Программа экзамена.

 

Баллы ставятся по результатам трех контрольных работ ( по 20 баллов каждая). Практические задачи контрольных работ представлены в пособиях [2], [3], [4], [5] пункта  V.

.

“ Математическая логика и теория алгоритмов”

[1] Игошин В.И.  “Задачи и упражнения по математической логике и  теории алгоритмов” ,

 М.: Издательский  центр «Академия», 2007. — 304 с.

 [2] Игошин В.И.  “Математическая логика и теория алгоритмов“,  М.: Издательский центр «Академия», 2008. — 448 с.

Тема 1. АЛГЕБРА ВЫСКАЗЫВАНИЙ.  Задачи  1.1-1.71  [1] стр.6-40;

1. Основные понятия алгебры высказываний.
2. Высказывания и операции над ними.

3. Формулы алгебры высказываний.

4. Тавтологии алгебры высказываний.

5.  Логическое следование. 

6. Равносильность формул.

7.  Упрощение систем высказываний.
 Тема 2. ФОРМАЛИЗОВАННОЕ ИСЧИСЛЕНИЕ  ВЫСКАЗЫВАНИЙ. 

Задачи  8.1-8.27  [1] стр.143-161;

1. Построение формализованного исчисления высказываний

и исследование системы аксиом на независимость.

2. Построение выводов из аксиом.

3. Построение выводов из гипотез.

4. Теорема о дедукции и её применение.

5. Производные правила вывода и их применение.

6.  Независимость системы аксиом.

Тема 3. ЛОГИКА ПРЕДИКАТОВ

Задачи  9.1-9.71  [1] стр.162-204;

1. Основные понятия логики предикатов.

2. Понятие предиката и операции над предикатами.

3. Множество  истинности предиката.

4. Равносильность и следование предикатов.

5. Формулы логики предикатов, их интерпретация и классификация.

6. Равносильность формул логики предикатов.

7. Тавтологии логики предикатов. 

8. Равносильные преобразования формул.

9. Проблемы разрешимости для общезначимости и выполнимости формул.

10. Логическое следование формул логики предикатов.

Тема 4.   ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ.

Задачи  12.1-12.38, 13.1-13.16, 14.1-14.29  [1] стр.221-256;

1. Машины Тьюринга.

2. Применение машин Тьюринга к словам.

3. Конструирование машин Тьюринга.

4.  Вычислимые по Тьюрингу функции.

5. Рекурсивные функции.

6. Примитивно рекурсивные функции.

7. Примитивно рекурсивные предикаты.

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

9. Марковские подстановки.

10. Нормальные алгоритмы и их применение к словам.

11. Нормально вычислимые функции.

 

 

 

 

IV.           Учебно–методическое обеспечение

 

Основные пособия по курсу «математическая логика и теория алгоритмов» для специальности «математика» - [3], [4], [5].  Методы решения задач представлены в учебниках [2] и [3]. Кроме этого, имеются электронные обучающие программы и электронные учебники.

 

 

 

V.               Литература

1. Яблонский С.В. Введение в дискретную математику. - М. 1987

2. Гаврилов Г. П., Сапоженко А.А. "Сборник задач по дискретной математике". - М. 1989.

3. Мендельсон. Математическая логика. - М. 1980

4. Верещагин Н.К., Шень А. Языки и исчисления. М.: МЦНМО, 2000

5. Верещагин Н.К., Шень А. Вычислимые функции. М.: МЦНМО, 1999