Матрица соотнесения разделов учебной дисциплины и формируемых компетенций

№	Разделы	Компетенции
1.	Дедуктивный характер математики. Предмет и методы математической логики. Этапы развития математики.	СК-1
2.	Алгебра высказываний. Формулы алгебры высказываний. Основные равносильности алгебры высказываний. Нормальные и совершенные формы. Логическое следование формул. Применение алгебры высказываний к анализу рассуждений, описанию и преобразованию переключательных схем.	СК-1 СК-2
3.	Исчисление высказываний. Аксиомы и правила вывода. Выводимость из гипотез. Свойства выводимости из гипотез. Теорема дедукции. Производные правила вывода. Выводимость формул исчисления высказываний. Доказуемость формулы и её тождественная истинность. Теорема о полноте исчисления высказываний. Непротиворечивость, полнота и разрешимость исчисления высказываний.	СК-1 СК-3
4.	Логика предикатов. Предикаты. Логические операции над предикатами. Кванторные операции над предикатами. Формулы логики предикатов. Классификация формул логики предикатов. Интерпретация формул. Предваренная нормальная форма. Логическое следование. Запись математических предложений на языке логики предикатов. Методы рассуждений.	СК-1 СК-2
5.	Исчисление предикатов. Аксиоматическое построение исчисления предикатов: аксиомы и правила вывода. Теорема дедукции. Теоремы исчисления предикатов. Выводимость и общезначимость формул исчисления предикатов. Непротиворечивость, неразрешимость исчисления предикатов. Теорема Гёделя о неполноте исчисления предикатов.	СК-1 СК-3
6.	Неклассические логики. Многозначная логика Лукасевича. Нечёткие множества и нечёткая логика. Операции над нечёткими множествами. Нечёткие отношения. Нечёткие правила вывода	СК-1 СК-3
7.	Теория алгоритмов Машины Тьюринга. Алгоритмически неразрешимые задачи. Частично рекурсивные функции. Нумерация кортежей.	СК-1 СК-3

4. Объем дисциплины

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

Вид учебной работы	Количество часов по формам обучения
Очная
Номера семестров:
Аудиторные занятия (всего): В том числе:
	Лекции (Л)
Практические занятия (ПЗ)
Самостоятельная работа (СРС) (всего) В том числе:
	Реферат
Конспект в рабочей тетради
Аналитическая таблица
Исследовательский проект
Общая трудоемкость: часы/ зачетные единицы	180 (5 ед.)
Входной контроль (вид, № семестра)	тест
Форма итоговой аттестации - № семестров	экзамен

4.2. Распределение часов по темам и видам учебной работы

Названия разделов и тем	Всего часов по учебному плану	Виды учебных занятий
Аудиторные занятия, в том числе:	самостоя-тельная работа
лекции (в том числе интерактивные)	практ. занятия
Раздел 1. Алгебра высказываний
1. Понятие о логике как науке. Этапы развития логики. Предмет математической логики. Роль математической логики в системе научного знания.
2. Высказывания. Логические операции над высказываниями. Понятие формулы алгебры высказываний. Равносильность формул алгебры высказы­ваний. Таблица истин­ности формулы. Тавтологии.
3. ДНФ и КНФ, построение табличным и аналитическим (с помощью равносильностей) способами. Совершенные формы.
4. Применение алгебры высказываний к анализу рассуждений и описанию релейно–контактных схем.
Раздел 2. Исчисление высказываний
5. Аксиоматическое построение логики высказываний. Аксио­мы и правила вывода. Вывод формул из гипотез.
6. Теорема дедукции. Производные правила вывода.
7. Непротиворечивость, полнота, разрешимость исчисления высказываний. Независимость аксиом.
Раздел 3. Логика предикатов
8. Предикаты (отношения) на множестве. Сигнатура. Формула логики предикатов данной сигнатуры. Кванторы. Свобод­ные и связанные переменные.
9. Алгебраическая система (модель) данной сигнатуры. Определение истинности фор­мулы логики предикатов данной сигнатуры на модели той же сигнатуры. Применение языка логики предикатов для записи матема­тических предложений.
10. Эквивалентные формулы логики предикатов. Общезначимость и выполнимость формул логики предикатов. Предварен­ная нормальная форма.
Раздел 4. Исчисление предикатов
11. Построение ИП данной сигнатуры. Логические аксиомы. Правила вывода. Вывод формул. Примеры выводимых формул. Теорема Геделя о полноте исчис­ления предикатов.
12.Метатеория формальных систем. Характеристики систем (полнота, противоречивость, разрешимость). Теорема Геделя о неполноте теорий первого порядка включая формальную арифметику.
Раздел 5.Рекурсивные функции.
13. Интуитивное понятие алго­ритма. Свойства алгоритмов. Различные подходы к уточне­нию понятия алгоритма.
14. Понятие частично-рекурсивных, рекурсивных и общерекурсивных функций. Базовые функции и базовые операции. Рекурсивность основных функции арифметики. Тезис Черча.
Раздел 6. Машины Тьюринга
15. Машина Тьюринга, ее устройство. Действия над машинами Тьюринга. Функции, вычислимые и невычислимые на машине Тьюринга.
Раздел 7. Общие вопросы теории алгоритмов.
16. Алгоритмически неразрешимые проблемы. Нумерации (Кантора, Геделя).
ИТОГО:	180(36+ 144)

5. Содержание дисциплины

5.1. Содержание разделов дисциплины

Раздел 1.Алгебра высказываний

Тема 1. Введение Понятие о логике как науке. Этапы развития логики. Предмет математической логики. Роль математической логики в системе научного знания.

