Лекции по математической логике миэм, фпм, 2 курс, 4 семестр Весенний семестр 2010/2011 учебного года Группы м-41−46



Скачать 60.15 Kb.
Дата03.12.2012
Размер60.15 Kb.
ТипЛекции



26.10.12, М.

Лекции

по математической логике
МИЭМ, ФПМ, 2 курс, 4 семестр

Весенний семестр 2010/2011 учебного года

Группы М-41−46

Лектор – доцент, к. ф.-м. н. К. К. Андреев

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

Глава 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.)

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

  5. 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’я о неполноте арифметики.

Похожие:

Лекции по математической логике миэм, фпм, 2 курс, 4 семестр Весенний семестр 2010/2011 учебного года Группы м-41−46 iconЛекции по математической логике миэм, фэ, 2 курс, 3 семестр Осенний семестр 2009/2010 учебного года Группы к-31, 32
Дать определения декартова произведения двух множеств, декартова квадрата произ­вольного множества. Привести примеры. Записать формулы,...
Лекции по математической логике миэм, фпм, 2 курс, 4 семестр Весенний семестр 2010/2011 учебного года Группы м-41−46 iconЛекции по линейной алгебре и аналитической геометрии фпм, 2 курс Осенний семестр 2010/2011 учебного года
Дать определение скалярного произведения, привести примеры. (Стр. 6, 7 и 9 методички.)
Лекции по математической логике миэм, фпм, 2 курс, 4 семестр Весенний семестр 2010/2011 учебного года Группы м-41−46 iconЛекции по линейной алгебре и аналитической геометрии фпм, 1 курс Весенний семестр 2009/2010 учебного года
...
Лекции по математической логике миэм, фпм, 2 курс, 4 семестр Весенний семестр 2010/2011 учебного года Группы м-41−46 iconКалендарно-тематический план практических занятий по математике на весенний семестр 2009-2010 учебного года 1 курс

Лекции по математической логике миэм, фпм, 2 курс, 4 семестр Весенний семестр 2010/2011 учебного года Группы м-41−46 iconРасписание занятий 6 курса лечебного факультета на весенний семестр 2009 2010 учебного года

Лекции по математической логике миэм, фпм, 2 курс, 4 семестр Весенний семестр 2010/2011 учебного года Группы м-41−46 iconРасписание экзаменов 1 курс осенний семестр (1) 2011-2012 учебного года

Лекции по математической логике миэм, фпм, 2 курс, 4 семестр Весенний семестр 2010/2011 учебного года Группы м-41−46 iconПрограмма экзамена по курсу тфкп 2-й курс, 251-253 группы, весенний семестр 2003/2004 учебного года
Определение и свойства комплексных чисел и арифметических операций над ними. Геометрическая интерпретация комплексных чисел. Аргумент...
Лекции по математической логике миэм, фпм, 2 курс, 4 семестр Весенний семестр 2010/2011 учебного года Группы м-41−46 iconГрафик занятости преподавателей кафедры теории и истории музыки на 2-ой семестр 2010/2011 учебного года

Лекции по математической логике миэм, фпм, 2 курс, 4 семестр Весенний семестр 2010/2011 учебного года Группы м-41−46 iconТематический план лекций по биологии с экологией на 2-й семестр 2010-2011 учебного года для студентов лечебного и педиатрического факультетов

Лекции по математической логике миэм, фпм, 2 курс, 4 семестр Весенний семестр 2010/2011 учебного года Группы м-41−46 iconПрограмма курса Для студентов всех специальностей, всех форм обучения курс 2 семестр 3 Экзамен 3 семестр Лекции 34 часа
Филиал Санкт-Петербургского государственного инженерно-экономического университета в г. Апатиты
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org