Программа дисциплины «математическая логика» - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Учебная программа Дисциплины б5 «Математическая логика и теория алгоритмов» 1 127.11kb.
Программа-минимум кандидатского экзамена по специальности 01. 1 37.04kb.
Рабочая учебная программа по дисциплине «Математическая логика» для... 1 140.83kb.
Рабочая программа дисциплины Математическая логика и теория алгоритмов 1 115.26kb.
Программа дисциплины «Математическая логика» 1 287.07kb.
Программа дисциплины [Введите название дисциплины] для направления/... 1 197.04kb.
Программа по дисциплине математическая логика кузьмина И. П. 1 31.64kb.
Рабочая программа дисциплины «Математическая логика и теория алгоритмов»... 3 543.74kb.
Программа дисциплины теория вероятностей и математическая статистика... 1 91.28kb.
Программа дисциплины Логика Карпенко И. А, к филос н. Москва, 2010... 1 107.8kb.
Программа вступительного экзамена по специальности для поступающих... 1 118.21kb.
Понятие алгоритма и его свойств 1 197.21kb.
Направления изучения представлений о справедливости 1 202.17kb.

Программа дисциплины «математическая логика» - страница №1/1



Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
«Национальный исследовательский университет
“Высшая школа экономикиˮ»

Московский институт электроники и математики Национального

исследовательского университета «Высшая школа экономики»


Факультет прикладной математики и кибернетики

Программа дисциплины «математическая логика»


для направления 010400.62 (прикладная математика и информатика) подготовки бакалавра

Автор программы:

Кирилл Кириллович Андреев, кандидат физико-математических наук, доцент, kirill.andreyev@yandex.ru

Одобрена на заседании кафедры высшей математики ___ ____________ 2012 г.
И. о. зав. кафедрой

Л. И. Кузьмина


Рекомендована учебно-методической комиссией ФПМиК ___ ____________ 2012 г.
Председатель

Утверждена учёным советом ФПМиК ___ _____________2012 г.


Учёный секретарь ________________________

Москва, 2012



Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедрыразработчика программы.



Область применения и нормативные ссылки


Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчётности.

Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010400.62 (прикладная математика и информатика), изучающих дисциплину математическая логика.

Программа разработана в соответствии с:


  • федеральным государственным стандартом (ФГОС) по направлению 010400.62 (прикладная математика и информатика);

  • рабочим учебным планом университета по направлению 010400.62 (прикладная математика и информатика), утвержденным в 2012 году.


Цели освоения дисциплины

Дисциплина «математическая логика» относится к математическому и естест­венно-научному циклу и обеспечивает связь между различными дисциплинами как наука (наряду с теорией множеств), лежащая в основе всех разделов математики. Изу­чение дисциплины направлено на формирование перечисленных ниже элементов обще­культурных и профессиональных компетенций.

В задачи дисциплины входит:

 ознакомление с важнейшими понятиями и результатами классической математи­ческой логики;

– овладение основными приёмами решения типовых задач по темам изучаемой дисциплины;

 развитие навыков чёткого, логического мышления;

− ознакомление с прикладными аспектами математической логики;

− осознание места математической логики в общей системе математических наук.


Компетенции обучающегося, формируемые в результате освоения дисциплины

В результате освоения дисциплины студент должен:




  • знать:

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



  • уметь:

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

  • демонстрировать способность и готовность:

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

Процесс изучения дисциплины направлен на формирование элементов следующих ком­петенций в соответствии с ФГОС ВПО по направлению «прикладная математика (бакалавры)»:


А) общекультурных (ОК):


  • способностью владеть культурой мышления, умение аргументировано и ясно строить устную и письменную речь (ОК-1);

  • способностью владения навыками работы с компьютером как средством управления информацией (ОК-11);

  • способностью работать с информацией в глобальных компьютерных сетях (ОК-12);

Б) профессиональных (ПК):




  • способностью демонстрации общенаучных базовых знаний естественных наук, математики и информатики, понимание основных фактов, концепций, принципов теорий, связанных с прикладной математикой и информатикой (ПК-1);

  • способностью приобретать новые научные и профессиональные знания, используя современные образовательные и информационные технологии (ПК-2);

  • способностью понимать и применять в исследовательской и прикладной деятельности современный математический аппарат (ПК-3);