Тема 2. Высказывания и операции над ними. Высказывания. Логические операции над высказываниями. Понятие формулы алгебры высказываний. Равносильность формул алгебры высказы­ваний. Таблица истин­ности формулы. Тавтологии.

Тема 3. СКНД, СДНФ ДНФ и КНФ, построение табличным и аналитическим (с помощью равносильностей) способами. Совершенные формы.

Тема 4. Применение АВ Применение алгебры высказываний к анализу рассуждений и описанию релейно–контактных схем.

Раздел 2. Исчисление высказываний

Тема 1. Построение теории ИВ. Аксиоматическое построение логики высказываний. Аксио­мы и правила вывода. Вывод формул из гипотез.

Тема 2. Выводимость. Теорема дедукции. Производные правила вывода.

Тема 3 . Критерии теории ИВ. Непротиворечивость, полнота, разрешимость исчисления высказываний. Независимость аксиом.

Раздел 3. Логика предикатов

Тема 1 . Предикаты. Предикаты (отношения) на множестве. Сигнатура. Формула логики предикатов данной сигнатуры. Кванторы. Свобод­ные и связанные переменные.

Тема 2. Модели Алгебраическая система (модель) данной сигнатуры. Определение истинности фор­мулы логики предикатов данной сигнатуры на модели той же сигнатуры. Применение языка логики предикатов для записи матема­тических предложений.

Тема 3. Нормальные формы Эквивалентные формулы логики предикатов. Общезначимость и выполнимость формул логики предикатов. Предварен­ная нормальная форма.

Раздел 4. Исчисления предикатов

Тема 1. Построение ИП. Построение ИП данной сигнатуры. Логические аксиомы. Правила вывода. Вывод формул. Примеры выводимых формул. Теорема Геделя о полноте исчис­ления предикатов.

Тема 2. Формальные системы и их характеристики. Метатеория формальных систем. Характеристики систем (полнота, противоречивость, разрешимость). Теорема Геделя о неполноте теорий первого порядка включая формальную арифметику.

Раздел 5. Рекурсивные функции

Тема 1 . Понятие алгоритма. Интуитивное понятие алго­ритма. Свойства алгоритмов. Различные подходы к уточне­нию понятия алгоритма.

Тема 2. Рекурсивные функции. Понятие частично-рекурсивных, рекурсивных и общерекурсивных функций. Базовые функции и базовые операции. Рекурсивность основных функции арифметики. Тезис Черча.

Раздел 6. Машины Тьюринга

Тема 1 .Машины Тьюринга. Машина Тьюринга, ее устройство. Действия над машинами Тьюринга. Функции, вычислимые и невычислимые на машине Тьюринга.

Раздел 7. Общие вопросы теории алгоритмов.

Тема 1.Дополнительные вопросы теории алгоритмов. Алгоритмически неразрешимые проблемы. Нумерации (Кантора, Геделя).

5.2. Содержание семинарских и практических занятий

Тема 1. Введение Понятия: логика. Вопросы: Понятие о логике как науке. Этапы развития логики. Предмет математической логики. Роль математической логики в системе научного знания. Литература: [1] стр. 6-8 ,[2] стр. 50.

Тема 2. Высказывания и операции над ними. Понятия: высказывания, формула, таблица истинности, тавтология. Вопросы: Логические операции над высказываниями. Примеры формул алгебры высказываний (ТИ, ТЛ, выполнимых). Равносильность формул алгебры высказы­ваний. Таблица истин­ности формулы. Литература: [1] стр. 6-39, [2], стр. 50-52

Тема 3. СКНД, СДНФ Понятия: ДНФ, КНФ, СДНФ, СКНФ. Вопросы: 1. ДНФ и КНФ, построение табличным и аналитическим (с помощью равносильностей) способами. 2. Совершенные формы. Литература: [1] стр. 41- 47, [2], стр.52-54

Тема 4. Применение АВ Понятия: РКС. Вопросы: 1. Применение алгебры высказываний к анализу рассуждений и описанию релейно–контактных схем. Литература: [1] стр. 88-92, 138-143.

Тема 5. Построение теории ИВ. Понятия: аксиома, выводимость. Вопросы: Аксиоматическое построение логики высказываний. Аксио­мы и правила вывода. Вывод формул из гипотез. Литература: [1] стр. 143-146. [2], стр. 63-65

Тема 6. Выводимость. Понятия: выводимость. Вопросы: Теорема дедукции. Производные правила вывода. Литература: [1] стр. 146-154, [2], стр. 65-67.

Тема 7. Критерии теории ИВ. Понятия: непротиворечивость, полнота, разрешимость. Вопросы: Непротиворечивость, полнота, и разрешимость исчисления высказываний. Независимость аксиом. Литература: [1] стр. 157-162, [2], стр. 68-73.

Тема 8. Предикаты. Понятия: предикаты, кванторы. Вопросы: Предикаты (отношения) на множестве. Формула логики предикатов. Кванторы, свобод­ные и связанные переменные. Литература: [1] стр. 162-179, [2], стр.74-76.

Тема 9. Модели Понятия: модель, истинная формула ИП. Вопросы: Алгебраическая система (модель) данной сигнатуры. Определение истинности фор­мулы логики предикатов данной сигнатуры на модели той же сигнатуры. Применение языка логики предикатов для записи матема­тических предложений. Литература: [1] стр. 180-195, [2], стр. 77-79.

Тема 10. Нормальные формы   Понятия: эквивалентность, общезначимость, выполнимость, ПНФ. Вопросы: Эквивалентные формулы логики предикатов. Общезначимость и выполнимость формул логики предикатов. Предварен­ная нормальная форма. Литература: [1] стр. 195-197, [2], стр. 79-81.

