Программа дисциплины «математическая логика» для направления 010400. 62 (прикладная математика и информатика) подготовки бакалавра Автор программы
Смотрите также:
- Программа дисциплины «Теория вероятностей и математическая статистика» для направления 010400
- Программа дисциплины «Современные технологии баз данных» для направления 010400
- Программа дисциплины Операционная система unix для направления 010400
- Программа нис: Разработка программных систем для направлений 010400
- Программа нис: Разработка программных систем для направлений 010400
- Программа дисциплины Электронные библиотечные ресурсы для направления 080500
- Программа дисциплины Методы и алгоритмы кодирования и передачи телевизионного сигнала для
федеральным государственным стандартом (ФГОС) по направлению 010400.62 (при кладная математика и информатика);
рабочим учебным планом университета по направлению 010400.62 (прикладная ма тематика и информатика), утвержденным в 2012 году.
знать:
уметь:
демонстрировать способность и готовность:
способностью владеть культурой мышления, умение аргументировано и ясно строить устную и письменную речь (ОК-1);
способностью владения навыками работы с компьютером как средством управления информацией (ОК-11);
способностью работать с информацией в глобальных компьютерных сетях (ОК-12);
способностью демонстрации общенаучных базовых знаний естественных наук, математики и информатики, понимание основных фактов, концепций, принципов теорий, связанных с прикладной математикой и информатикой (ПК-1);
способностью приобретать новые научные и профессиональные знания, используя современные образовательные и информационные технологии (ПК-2);
способностью понимать и применять в исследовательской и прикладной деятельности современный математический аппарат (ПК-3);
- ^
- ^
1. Дать определения декартова произведения двух множеств, декартова квадрата произвольного множества. Привести примеры. Записать формулы, выражающие число элементов декартова произведения и декартова квадрата.
2. Дать определение декартовой степени произвольного множества. Привести пример. Записать формулу, выражающую число элементов декартовой степени.
3. Дать определение булевой функции от n переменных; привести примеры.
4. Выписать таблицы истинности для следующих булевых функций: отрицание, дизъюнкция, конъюнкция, импликация, сложение modulo 2, эквивалентность.
5. Сформулировать основные тождества, выполняющиеся для булевых функций. Доказать какие-нибудь два из них.
6. Дать определения элементарной конъюнкции от данных переменных, её длины. Рассказать об экспоненциальных обозначениях в конъюнкциях.
7. Дать определение носителя (множества истинности) булевой функции.
8. Доказать лемму о равенстве двух булевых функций.
9. Доказать теорему о совершенной ДНФ. Сформулировать и объяснить следствие из этой теоремы. (Л3, 24.02.11.)
10. Дать определения дизъюнктивной нормальной формы (ДНФ) и её длины. Доказать, что любая ненулевая булева функция обладает разложением в ДНФ.
11. Изложить определение языка исчисления высказываний (ИВ): определения алфавита, слова, формативной последовательности, формулы.
12. Привести список 11 аксиом исчисления высказываний. Показать (на примере одной из них), что все они являются формулами ИВ.
13. Дать определение подстановки в слово. Привести пример. Сформулировать предложение о подстановке в формулу. Дать определения правил вывода ИВ (правил подстановки и правила modus ponens).
14. Дать определения формального вывода в исчислении высказываний и выводимой формулы. Объяснить, почему аксиомы выводимы. Доказать правило одновременной подстановки.
15. Привести (с обоснованием) пример формального вывода в ИВ (доказать выводимость формулы (A A)).
16. Дать определение формального вывода из гипотез (в ИВ). Дать определение формулы, выводимой из данного списка гипотез.
17. Привести пример формального вывода из гипотез.
18. Сформулировать и доказать лемму к теореме дедукции.
19. Сформулировать теорему дедукции. Сформулировать следствие из неё. Доказать теорему, обратную к теореме дедукции.
20. Доказать теорему дедукции в трёх частных случаях.
21. Доказать теорему дедукции в общем случае (в предположении, что она уже доказана в трёх частных случаях).
22. Дать определение интерпретации формулы ИВ (во множестве булевых функций).
23. Сформулировать критерий выводимости в ИВ.
24. Сформулировать и частично доказать критерий выводимости в ИВ.
25. Объяснить, как может быть определено понятие противоречивости ИВ (три варианта определения).
26. Доказать, что ИВ является непротиворечивым по любому из трёх вариантов определения противоречивости.
27. Дать определение n-местного предиката. Привести примеры. Дать определение множества истинности предиката.
28. Объяснить понятие квантора. Привести примеры.
29. Объяснить (на примерах) различие между свободными и связанными переменными в математике.
30. Рассказать о языке (исчисления предикатов) первого порядка.
31. Привести примеры сигнатур.
32. Сформулировать аксиомы арифметики G. Peano.
33. Рассказать об антиномии B. Russell’а. (Л8, 31.03.11.)
34. Сформулировать аксиомы теории множеств Zermelo − Fraenkel’я.
35. Дать определения терма и формулы для исчисления предикатов.
36. Привести список аксиом ИП. Сформулировать две аксиомы равенства.
37. Сформулировать правила вывода ИП (modus ponens и правила P. Bernays’а).
38. Доказать, что если x = y, то y = x. (Л10, 14.04.11.)
39. Дать определение машины с неограниченными регистрами (МНР), определение программы для такой машины.
40. Рассказать о реализации функций натурального аргумента на МНР. Привести программу вычисления суммы двух чисел.
41. Дать определение (частичной) вычислимой функции натурального аргумента. Объяснить связь с понятием последовательности натуральных чисел (возможно, лакунарной).
42. Доказать, что множество всех вычислимых функций счётно. Доказать существование невычислимой функции.
43. Рассказать о нумерации N2 и N3.
44. Рассказать о нумерации команд для МНР. Рассказать о нумерации конечных последовательностей.
45. Рассказать о нумерации программ для МНР. Объяснить, почему её можно рассматривать как вычислимую функцию. Привести примеры.
3.2.1. Универсальная вычислимая функция
46. Дать определение функции, универсальной для данного класса (множества) функций (натурального аргумента). Доказать, что универсальная функция существует тогда и только тогда, когда данный класс не пуст и не более чем счётен. Доказать существование универсальной вычислимой функции.
47. Доказать, что функция, универсальная в классе всех вычислимых всюду определённых функций, не является вычислимой. (Л12, 28.04.11.)
48. Доказать, что универсальная вычислимая функция не может быть продолжена до всюду определённой вычислимой функции.
49. Привести пример невычислимой функции.
50. Доказать, что не существует алгорифма, который определял бы по произвольной паре натуральных чисел, входит ли она в область определения универсальной вычислимой функции или нет.
51. Доказать, что не существует алгорифма проверки корректности программы. (Л13, 05.05.11.)
52. Рассказать о проверке программы на наличие вируса.
53. Дать определение разрешимого множества. Привести примеры.
54. Дать определение перечислимого множества. Привести примеры.
55. Доказать, что всякое разрешимое множество перечислимо.
56. Привести пример перечислимого, но не разрешимого множества.
3.3.1. Тезис A. Church’а
3.3.2. Свойства разрешимых и перечислимых множеств
3.3.3. Некоторые факты из теории чисел
3.3.4. Арифметические функции и множества
3.3.5. Доказательство теоремы K. Gödel’я
Н. К. Верещагин, А. Шень. Языки и исчисления. М., МЦНМО, 2008.
В. А. Душский. Исчисление высказываний и его свойства. М., МИЭМ, 2007.
П. С. Новиков. Элементы математической логики. М., «Наука», 1973.
В. А. Успенский, Н. К. Верещагин, В. Е. Плиско. Вводный курс математической логики. М., «Физматлит», 2004.
Г. П. Гаврилов, А. А. Сапоженко. Задачи и упражнения по дискретной математике. М., «Физматлит», 2005.
А. Н. Колмогоров, А. Г. Драгалин. Математическая логика. М., «УРСС», 2005.
А. Чёрч. Введение в математическую логику. М., URSS, 2009.
Ю. Ю. Кочетков. Вычислимые функции. М., МИЭМ, 2008.
И. А. Лавров, Л. Л. Максимова. Задачи по теории множеств, математической логике и теории алгоритмов. М., «Физматлит», 2004.
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Национальный исследовательский университет “Высшая школа экономикиˮ» Московский институт электроники и математики Национального исследовательского университета «Высшая школа экономики» Факультет прикладной математики и кибернетики Программа дисциплины «математическая логика» для направления 010400.62 (прикладная математика и информатика) подготовки бакалавра Автор программы: Кирилл Кириллович Андреев, кандидат физико-математических наук, доцент, kirill.andreyev@yandex.ru Одобрена на заседании кафедры высшей математики ___ ____________ 2012 г. И. о. зав. кафедрой Л. И. Кузьмина Рекомендована учебно-методической комиссией ФПМиК ___ ____________ 2012 г. Председатель Утверждена учёным советом ФПМиК ___ _____________2012 г. Учёный секретарь ________________________ Москва, 2012 Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры − разработчика программы. ^ Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчётности. Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010400.62 (прикладная математика и информатика), изучающих дисциплину математическая логика. Программа разработана в соответствии с: Дисциплина «математическая логика» относится к математическому и естественно-научному циклу и обеспечивает связь между различными дисциплинами как наука (наряду с теорией множеств), лежащая в основе всех разделов математики. Изучение дисциплины направлено на формирование перечисленных ниже элементов общекультурных и профессиональных компетенций. В задачи дисциплины входит: ознакомление с важнейшими понятиями и результатами классической математической логики; – овладение основными приёмами решения типовых задач по темам изучаемой дисциплины; развитие навыков чёткого, логического мышления; − ознакомление с прикладными аспектами математической логики; − осознание места математической логики в общей системе математических наук. ^ В результате освоения дисциплины студент должен: основные понятия формальной логики, элементарной теории множеств (операции над множествами и основные факты, связанные с понятием мощности множества), (булевой) логики высказываний (включая вопросы полноты систем булевых функций), общей теории формальных исчислений и, более подробно, (классического) исчисления высказываний, а также (теоретико-множественной) логики предикатов и её взаимоотношение с (формальным) исчислением предикатов; применять изученный математический аппарат при решении типовых задач, а также обнаруживать применимость аппарата математической логики для решения задач из родственных областей науки и её приложений; к изучению дальнейших понятий и теорий, разработанных в современной математической логике, а также к оценке степени адекватности предлагаемого аппарата к решению прикладных задач. Процесс изучения дисциплины направлен на формирование элементов следующих компетенций в соответствии с ФГОС ВПО по направлению «прикладная математика (бакалавры)»: А) общекультурных (ОК): Б) профессиональных (ПК): ^ Данная дисциплина относится к математическому и естественно-научному циклу (его вариативной части). Она входит в цикл «дискретная математика» (теория графов и комбинаторика, математическая логика, алгоритмы дискретной математики) и изучается после дисциплины «дискретная математика». ^
^
В контрольной работе студент должен самостоятельно применять изученные методы к решению поставленных задач и приготовить отчёт по результатам выполненной работы. На экзамене студент должен уметь выявлять сущность математических проблем, логически верно и аргументированно излагать доказательства теорем, понимать связи между различными понятиями курса. Оценки по всем формам текущего контроля выставляются по десятибалльной шкале. Преподаватель оценивает работу студентов на практических занятиях: активность студентов при обсуждении фундаментальных понятий курса, правильность решения задач и ответов на вопросы преподавателя на семинаре. Оценки за работу на семинарских и практических занятиях преподаватель выставляет в рабочую ведомость. Накопленная оценка по десятибалльной шкале за работу на практических занятиях определяется перед промежуточным или итоговым контролем − Оаудиторная. Преподаватель оценивает самостоятельную работу студентов: оценивается правиль ность выполнения домашних заданий, которые выдаются на практических занятиях, знание определений изучаемых понятий. Оценки за самостоятельную работу студента преподаватель выставляет в рабочую ведомость. Накопленная оценка по десятибалльной шкале за самостоятельную работу определяется перед промежуточным или итоговым контролем – Осам. работа. Накопленная оценка за текущий контроль учитывает результаты студента по текущему контролю следующим образом: Онакопленная= 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 Московский институт электроники и математики ФЭ, ФПМ, 2 курс Контрольная работа по математической логике (и теории алгорифмов) (домашняя) Осенний семестр 2009 года. К. К. Андреев. Комплект № 1 Билет № 1 1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением. (A → (C → B)), (D → A), C ├ (D → B). 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. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением. (A → B), (A → C) ├ (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.2. Декартова степень 1.1.3. Определение булевой функции § 1.2. Свойства булевых функций § 1.3. Дизъюнктивные нормальные формы (ДНФ) (Л2, 17.02.11) 1.3.1. Экспоненциальные обозначения в конъюнкциях 1.3.2. Лемма о равенстве двух булевых функций 1.3.3. Теорема о совершенной ДНФ 1.3.4. Определение ДНФ Глава 2. Логические исчисления § 2.1. Определение исчисления высказываний (ИВ) 2.1.1. Язык ИВ 2.1.2. Аксиомы ИВ 2.1.3. Правила вывода (Л4, 03.03.11) § 2.2. Формальные выводы 2.2.1. Определение формального вывода в ИВ 2.2.2. Пример формального вывода в ИВ 2.2.3. Формальный вывод из гипотез (Л5, 10.03.11) 2.2.4. Пример формального вывода из гипотез § 2.3. Теорема дедукции [доказательство есть на сайте] 2.3.1. Лемма к теореме дедукции 2.3.2. Формулировка теоремы дедукции 2.3.3. Доказательство теоремы дедукции в частных случаях 2.3.4. Доказательство теоремы в общем случае (Л6, 17.03.11) § 2.4. Критерий выводимости 2.4.1. Понятие интерпретации формулы 2.4.2. Формулировка критерия выводимости 2.4.3. Доказательство теоремы в одну сторону § 2.5. Непротиворечивость ИВ 2.5.1. Определение противоречивости 2.5.2. Доказательство непротиворечивости ИВ § 2.6. Исчисление предикатов (Л7, 24.03.11) 2.6.1. Определение предиката 2.6.2. Кванторы 2.6.3. Свободные и связанные переменные в математике 2.6.4. Язык исчисления предикатов (первого порядка) 2.6.5. Примеры сигнатур в математике 2.6.6. Понятия терма и формулы (Л9, 07.04.11) 2.6.7. Аксиомы и правила вывода ИП Глава 3. Теория алгорифмов § 3.1. Машина с неограниченными регистрами (МНР) 3.1.1. Определение МНР 3.1.2. Понятие вычислимой функции 3.1.3. Нумерация (Л11, 21.04.11) § 3.2. Универсальные функции 3.2.2. Некоторые алгорифмически неразрешимые проблемы 3.2.3. Разрешимые и перечислимые множества § 3.3. Теорема K. Gödel’я (Л14, 12.05.11) 57. Сформулировать тезис A. Church’а. Объяснить, почему он не может быть доказан как математическая теорема. 58. Доказать эквивалентность четырёх определений перечислимого множества. 59. Доказать теорему E. Post’а о разрешимых и перечислимых множествах. 60. Доказать, что множество перечислимо тогда и только тогда, когда оно является проекцией некоторого разрешимого множества. 61. Доказать китайскую теорему об остатках. 62. Дать определение β-функции K. Gödel’я и доказать соответствующие леммы. 63. Дать определения арифметической формулы и арифметического множества. 64. Доказать, что разрешимые и перечислимые множества арифметичны. 65. Доказать, что график вычислимой функции есть арифметическое множество. (Л16, 26.05.11.) 66. Доказать теорему Тарского. 67. Доказать теорему K. Gödel’я о неполноте арифметики. ^ А) Основная литература (базовые учебники и задачник) В) Программные средстваДля успешного освоения дисциплины студент использует программы на языке типа пакета Maple, а также программы, создаваемые ad hoc.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