Место дисциплины в структуре образовательной программы

Данная дисциплина относится к математическому и естественно-научному циклу (его вариативной части). Она входит в цикл «дискретная математика» (теория графов и комбина­торика, математическая логика, алгоритмы дискретной математики) и изучается после дисциплины «дискретная математика».



Тематический план учебной дисциплины






Название раздела

Всего часов

Аудиторные часы

Самостоя­тельная работа

Лек-ции




Практи-ческие занятия

1

Классическая логика, её предмет и аппарат

24

6




6

12

2

Математика как дедуктивная наука. Теория множеств и её парадоксы

24

6




6

12

3

Логика высказываний

28

7




7

14

4

Общее представление о формальном исчислении и классическое исчисле­ние высказываний

34

8




9

17

5

Логика и исчисление предикатов

34

9




8

17

























Итого:

144

36




36

72

Формы контроля знаний студентов





Тип контроля

Форма контроля

Семестр

Параметры

2










Текущий

(неделя)


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

7










Письменная работа
















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

14










Письменная работа









































































Итого-вый

Экзамен

*










Устный


    1. Критерии оценки знаний, навыков



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

На экзамене студент должен уметь выявлять сущность математических проблем, логиче­ски верно и аргументированно излагать доказательства теорем, понимать связи между различ­ными понятиями курса.

Оценки по всем формам текущего контроля выставляются по десятибалльной шкале.

    1. Порядок формирования оценок по дисциплине

Преподаватель оценивает работу студентов на практических занятиях: активность студентов при обсуждении фундаментальных понятий курса, правильность решения задач и ответов на вопросы преподавателя на семинаре. Оценки за работу на семинарских и практических заня­тиях преподаватель выставляет в рабочую ведомость. Накопленная оценка по десятибалльной шкале за работу на практических занятиях определяется перед промежуточным или итоговым контролем − Оаудиторная.

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

Накопленная оценка за текущий контроль учитывает результаты студента по текущему контролю следующим образом:

Онакопленная= 0,5* Отекущий + 0,25* Оауд + 0,25* Осам.работа

где Отекущий рассчитывается как взвешенная сумма всех форм текущего контроля, предусмот­ренных в РУП:



Отекущий = 0,5·Ок. р. 1 + 0,5·Ок. к. 2 .

Способ округления накопленной оценки текущего контроля производится в пользу студента.

Результирующая оценка за дисциплину рассчитывается следующим образом:

За семестр:



Орезульт = 0,5* Онакопл + 0,5*·Оэкз

Способ округления накопленной оценки промежуточного (итогового) контроля в форме зачёта производится в пользу накопленной оценки.

На пересдаче студенту не предоставляется возможность получить дополнительный балл для компенсации оценки за текущий контроль.

На экзамене студент может получить дополнительный вопрос (дополнительную практическую задачу, решить к пересдаче домашнее задание), ответ на который оценивается в 1 балл.

В диплом выставляется результирующая оценка по учебной дисциплине, которая формируется по следующей формуле:

Орезульт =0,5·Онакопл + 0,5·Оитоговый

Способ округления результирующей оценки по учебной дисциплине: в пользу накопленной оценки.



ВНИМАНИЕ: оценка за итоговый контроль блокирующая, при неудовлетворительной итоговой оценке она равна результирующей.


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


Изложение строится по разделам и темам. Содержание темы может распределяться по лекционным и практическим занятиям.

1. Классическая логика, её предмет и аппарат

Предмет логики, логика и язык. Знак, его предмет и смысл. Язык как знаковая сис­тема. Понятие. Суждение и высказывание. Разделение высказываний на истинные и лож­ные: воз­можность альтернативных точек зрения и, как следствие, иных неклассических логик.

Умозаключения и рассуждения, правильные и неправильные рассуждения.

Различные уровни анализа высказываний: представление о логике высказываний и логи­ческих предикатов.
Аудиторная работа − 12 часов.

Самостоятельная работа − 12 часов:

− подготовка к лекциям и практическим занятиям;

− выполнение домашних работ, задаваемых на практических занятиях;

Для освоения раздела предусмотрено обсуждение фундаментальных понятий дисцип­лины, их взаимосвязей, решение теоретических и вычислительных задач.
2. Математика как дедуктивная наука. Теория множеств и её парадоксы