Тема 11. Построение ИП. Понятия: выводимые формулы, ИП. Вопросы: Логические аксиомы и правила вывода. Примеры выводимых формул. Построение ИП. Литература: [1] стр. 213-218, [2], стр. 89-98.

Тема 12. Формальные системы и их характеристики. Понятия: полнота, противоречивость, разрешимость произвольных теорий. Вопросы: Метатеория формальных систем. Характеристики систем (полнота, противоречивость, разрешимость). Теорема Геделя о неполноте теорий первого порядка включая формальную арифметику. Литература:[ 2], стр. 98-108.

Тема 13. Понятие алгоритма. Понятия: алгоритм. Вопросы: Интуитивное понятие алго­ритма. Свойства алгоритмов. Различные подходы к уточне­нию понятия алгоритма. Литература: [1] стр. 221, [2], стр. 124.

Тема 14. Рекурсивные функции. Понятия: частично-рекурсивных, рекурсивных и общерекурсивных функций. Вопросы: 1. Применение базовых функции и базовых операции. 2. Рекурсивность основных функции арифметики. 3. Тезис Черча. Литература: [1] стр. 240-247, [2], стр. 124-136.

Тема 15. Машины Тьюринга. Понятия: машина Тьюринга. Вопросы: Машина Тьюринга, ее устройство. Действия над машинами Тьюринга. Функции, вычислимые и невычислимые на машине Тьюринга. Тезис Тьюринга, связь с тезисом Черча. Литература: [1] стр. 221-237, [2], стр. 136-142.

Тема 16. Дополнительные вопросы теории алгоритмов. Понятия: алгоритмическая неразрешимость. Вопросы: Алгоритмически неразрешимые проблемы и программа Гильберта. Нумерации. Литература:[2], стр. 148-155.

Литература:

1. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В.И.Игошин. — 3-е изд., стер. — М.: Издательский центр «Академия», 2007.

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

7. Структура и содержание самостоятельной работы студентов

7.1. План-график самостоятельной работы

№	Темы самостоятельной работы	Вопросы для самостоятельной работы	Контроль усвоения
	Интуитивное понятие алго­ритма	Приметы алгоритмов в ма­тематике, некор­ректность интуитив­ного понятия.	К/р №1
	Свойства алгоритмов	Определение алго­ритма через его ос­новные свой­ства, не­зависимость свойств при различных под­ходах.	К/р №1
	Различные подходы к уточнению понятия алгоритма	Краткое перечисле­ние раз­личных под­ходок к уточ­нению понятия алгорит­мов, взаимосвязь	К/р №1
	Основные функции и операции	Нуль функция, функ­ция выбора аргу­мента, функ­ция сле­дования. Операция рекурсии, минимиза­ции, суперпозиции.	К/р №2
	Рекурсивность различных функций	Доказательство ре­курсив­ности основ­ных функций ариф­метики. Иные функ­ции, их рекурсив­ность	К/р №2
	Тезис Черча.	Связь интуитивного поня­тия вычислимой функции и рекурсив­ной функции.	К/р №2
	Машины Тьюринга и опе­ра­ции над ма­ши­на­ми Тью­рин­га.	Устройство машины Тью­ринга. Примеры построе­ния и реше­ния задач на их со­ставление.	К/р №3
	Фун­кция, вы­чис­ли­мая по Тью­рин­гу. До­ка­за­те­ль­ст­во су­ще­ст­во­ва­ния фун­кций, не­вы­чис­ли­мых по Тью­рин­гу. При­мер не­вы­чис­ли­мой по Тью­рин­гу фун­кции.	Примеры функций, вычис­лимых по Тью­рингу и со­ответст­вующие программы этих машин. Беско­нечно и конечные машины Тью­ринга. Невычислимые по Тьюрингу функции.	К/р №3
	При­ме­ры ал­го­рит­ми­че­с­ки не­раз­ре­ши­мых про­блем (про­бле­ма рас­по­зна­ва­ния са­мопри­ме­ни­мо­сти, про­бле­ма при­ме­ни­мо­сти).	Проблема останова. Проблема самопри­мени­мости.	Коллоквиум №1

7.2. Структура и трудоемкость самостоятельной работы студентов

№ раздела дисциплины	Наименование раздела дисциплины	Формы самостоятельной работы (ак. час. / зач. ед.)	Общая трудоемкость (ак. час. / зач. ед.)
Конспектирование в рабочей тетради	Написание реферата	Работа с монографией	Выполнение контольных домашних работ	Составление аналитических таблиц
1.	Алгебра высказываний
2.	Исчисление высказываний
	Логика предикатов
	Исчисление предикатов
	Рекурсивные функции
	Машины Тьюринга
	Дополнительные вопросы
	Итого:

7.3. Тематика рефератов/курсовых работ и методические рекомендации по их выполнению

1. Творцы теории алгоритмов.

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

Рекомендуется следующий план изложения материала:

1. Проблемы отсутствия алгоритма для решения класса математичес­ких задач (проблема тождества для полугрупп и групп, нахождение общего способа решения диофантовых уравнений и др.)./1/, § 71.

2. Неразрешимые задачи в теории алгоритмов. /2/,с. 279-282.

Литература, рекомендуемая для изучения темы:

1. Клини С.К. Введение в математику.- М.: ИЛ, 1957.

2. Мендельсон Э. Введение в математическую логику.- М.: Наука, 1984.

