Учебно-методический комплекс дисциплины математическая логика и теория алгоритмов 050100 Педагогическое образование

Вид материала

Учебно-методический комплекс

Содержание 5.2. Содержание семинарских и практических занятий 7. Структура и содержание самостоятельной работы студентов Темы самостоятельной работы Структура и трудоемкость самостоятельной работы студентов Написание реферата 7.3. Тематика рефератов/курсовых работ и методические рекомендации по их выполнению 2. Алгоритмы поиска. 3. Неразрешимость логики первого порядка. 4. Нестандартные модели арифметики. 5. Метод диагонализации в математической логике. 6. Машины Тьюринга и невычислимые функции. 7. Вычислимость на абаке и рекурсивные функции. 8. Представимость рекурсивных функций и отрицательные резуль­таты ма­тематической логики. 9. Разрешимость арифметики сложения. 10. Теорема Геделя о неполноте формальной арифметики. 12. Логическая игра. 13. Логика второго порядка и определимость в арифметике. 14. Интерполяционная лемма Крейга и ее приложения. 7.4. Примерные контрольные и самостоятельные работы по дисциплине 8. Учебно-методическое и информационное обеспечение дисциплины ... Полное содержание

Подобный материал:

• Рабочей программы учебной дисциплины дв2 Математическая логика и теория алгоритмов, 50.1kb.
• Учебно-методический комплекс по дисциплине математическая логика и теория алгоритмов, 144.09kb.
• Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов шифр, 316.78kb.
• Рабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов», 69.99kb.
• Учебно-методический комплекс дисциплины «Математическая логика и теория алгоритмов», 376.44kb.
• Рабочая программа учебно-педагогической практики (летние лагерные сборы) на 2010-2011, 438.34kb.
• Рабочая программа дисциплины «Математическая логика и теория алгоритмов», 143.48kb.
• Рабочая программа учебно-исследовательской практики на 2011-2012 учебный год Направление, 225.84kb.
• Рабочая программа учебно-полевой практики по зоологии 2010-2011 учебный год, 254.69kb.
• Программа вступительного экзамена в магистратуру по направлению подготовки: 050100., 85.55kb.

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] стр. 41- 47, [2], стр.52-54

Тема 4. Применение АВ Понятия: РКС. Вопросы: Применение алгебры высказываний к анализу рассуждений и описанию релейно–контактных схем. Литература: [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] стр. 240-247, [2], стр. 124-136.

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

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

Литература:

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

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

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

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

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

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

№ раздела дисциплины	Наименование раздела дисциплины	Формы самостоятельной работы (ак. час. / зач. ед.)					Общая трудоемкость (ак. час. / зач. ед.)
		Конспектирование в рабочей тетради	Написание реферата	Работа с монографией	Выполнение контольных домашних работ	Составление аналитических таблиц
1.	Алгебра высказываний	2	2	2	4	1	11
2.	Исчисление высказываний	2	2	1	3	2	10
3	Логика предикатов	2	2	1	3	2	10
4	Исчисление предикатов	2	2	1	3	2	10
5	Рекурсивные функции	3	2	2	2	3	12
6	Машины Тьюринга	3	3	2	3	3	14
7	Дополнительные вопросы	3	3	2	4	3	15
	Итого:	17	16	11	22	16	82

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.

8. Разрешимые и неразрешимые аксиоматические теории.
   

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

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

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
   0	0	0	1	1	0	0	1
   0	0	1	0	1	0	1	0
   0	1	0	1	1	1	0	1
   0	1	1	0	1	1	1	1

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. Электронные материалы