Доказательства в математике до теории множеств. Представление о евклидовом аксио­матическом методе.

Основные понятия теории множеств. Операции над множествами, их изображение с по­мощью диаграмм Венна. Взаимно однозначное соответствие; эквивалентность и мощ­ность множеств. Счётные и несчётные множества. Теорема Кантора; существование мно­жеств сколь угодно больших мощностей. Парадоксы теории множеств − сигнал к анализу логического аппа­рата математики.

Возникновение современной математической логики и её прикладные аспекты.

Аудиторная работа − 12 часов.

Самостоятельная работа − 12 часов:

− подготовка к лекциям и практическим занятиям;

− выполнение домашних работ, задаваемых на практических занятиях;

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

Логические связки и соответствующие им таблицы истинности. Высказывательные формы («высказывания с переменными») и соответствующие им булевы функции. Язык логики высказываний.

Интерпретации логических формул. Логические законы и логическое следование. Обще­значимые (тавтологии) и выполнимые логические формулы. Совместные множества логических формул. Эффективная распознаваемость этих свойств.

Важнейшие логические законы. Примеры правильных (и неправильных) схем умо­за­ключений. Полные системы булевых функций. Совершенные дизъюнктивная и конъ­юнктивная нормальные формы. Важнейшие примеры полных систем булевых функций. Примеры непол­ных систем.

Проблема эффективного распознавания полноты конечных систем булевых функ­ций. Невозможность её решения «по определению». Теорема Поста о полноте как инстру­мент эф­фективного распознавания полноты.

Аудиторная работа − 14 часов.

Самостоятельная работа − 14 часов:

− подготовка к лекциям и практическим занятиям;

− выполнение домашних работ, задаваемых на практических занятиях;

− подготовка к контрольной работе № 1.

Для освоения раздела предусмотрено обсуждение фундаментальных понятий дисцип­лины, их взаимосвязей, решение теоретических и вычислительных задач.
4. Общее представление о формальном исчислении и классическое исчисление высказы­ваний

Язык, аксиомы и правила вывода формального исчисления. Формальный вывод и выво­димые формулы. Общие свойства формальных выводов. Требование эффективной распозна­ваемости формальных выводов.

Логические исчисления.

Классическое исчисление высказываний (ИВ), примеры выводов в нём. Эффектив­ная распознаваемость выводов в ИВ.

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

Использование гипотез в математических рассуждениях. Формальный вывод из гипотез. Теорема дедукции и её применения.

Разрешимые исчисления. Интерпретации формул ИВ. Критерий выводимости для ИВ. Разрешимость и непротиворечивость ИВ.
Аудиторная работа − 17 часов.

Самостоятельная работа − 17 часов:

− подготовка к лекциям и практическим занятиям;

− выполнение домашних работ, задаваемых на практических занятиях.

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

Декартово произведение множеств и декартова степень. Определения n-местного преди­ката и его множества истинности.

Операции над предикатами: логические связки и кванторы. Свободные и связанные пе­ременные (их вхождение в формулы). Преобразование множеств истинности предика­тов под действием логических связок и кванторов. Вынесение кванторов из-под отрица­ния и взаимная выразимость кванторов.

Язык логики (исчисления) предикатов 1-го порядка. Термы и формулы. Интерпре­тации формул. Выполнимые и общезначимые формулы. Общезначимость подстановок и пропозицио­нальные тавтологии; иные общезначимые формулы.

Формулировка исчисления предикатов 1-го порядка. Примеры выводов в нём. Кри­терий выводимости для исчисления предикатов. Непротиворечивость исчисления преди­катов.
Аудиторная работа − 17 часов.

Самостоятельная работа − 17 часов:

− подготовка к лекциям и практическим занятиям;

− выполнение домашних работ, задаваемых на практических занятиях.

− подготовка к контрольной работе № 2.

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




Образовательные технологии


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



Оценочные средства для текущего контроля и аттестации студента

    1. Тематика заданий текущего контроля



Примерные варианты контрольной работы № 1
Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. К. К. Андреев. Комплект № 1


Билет 1

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.


(A → (C B)), (DA), C ├ (DB).
2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?
((x)(y)(z)(P(xy, z) → (P(x, z)  P(y, z))) → Q(16)).
Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.
3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