2. Алгоритмы поиска. Цель данной работы – рассмотреть основные алгоритмы награфах, которые находят применение при сжатии информации, распозна­вании образов и синтезе баз данных. Рекомендуется следующий план изложения материала: 1. Необходимые понятия теории графов (/2/, с. 9-43, /1/, с. 57-64). 2. Бинарный поиск (/1/, с. 64-65). 3. Быстрая сортировка (/1/, с. 65-69). 4. Алгоритм Дикстры (/1/, с. 69-72).Литература, рекомендуемая для изучения темы: 1. Гоппа В.Д. Введение в алгебраическую теорию информации. – М.: Наука, 1995. 2. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977. 3. Неразрешимость логики первого порядка. Одним из принципиально важных результатов математической логики и теории алгоритмов является доказательство неразрешимости в логике первого порядка проблем распознавания как общезначимости, так и вы­полнимости ее предложений. Цель данной работы – изучить до­казательства неразре­шимости логики первого порядка. Рекомендуется следующий план работы: 1. Изучить основные понятия логики первого порядка (/1/, с. 130-151). 2. Рассмотреть понятие машины Тьюринга и доказать неразрешимость про­блемы остановки (/1/, с. 36-54). 3. Вывести неразрешимость логики первого порядка из неразрешимо­сти проблемы остановки (/1/, с. 152-160). 4. Разобрать доказательство неразрешимости логики первого порядка методом Геделя (/1/, с. 160-166). 5. Решить задачи 3.6, 3.10 из упражнения на стр. 46-48 и задачи 10.1, 10.3 из упражнения на стр. 164-165 в книге /1/.Литература, рекомендуемая для изучения темы: 1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994. 4. Нестандартные модели арифметики. В любой математической теории принципиально важным является вопрос о существовании и единственности модели формализации этой теории. Цель дан­ной работы – проанализировать этот вопрос для элементарной теории арифметики. Рекомендуется следующий план работы: 1. Рассмотреть язык логики узкого исчисления предикатов арифметики и его стандартную интерпретацию в алгебре натуральных чисел(/1/, с. 131-151; /2/, с. 115-131). 2. Доказать теорему о существовании нестандартных моделей элементарной теории арифметики (/1/, с. 252-260). 3. Изучить метод построения моделей элементарной теории арифме­тики с помощью принципов нестандартного анализа (/1/, с. 25-32; /3/, с. 57- 79). 4. Разобрать все примеры из указанных выше литературных источ­ников и решить задачи 17.1, 17.2 в /1/, а также задачи 1-3 стр.131 в книге /2/.Литература, рекомендуемая для изучения темы: 1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994. 2. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1971. 5. Метод диагонализации в математической логике.В теории алгоритмов, математической логике, теории множеств и других разделах математики широко применяется метод диагонализации, в основе кото­рого лежит возможность построения антидиагонального счетного множества для любой последовательности счетных множеств. Цель данной работы – изучить метод диагонализации и с его помощью построить примеры невычисли­мых функций. Рекомендуется следующий план работы: 1. Рассмотреть понятие счетного множества и изучить метод диаго­нализа­ции (/1/, с. 12-30). 2. Рассмотреть понятие машины Тьюринга и методом диагонализации по­строить пример невычислимой функции (/1/, с. 36-45, 66-74). 3. Рассмотреть проблему остановки машины Тьюринга и с помощью тезиса Черча доказать ее неразрешимость (/1/, с. 47-48, 74-76). 4. Рассмотреть понятие диагонализации выражения и доказать лемму о диа­гонализации и теорему Черча о неразрешимости (/1/, с. 228-235).5. Разобрать решения всех примеров из цитированных разделов /1/ и решить задачи 3.9, 3.10 из упражнения на стр. 45-48 и задачи 5.1-5.4 из упражнения на стр. 76-77 в книге /1/.Литература, рекомендуемая для изучения темы: 1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994. 6. Машины Тьюринга и невычислимые функции. Машина Тьюринга и вычислимость являются фундаментальными по­нятиями теории алгоритмов. Цель данной работы – изучить ос­новные свойства машины Тьюринга и с ее помощью построить невычис­лимую функцию. Рекомендуется следующий план работы: 1. Разобрать такие основополагающие понятия теории алгоритмов, как машина Тьюринга, вычислимая функция и тезис Черча (/1/, с. 36-54; /2/, с.228-229, 249-255). 2. Рассмотреть понятие продуктивности машины Тьюринга и дока­зать ее основные свойства (/1/, с. 46, 55-60; /2/, с. 12-25). 3. Доказать невычислимость функции – самоприменимость машины Тьюринга (/1/, с. 60-64). 4. Рассмотреть проблему останова машины Тьюринга и доказать ее нераз­решимость (/1/, с. 47-48, 53-54, 64-65). 5. Разобрать решения всех примеров из литературных источников /1/,/2/ и решить задачи 3.1-3.10 из упражнения на стр. 45-48 в книге /1/.Литература, рекомендуемая для изучения темы: 1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994. 2. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1971. 7. Вычислимость на абаке и рекурсивные функции. Рекурсивная функция и вычислимость являются фундаментальными поня­тиями теории алгоритмов. Цель данной работы – изучить вычисли­мость на абаке, вычислимость машиной Тьюринга и доказать их эквивалент­ность понятию рекурсивной функции. Рекомендуется следующий план работы: 1. Разобрать такие основополагающие понятия теории алгоритмов, как машина Тьюринга, рекурсивная функция и тезис Черча (/1/, с. 36-54). 2. Рассмотреть понятие «обычного» компьютера, введенное Иоахи­мом Ламбеком и названное им абаком, доказать, что вычислимость функ­ции абаком сводится к вычислимости ее машиной Тьюринга (/1/, с. 78-95). 3. Доказать, что рекурсивные функции вычислимы на абаках (/1/, с. 100-122). 4. Доказать, что вычислимые функции рекурсивны (/1/, с. 100-122). 5. Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 6.1- 6.4 из упражнения на стр. 96 в книге /1/.Литература, рекомендуемая для изучения темы: 1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994. 8. Представимость рекурсивных функций и отрицательные резуль­таты ма­тематической логики. Главными отрицательными результатами теории алгоритмов являются тео­рема Черча о неразрешимости, теорема Тарского о неопределимости истинности и первая теорема Геделя о неполноте систем арифметики. Цель данной работы – изучить доказательства этих теорем с по­мощью представления рекур­сивных функций в специальном расширении арифметики. Рекомендуется следующий план работы: 1. Разобрать такие основополагающие понятия теории алгоритмов, как язык арифметики и рекурсивная функция (/1/, с. 103-108, 141-145). 2. Рассмотреть понятие представимости функций в теории и доказать представимость рекурсивных функций в специальном непротиворечивом расширении Q арифметики (/1/, с. 212-226). 3. Рассмотреть понятие геделевой нумерации и доказать главные отрицательные результаты теории алгоритмов (/1/, с. 228-240). 4. Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 14.1-14.2 из упражнения на стр. 226-227 и задачи 15.1-15.4 из упражнения на стр. 240 в книге /1/.Литература, рекомендуемая для изучения темы: 1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994. 9. Разрешимость арифметики сложения. Проблема разрешимости теорий имеет принципиальное значение для эле­ментарно аксиоматизируемых математических теорий и, в частности, для ариф­метики. Цель данной работы – проанализировать эту проблему для арифметики с различными основными операциями. Рекомендуется следующий план работы:1. Разобрать такие основополагающие понятия математической ло­гики, как геделева нумерация и разрешимое множество (/1/, с. 228-233, /2/, с.151-152). 2. Доказать неразрешимость арифметики со сложением и умноже­нием (/1/, с. 234-236). 3. Доказать разрешимость арифметики со сложением, без умноже­ния (/1/, с. 290-299). 4. Разобрать решения всех примеров из цитированных разделов книг /1/,/2/ и решить задачи 1-3 из упражнения на стр. 152 в книге /2/.Литература, рекомендуемая для изучения темы: 1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994. 10. Теорема Геделя о неполноте формальной арифметики. Теорема Геделя о неполноте формальной арифметики по праву счи­тается одним из наиболее замечательных достижений математической ло­гики и теории алгоритмов, поскольку в своей семантической формули­ровке устанавливает не­возможность доказательства любого истинного ут­верждения этих формальной теории. Цель данной работы - изу­чить основы формальной арифме­тики и разобрать доказательство семан­тической формулировки теоремы Геделя о ее неполноте. Рекомендуется следующий план работы: 1. Изучить постановку задачи о неполноте формальной арифметики (/1/,с. 7-11). 2. Рассмотреть начальные понятия теории алгоритмов и примеры их применения (/1/, с. 12-21). 3. Доказать простейшие критерии неполноты (/1/, с. 21-25). 4. Изучить основы формальной арифметики и доказать семантиче­скую формулировку теоремы Геделя о ее неполноте (/1/, с. 25-42). 5. Разобрать все примеры и восстановить все пропущенные доказа­тельства в брошюре /1/.Литература, рекомендуемая для изучения темы: 1. Успенский В.А. Теорема Геделя о неполноте. – М.: Наука, 1982. 11. Разрешимые и неразрешимые аксиоматические теории. Проблема разрешимости теорий имеет принципиальное значение для элемен­тарно аксиоматизируемых математических теорий. Цель работы – изучить методы доказательства разрешимости и не­разрешимости теорий, проиллюстрировав их применение на известных важных примерах.Рекомендуется следующий план работы: 1. Разобрать такие основополагающие понятия теории моделей, какязык узкого исчисления предикатов (УИП) и его интерпретация в моделях, рассмотреть известные конструкции над алгебраическими системами (/1/, с.103-118; /2/, с. 12-25). 2. Изучить методы доказательства разрешимости и неразрешимости теорий (/2/, с. 265-275). 3. Рассмотреть известные примеры доказательства разрешимости и неразрешимости аксиоматических теорий (/2/, с. 275-292; /3/). 4. Разобрать решения всех примеров из литературных источников /1/, /2/.Литература, рекомендуемая для изучения темы: 1. Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука, 1979. 2. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. – М.: Наука, 1980. 3. Рабин М.О. Разрешимые теории. В кн.: Справочная книга по математической логике, ч.3. Теория рекурсии. – М.: Наука, 1982. – с. 77-111. 4. Ершов Ю.Л., Лавров И.А., Тайманов А.Д., Тайцлин М.А. Элементарные теории // УМН, 1965, 20, № 4, с. 37-108.

12. Логическая игра.

В работе предлагается осветить символический и графический методы решения логических задач. Рекомендуется следующий план работы.

1. Рассмотреть основные понятия алгебры высказываний и логики предикатов (/1/, с.10-35, 122-134).

2. Изучить приложение алгебры высказываний и логики предикатов к логико-математической практике (/1/, с. 52-62, 168-182).

3. Изучить кванторные операции над предикатами (/1/, с. 134-159).

4. Рассмотреть решение "логических" задач на языке символов (/3/, с.

60-65).

5. Разобрать графический способ решения задач подобного рода (/2/, с.

9-56).

Разобрать решения всех задач из цитированных выше разделов указанных литературных источников и решить задачи 3.58-3.61 из книги /3/. Выполнить 30 заданий из упражнений 1-91 на с. 57-60 книги /2/.

Литература, рекомендуемая для изучения темы

1 . Игошин В.И. Математическая логика и теория алгоритмов. - Саратов: Изд-во Сарат. ун-та, 1991.

2 . Кэрролл Л. Логическая игра: Пер. с англ. Ю.А. Данилова. - М.: Наука, 1991. (Б-ка "Квант"; Вып. 73).

3 . Игошин В.И. Задачник-практикум по математической логике: Учеб. пособие для студентов-заочников физ.-мат. фак-в пед. ин-тов. - М.: Просвещение, 1986.