((((x)P(x, z)) → Q(y)))  (((z)P(x, z)) & (((x)Q(x)))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. К. К. Андреев. Комплект № 1


Билет 2

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(AB), (AC) ├ (A → (B & C)).
2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(Q(k)  ((t)P(t, k))) → ((m)P(2t, k)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:


Q(y , z) → (((((x)P(x)) → ((y)Q(x , y)))) & P( y) & ((y)Q(z, y))).

Примерные варианты контрольной работы № 2

Московский институт электроники и математики

Контрольная работа по математической логике

«Вычислимые функции»

Весенний семестр 2011 года. К. К. Андреев. Комплект № 1
Билет 1

1. Найти программу, имеющую номер 21365. Что она вычислит, если в первом ре­гистре стоит число 17, а в остальных регистрах − нули?

2. Написать программу, вычисляющую следующую функцию:

f(n) =

Найти её номер.



3. Рассмотрим функцию

h(n) =

Здесь Φ − универсальная функция от двух переменных. Вычислить значения h(22) и h(23).

Московский институт электроники и математики

Контрольная работа по математической логике

«Вычислимые функции»

Весенний семестр 2011 года. К. К. Андреев. Комплект № 1


Билет 2

1. Найти программу, имеющую номер 11162. Что она вычислит, если в первом ре­гистре стоит число 12, а в остальных регистрах − нули?

2. Написать программу, вычисляющую следующую функцию:

f(n) =

Найти её номер.



3. Рассмотрим функцию

h(n) =

Здесь Φ − универсальная функция от двух переменных. Вычислить значения h(20) и h(18).



Вопросы для оценки качества освоения дисциплины
Примерный перечень вопросов к экзамену по всему курсу или к каждому промежуточному и итоговому контролю для самопроверки

Вопросы к экзамену по всему курсу
Глава 1. Булевы функции (Л1, 10.02.11)
§ 1.1. Основные понятия
1.1.1. Декартово произведение

  1. 1. Дать определения декартова произведения двух множеств, декартова квадрата произ­вольного множества. Привести примеры. Записать формулы, выражающие число элементов де­картова произведения и декартова квадрата.

1.1.2. Декартова степень

  1. 2. Дать определение декартовой степени произвольного множества. Привести пример. За­писать формулу, выражающую число элементов декартовой степени.

1.1.3. Определение булевой функции

  1. 3. Дать определение булевой функции от n переменных; привести примеры.

  2. 4. Выписать таблицы истинности для следующих булевых функций: отрицание, дизъ­юнк­ция, конъюнкция, импликация, сложение modulo 2, эквивалентность.

§ 1.2. Свойства булевых функций


  1. 5. Сформулировать основные тождества, выполняющиеся для булевых функций. До­ка­зать какие-нибудь два из них.

§ 1.3. Дизъюнктивные нормальные формы (ДНФ) (Л2, 17.02.11)
1.3.1. Экспоненциальные обозначения в конъюнкциях

  1. 6. Дать определения элементарной конъюнкции от данных переменных, её длины. Рассказать об экс­по­ненциальных обозначениях в конъюнкциях.

1.3.2. Лемма о равенстве двух булевых функций

  1. 7. Дать определение носителя (множества истинности) булевой функции.

  2. 8. Доказать лемму о равенстве двух булевых функций.



1.3.3. Теорема о совершенной ДНФ

  1. 9. Доказать теорему о совершенной ДНФ. Сформулировать и объяснить следствие из этой теоремы. (Л3, 24.02.11.)

1.3.4. Определение ДНФ

  1. 10. Дать определения дизъюнктивной нормальной формы (ДНФ) и её длины. Доказать, что любая ненулевая булева функция обладает разложением в ДНФ.

Глава 2. Логические исчисления
§ 2.1. Определение исчисления высказываний (ИВ)
2.1.1. Язык ИВ

  1. 11. Изложить определение языка исчисления высказываний (ИВ): определения алфа­вита, слова, формативной последовательности, формулы.

2.1.2. Аксиомы ИВ

  1. 12. Привести список 11 аксиом исчисления высказываний. Показать (на примере одной из них), что все они являются формулами ИВ.

2.1.3. Правила вывода (Л4, 03.03.11)

  1. 13. Дать определение подстановки в слово. Привести пример. Сформулировать предложе­ние о подста­новке в формулу. Дать определения правил вывода ИВ (правил подста­новки и правила modus ponens).

§ 2.2. Формальные выводы
2.2.1. Определение формального вывода в ИВ

  1. 14. Дать определения формального вывода в исчислении высказываний и выводимой фор­мулы. Объяснить, почему аксиомы выводимы. Доказать правило одновременной подстановки.

2.2.2. Пример формального вывода в ИВ

  1. 15. Привести (с обоснованием) пример формального вывода в ИВ (доказать выводи­мость формулы (A A)).

2.2.3. Формальный вывод из гипотез (Л5, 10.03.11)

  1. 16. Дать определение формального вывода из гипотез (в ИВ). Дать определение фор­мулы, выводимой из данного списка гипотез.

2.2.4. Пример формального вывода из гипотез

  1. 17. Привести пример формального вывода из гипотез.

§ 2.3. Теорема дедукции

[доказательство есть на сайте]


2.3.1. Лемма к теореме дедукции

  1. 18. Сформулировать и доказать лемму к теореме де­дукции.

2.3.2. Формулировка теоремы дедукции

  1. 19. Сформулировать теорему дедукции. Сформулировать следствие из неё. Доказать теорему, обратную к теореме дедук­ции.

2.3.3. Доказательство теоремы дедукции в частных случаях

  1. 20. Доказать теорему дедукции в трёх частных случаях.

2.3.4. Доказательство теоремы в общем случае (Л6, 17.03.11)

  1. 21. Доказать теорему дедукции в общем случае (в предположении, что она уже доказана в трёх частных случаях).

§ 2.4. Критерий выводимости


2.4.1. Понятие интерпретации формулы

  1. 22. Дать определение интерпретации формулы ИВ (во множестве булевых функций).

2.4.2. Формулировка критерия выводимости

  1. 23. Сформулировать критерий выводимости в ИВ.

2.4.3. Доказательство теоремы в одну сторону

  1. 24. Сформулировать и частично доказать критерий выводимости в ИВ.

§ 2.5. Непротиворечивость ИВ
2.5.1. Определение противоречивости

  1. 25. Объяснить, как может быть определено понятие противоречивости ИВ (три вари­анта определения).

2.5.2. Доказательство непротиворечивости ИВ

  1. 26. Доказать, что ИВ является непротиворечивым по любому из трёх вариантов определе­ния противоречивости.

§ 2.6. Исчисление предикатов (Л7, 24.03.11)
2.6.1. Определение предиката

  1. 27. Дать определение n-местного предиката. Привести примеры. Дать определение множества истинности предиката.

2.6.2. Кванторы

  1. 28. Объяснить понятие квантора. Привести примеры.

2.6.3. Свободные и связанные переменные в математике

  1. 29. Объяснить (на примерах) различие между свободными и связанными переменными в математике.

2.6.4. Язык исчисления предикатов (первого порядка)

  1. 30. Рассказать о языке (исчисления предикатов) первого порядка.

2.6.5. Примеры сигнатур в математике

  1. 31. Привести примеры сиг­натур.



  2. 32. Сформулировать аксиомы арифметики G. Peano.

  3. 33. Рассказать об антиномии B. Russell’а. (Л8, 31.03.11.)

  4. 34. Сформулировать аксиомы теории множеств Zermelo − Fraenkel’я.

2.6.6. Понятия терма и формулы (Л9, 07.04.11)

  1. 35. Дать определения терма и формулы для исчисления предикатов.

2.6.7. Аксиомы и правила вывода ИП

  1. 36. Привести список аксиом ИП. Сформулировать две аксиомы равенства.

  2. 37. Сформулировать правила вывода ИП (modus ponens и правила P. Bernays’а).

  3. 38. Доказать, что если x = y, то y = x. (Л10, 14.04.11.)


Глава 3. Теория алгорифмов
§ 3.1. Машина с неограниченными регистрами (МНР)

3.1.1. Определение МНР



  1. 39. Дать определение машины с неограниченными регистрами (МНР), определение про­граммы для такой машины.

3.1.2. Понятие вычислимой функции

  1. 40. Рассказать о реализации функций натурального аргумента на МНР. Привести программу вычисления суммы двух чисел.

  2. 41. Дать определение (частичной) вычислимой функции натурального аргумента. Объяс­нить связь с понятием последовательности натуральных чисел (возможно, лакунарной).

  3. 42. Доказать, что множество всех вычислимых функций счётно. Доказать существова­ние невычислимой функции.

3.1.3. Нумерация (Л11, 21.04.11)

  1. 43. Рассказать о нумерации N2 и N3.

  2. 44. Рассказать о нумерации команд для МНР. Рассказать о нумерации конечных последовательностей.

  3. 45. Рассказать о нумерации программ для МНР. Объяснить, почему её можно рассматри­вать как вычислимую функцию. Привести примеры.

§ 3.2. Универсальные функции

  1. 3.2.1. Универсальная вычислимая функция

  2. 46. Дать определение функции, универсальной для данного класса (множества) функций (натурального аргумента). Доказать, что универсальная функция существует тогда и только то­гда, когда данный класс не пуст и не более чем счётен. Доказать существование универсальной вычислимой функции.

  3. 47. Доказать, что функция, универсальная в классе всех вычислимых всюду определён­ных функций, не является вычислимой. (Л12, 28.04.11.)



  1. 48. Доказать, что универсальная вычислимая функция не может быть продолжена до всюду определённой вычислимой функции.

  2. 49. Привести пример невычислимой функции.

3.2.2. Некоторые алгорифмически неразрешимые проблемы

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

  2. 51. Доказать, что не существует алгорифма проверки корректности программы. (Л13, 05.05.11.)

  3. 52. Рассказать о проверке программы на наличие вируса.



3.2.3. Разрешимые и перечислимые множества

  1. 53. Дать определение разрешимого множества. Привести примеры.

  2. 54. Дать определение перечислимого множества. Привести примеры.

  3. 55. Доказать, что всякое разрешимое множество перечислимо.

  4. 56. Привести пример перечислимого, но не разрешимого множества.

§ 3.3. Теорема K. Gödel’я (Л14, 12.05.11)

  1. 3.3.1. Тезис A. Church’а

57. Сформулировать тезис A. Church’а. Объяснить, почему он не может быть доказан как математическая теорема.

  1. 3.3.2. Свойства разрешимых и перечислимых множеств

58. Доказать эквивалентность четырёх определений перечислимого множества.

59. Доказать теорему E. Post’а о разрешимых и перечислимых множествах.

60. Доказать, что множество перечислимо тогда и только тогда, когда оно является проекцией некоторого разрешимого множества.


  1. 3.3.3. Некоторые факты из теории чисел



61. Доказать китайскую теорему об остатках.

62. Дать определение β-функции K. Gödel’я и доказать соответствующие леммы.



  1. 3.3.4. Арифметические функции и множества

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

64. Доказать, что разрешимые и перечислимые множества арифметичны.

65. Доказать, что график вычислимой функции есть арифметическое множество. (Л16, 26.05.11.)


  1. 3.3.5. Доказательство теоремы K. Gödel’я

66. Доказать теорему Тарского.

67. Доказать теорему K. Gödel’я о неполноте арифметики.


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



А) Основная литература (базовые учебники и задачник)


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

  2. В. А. Душский. Исчисление высказываний и его свойства. М., МИЭМ, 2007.

  3. П. С. Новиков. Элементы математической логики. М., «Наука», 1973.

  4. В. А. Успенский, Н. К. Верещагин, В. Е. Плиско. Вводный курс математиче­ской логики. М., «Физматлит», 2004.

  5. Г. П. Гаврилов, А. А. Сапоженко. Задачи и упражнения по дискретной матема­тике. М., «Физматлит», 2005.

Б) Дополнительная литература





  1. А. Н. Колмогоров, А. Г. Драгалин. Математическая логика. М., «УРСС», 2005.

  2. А. Чёрч. Введение в математическую логику. М., URSS, 2009.

  3. Ю. Ю. Кочетков. Вычислимые функции. М., МИЭМ, 2008.

  4. И. А. Лавров, Л. Л. Максимова. Задачи по теории множеств, математиче­ской ло­гике и теории алгоритмов. М., «Физматлит», 2004.



В) Программные средства

Для успешного освоения дисциплины студент использует программы на языке типа пакета Maple, а также программы, создаваемые ad hoc.









Я не танцую, но с удовольствием подержу вас, пока вы танцуете. «Плейбой»
ещё >>