13. Логика второго порядка и определимость в арифметике.

Логика второго порядка существенно отличается от логики первого порядка и позволяет всесторонне исследовать такую фундаментальную проблему математической логики, как определимость арифметической истины. В курсовой работе необходимо изучить основные методы логики второго порядка и с их помощью проанализировать понятие определимости в арифметике. Рекомендуется следующий план работы.

1. Изучить основные понятия логики второго порядка и проанализировать ее главные отличия от логики первого порядка (/1/, с. 261­273).

2. Рассмотреть понятие определимого в теории множества и исследовать проблему определимости множеств предложений первого порядка, истинных в стандартной модели арифметики (/1/, с. 273, 274-280).

3. Рассмотреть введенный П. Коэном метод вынуждения и доказать с его помощью теорему Дж. Аддисона о неопределимости в арифметике класса множеств, определимых в арифметике (/1/, с. 281-289).

Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 18.1-18.4 из упражнения на стр. 272-273 и задачи 20.1-20.10 из упражнения на стр. 289 в книге /1/.

Литература, рекомендуемая для изучения темы

1. Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.

14. Интерполяционная лемма Крейга и ее приложения.

Интерполяционная лемма Крейга дает положительное решение следующей важной задачи логики узкого исчисления предикатов (УИП): если из предложения А следует предложение С, то существует предложение В, которое следует из А, из которого следует С и которое содержит лишь нелогические символы, входящие как в А, так и в С. В курсовой работе необходимо изучить доказательство интерполяционной леммы Крейга и рассмотреть ее приложения к задаче о непротиворечивости объединения теорий и к задаче об определимости понятий теории. Рекомендуется следующий план работы.

1. Разобрать доказательство интерполяционной леммы Крейга (/1/, с. 308-318).

2. Доказать теорему Робинсона о непротиворечивости объединения теорий (/1/, с. 319-322).

Выполнить упражнение на с. 327 в книге /1/.

Литература, рекомендуемая для изучения темы

1. Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.

7.4. Примерные контрольные и самостоятельные работы по дисциплине

1. Индивидуальная работа по разделу «Алгебра высказываний»

Вариант 1.

1. Упростить формулу .

2. Данное высказывание «Он и жнец, и швец, и на дуде игрец» записать в виде формулы логики высказываний. Построить отрицание данного высказывания в виде формулы, не содержащей внешних знаков отрицания. Перевести на естественный язык.

3. Установить, является ли данное рассуждение правильным, (проверить, следует ли заключение из конъюнкции посылок):

«Если курс ценных бумаг растет, или процентная ставка снижается, то падает курс акций. Если процентная ставка снижается, то либо курс акций не падает, либо курс ценных бумаг не растет. Курс акций понижается. Следовательно, снижается процентная ставка».

2. Индивидуальная работа по разделу «Логика предикатов»

Вариант 1.

1. Установить, является ли данное выражение формулой, а если да, то определить, какие переменные в ней свободные, а какие связанные.

2. Даны предикаты: “ торговец подержанными автомобилями”; и “ нечестный человек”. Записать словами предложенную формулу .

3. Данное суждение «Не всякое действительное число является рациональным» записать в виде формулы логики предикатов. Построить отрицание данного суждения в виде формулы, не содержащей внешних знаков отрицания. Перевести на естественный язык.

4. Найти приведенную и нормальную формулы для данной формулы .

3. Итоговая контрольная работа по темам «Алгебра и исчисление высказываний»

Вариант 1.

1. Используя основные равносильности, найдите ДНФ и СДНФ формулы

2. Используя табличный метод, найдите СНДФ формулы

3. Подберите формулу A так, чтобы формула F тождественно равнялась 1:

F = .

4. Постройте комбинационную схему, реализующую функцию

x	Y	z	f	X	y	z	f

5. Докажите формулы исчисления высказываний, используя производные правила вывода:

а) ├

б) ├

4. Итоговая контрольная работа по темам «Логика и исчисление предикатов»

Вариант 1.

1. Пусть N = {0,1,2,...} - множество натуральных чисел с предикатами, соответствующими сложению и умножению:

2. Напишите формулу логики предикатов, истинную на N тогда и только тогда, когда z делится на x + y.

3. Запишите на языке логики предикатов: прямые x и y имеют общую точку, лежащую в плоскости z.

4. Докажите выводимость формулы: ├

5. Является ли тождественно истинной формула:

?

6. Найдите предваренную нормальную форму формулы и ее отрицания:

а) ; б)

5. Индивидуальная работа по разделу «Рекурсивные функции»

Вариант 1.

1. Выяснить, какая функция является результатом операции суперпозиции:

а) f₁(x_1, x₂)= x₁+ x₂, f₂(x_1, x₂)= x₁ x₂, f₃(x_1, x₂)= x₁+ x₂ + x₁ x₂ в

φ(y₁, y₂, y₃)= y₁+ y₂ - y₃;

б) О(x) = 0 в S(x) = x +1;

в) S(x) = x +1 в О(x) = 0.

2. Получить из базовых функций с помощью операции суперпозиции следующие функции:

а) ψ(x)= x + а;

б) ψ(x)= 2x.

3. Какой аналитический вид имеет функция φ, которая получена операцией рекурсии из функций:

а) f₁(x) = х и f₂(x, y, z) = z + 1;

б) f₁(x) = 0 и f₂(x, y, z) = x + z.

6. Индивидуальная работа по разделу «Машины Тьюринга»

Вариант 1.

1. Дано число n в восьмеричной системе счисления. Постройте машину Тьюринга, которая бы увеличивала данное число на единицу.

2. Дана десятичная запись натурального числа n > 1. Постройте машину Тью­ринга, которая уменьшала бы данное число на 1. При этом запись числа n – 1 не должна содержать левый нуль. Например, 100 – 1 = 99, а не 099. Начальное по­ложение головки – правое.

3. Построить машину Тьюринга, вычисляющую функцию

4. Построить машину Тьюринга, вычисляющую функцию , равную остатку от деления х на 2.

7. Контрольная работа по разделу «Рекурсивные функции и машины Тьюринга»

Вариант 1.

1. Какой аналитический вид имеет функция φ, которая получена операцией рекурсии из функций:

а) f₁(x) = х и f₂(x, y, z) = z + 5;

б) f₁(x) = х и f₂(x, y, z) = x + y + z;

в) f₁(x, y) = хy и f₂(x, y, z, s) = x + y + z+ s.

2. Какой аналитический вид имеет функция φ, которая получена операцией рекурсии из функций:

а) f₁(x) = х и f₂(x, y, z) = z + 1;

б) f₁(x) = 0 и f₂(x, y, z) = x + z;

в) f₁(x) = х и f₂(x, y, z) = x + y + z;

г) f₁(x, y) = хy и f₂(x, y, z, s) = x + y + z+ s.

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

8.1. Основная литература

1. Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, 2004. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. – М.: Академия, 2005.

2. Калинина О.Л. Основы дискретной математики. Часть 2. Элементы математической логики. Учебное пособие. Пермь: ПГПУ, 2008.

3. Алябьева В.Г., Пастухова Г.В., Теория алгоритмов. Учебное пособие. Пермь: ПГПУ, 2011.

8.2. Дополнительная литература

1. Кат­ленд Н. Вы­чис­ли­мость. Вве­де­ние в те­орию ре­кур­сив­ных фун­кций. - М.: Мир, 1983.

2. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математиче­ской логике и теории алгоритмов. – М.: Наука, 1984.

3. Мар­ков А.А., На­гор­ный Н.М. Те­ория ал­го­риф­мов. - М.: ФАЗИС, 1996. -448с.

4. Мат­ро­сов В.Л. Те­ория ал­го­рит­мов. - М.: Про­ме­тей, 1989.

5. Мен­де­ль­сон Э. Вве­де­ние в ма­те­ма­ти­че­с­кую ло­ги­ку: - 3-е изд. -М.: На­ука, 1984.

6. Ми­хай­лов А.Б., Ры­жо­ва Н.И., Швец­кий М.В. Лек­ции по ос­но­вам ма­те­ма­ти­че­с­кой ло­ги­ки. Эле­мен­ты те­ории ал­го­риф­мов. - СПб.: РГПУ им. А.И.Герцена, 1997.

7. Род­жерс Х. Те­ория ре­кур­сив­ных фун­кций и эф­фе­к­тив­ная вы­чис­ли­мость. - М.: Мир, 1972.

8. Трах­те­нб­рот Б.А. Ал­го­рит­мы и вы­чис­ли­те­ль­ные ав­то­ма­ты. - М.: Сов.

радио, 1974.

9. Успен­ский В.А. Ма­ши­на По­ста. - М.: На­ука, 1979.

10. Успен­ский В.А. Се­мё­нов А.Л. Те­ория ал­го­рит­мов: осно­вные от­кры­тия и при­ло­же­ния. - М.: На­ука, 1987.

8.4. Электронные материалы

1. Сайт профессора кафедры математической логики и теории алгоритмов МГУ им. Ломоносова Пентуса М.Р.:

http://lpcs.math.msu.su/~pentus/problems.htm

2. Сайт кафедры «Прикладной математики» Физико-механического фа­культета Санкт-Петербургского государственного технического универ­ситета: http://amd.stu.neva.ru/education/prog71.htm

3. Сайт УГАТУ (рефераты и лекции):

www.twirpx.com/files/special/protection/

4. Электронный вариант книги Носова В.А. «Алгоритмы и оценки их сложности»:

rrc.dgu.ru/res/intsys.msu.ru/staff/vnosov/theoralg.htm

5. Электронный вариант книги Мальцева А.И. «Алгоритмы и рекурсив­ные функ­ции»:

www.proklondike.com/contentview.php?content

9. Содержание и порядок проведения входного и текущего контроля, промежуточной аттестации

9.1. Содержание и формы проведения входного контроля

9.2. Содержание и формы текущего контроля знаний

№	Пороговый
СК -1	Знает: смысл основных понятий алгебры высказываний (АВ) и логики предикатов (ЛП), теории алгоритмов (ТА): высказывание, операции над высказываниями, таблица истинности, формула АВ, равносильные формулы, ДНФ, КНФ, предикат, кванторы, нормальная форма, алгоритм, машина Тьюринга, рекурсивная функция, вычислимая функция (описание).	Умеет: составлять таблицы истинности, применять основные равносильности, диагностировать формулу АВ (тождественно истинная, тождественно ложная, выполнимая), показывать выводимость из гипотез, записывать на языке предикатов математические объекты (определения, теоремы), показывать рекурсивность функций, строить машины Тьюринга;	Владеет: методом решения логических задач с помощью АВ; методами доказательства выводимости в построенном исчислении формул (теорем); способами уточнения понятия алгоритма в виде машин Тьюринга.
Продвинутый
Знает: смысл основных понятий АВ и ЛП, исчисления высказываний (ИВ) и предикатов (ИП), ТА: высказывания, действия над высказываниями (конъюнкция, дизъюнкция, импликация, эквивалентность), таблицы истинности, формулы АВ, равносильных формул, ДНФ, СДНФ, КНФ, СКНФ; аксиомы и их свойств (полнота, независимость) исчисления, правила вывода из аксиом, теорема дедукции, выводимой формулы, связь АВ и ИВ, свойства ИВ (непротиворечивость, полнота); предиката, квантора, нормальных форм и формул; формул ИП, аксиомы и их свойства ИП, выводимые формулы, теорема дедукции, свойства ИП (непротиворечивость, полнота; алгоритма, вычислимой функции, машины Тьюринга, действии над машинами, тезис Черча, тезис Тьюринга, рекурсивной функции (частично рекурсивной и примитивно рекурсивной));	Умеет: составлять таблицы истинности, применять основные равносильности, диагностировать формулу АВ (тождественно истинная, тождественно ложная, выполнимая), составлять СКНФ и СДНФ произвольной формулы, показывать выводимость из гипотез, записывать на языке предикатов математические объекты (определения, теоремы), проверять истинность формул методом резолюций, применять основные операции (рекурсии, суперпозиции, минимизации) к основным функциям (следования, ноль-функция, выбор аргумента), показывать рекурсивность функций, строить машины Тьюринга и производить действия с ними;	Владеет: методом решения логических задач и анализом РКС (релейно-контактных схем) с помощью АВ; методами доказательства выводимости в построенном исчислении формул (теорем) двумя различными способами; способами уточнения понятия алгоритма в виде машин Тьюринга и рекурсивных функций,
СК-2	Пороговый
Знает: способы построения аксиоматическим методом ИВ, уточнение определения алгоритма через машины Тьюринга, характеристики систем (полнота, противоречивость, разрешимость).	Умеет: приводить примеры полных систем, разрешимых и непротиворечивых, распознавать структуру системы (аксиомы, правила вывода и язык), строить МТ.	Владеет: методами построения МТ и рекурсивных функций.
Продвинутый
Знает: способы построения аксиоматическим методом ИВ и ИП, связь данных систем с АВ и ЛП, уточнение определения алгоритма через машины Тьюринга и рекурсивные функции, связь между тезисами Тьюринга и Черча, характеристики систем (полнота, противоречивость, разрешимость), примеры алгоритмически неразрешимых проблем.	Умеет: строить примеры полных систем, разрешимых и непротиворечивых, конструировать произвольные системы по заданным характеристикам (аксиомы, правила вывода и язык), строить произвольные МТ и рекурсивные функции, проводить аналогии между различными уточнениями алгоритма, показывать алгоритмическую неразрешимость некоторой задачи.	Владеет: методами построения МТ и рекурсивных функций, методами построения аксиоматических теории с заданными характеристиками.
СК-3	Пороговый
Знает: этапы формирования понятия алгоритма и аксиоматических систем.	Умеет: применить язык логики предикатов к анализу текстов.	Владеет: методикой построения необходимых и достаточных условий заданной задачи, навыком преобразований высказываний для анализа релейно-контактных схем и решения текстовых задач.
Продвинутый
Знает: этапы и методы формирования понятия алгоритма и аксиоматических систем.	Умеет: применить язык логики предикатов к анализу математических текстов (запись определения, предложения, теоремы) и построения противоположных. обратных утверждений данному и применять доказательство от противного.	Владеет: аксиоматическим методом анализу произвольной математической теории, методикой построения необходимых и достаточных условий произвольной задачи, навыком преобразований высказываний для анализа релейно-контактных схем и решения текстовых задач.

9.3. Содержание и формы промежуточной аттестации

Формы аттестации по дисциплине: экзамен.

Вопросы к экзамену:

1. Высказывания. Логические операции над высказываниями.

2. Понятие булевой функции. Число булевых функций от n переменных. Булевы функции от двух переменных. Связь между ними.

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. m-опе­ра­ция (опе­ра­ция ми­ни­ми­за­ции). Час­тич­но ре­кур­сив­ное опи­са­ние фун­к­ции. Час­тич­но ре­кур­сив­ная фун­кция. При­ме­ры час­тич­но ре­кур­сив­ных фун­кций. Об­ще­ре­кур­сив­ная фун­кция. При­ме­ры об­ще­ре­кур­сив­ных фун­кций.

28. Ма­ши­на Тью­рин­га. Опе­ра­ции над ма­ши­на­ми Тью­рин­га (опе­ра­ция ком­по­зи­ции, опе­ра­ция вет­вле­ния, опе­ра­ция за­цик­ли­ва­ния). Гё­де­ле­ва ну­ме­ра­ция ма­шин Тью­рин­га.

29. Фун­кция, вы­чис­ли­мая по Тью­рин­гу. До­ка­за­те­ль­ст­во су­ще­ст­во­ва­ния фун­к­ций, не­вы­чис­ли­мых по Тью­рин­гу. При­мер не­вы­чис­ли­мой по Тью­рин­гу фун­кции.

30. При­ме­ры ал­го­рит­ми­че­с­ки не­раз­ре­ши­мых проблем (про­бле­ма рас­по­зна­ва­ния са­мо­при­ме­ни­мо­сти, про­бле­ма при­ме­ни­мо­сти).