В.Б. Шехтман - Программа и задачи курса ЕНС - Математическая логика и алгоримы (1162046)
Текст из файла
Программа и задачи курса ЕНС«Математическая логика и алгоримы»Лектор — Валентин Борисович Шехтман8 семестр, 2006 г.Программа курсаЛогика высказываний1. Высказывания. Пропозициональные формулы. Оценка пропозициональных переменных. Значение формулы при оценке. Эквивалентные формулы. Тавтологии2. Аксиомы и правила вывода классического исчисления высказываний (CL) и интуиционистского исчисления высказываний (IL).3. Доказательства (выводы) в исчислениях CL и IL.
Теоремы (выводимые формулы). Доказательство формулы A→A.4. Теорема корректности для CL.5. Вывод из множества формул (теории) Γ (в CL и IL). Теорема дедукции.6. Лемма о доказательстве «от противного». Лемма о «разборе случаев».7. Непротиворечивость и (синтаксическая) полнота пропозициональной теории. Свойства полных теорий.8. Лемма Линденбаума. Выводимость формулы ¬¬A→A. Теорема о (семантической) полноте CL.9. Интуиционистская логика. Шкала Крипке.
Модель Крипке. Истинность формулы в точке («мире») моделиКрипке. Принцип сохранности.10. Теорема корректности для IL относительно моделей Крипке. Недоказуемость закона исключенного третьего (p ∨ ¬p) в IL.Логика предикатов11. Сигнатура. Термы и формулы данной сигнатуры. Свободные и связанные вхождения переменной в формулу. Параметры формулы. Замкнутые формулы (предложения).12. Интерпретация сигнатуры. Оцененные термы и формулы. Значение оцененного терма в интерпретации.Значение оцененной формулы в интерпретации. Нормальные интерпретации.13.
Выполнимость и общезначимость замкнутой формулы. Универсальное замыкание. Общезначимость произвольной формулы.14. Теория первого порядка. Модель теории. Выполнимая теория. Примеры теорий первого порядка: теорияграфов; теория полугрупп; теория строгого частичного порядка без максимальных элементов — выполнимая теория, не имеющая конечных моделей.15. Свободная подстановка терма вместо переменной в формулу.16. Классическое исчисление предикатов сигнатуры Ω (PCΩ ). Вывод.
Теоремы. Вывод из данного множестваформул.17. Теорема дедукции для PCΩ .18. Примеры теорем и допустимых правил исчисления предикатов: правила Бернайса; правила монотонности;формулы ¬ ∃ xϕ ↔ ∀ x¬ϕ, ¬ ∀ xϕ ↔ ∃ x¬ϕ; формулы ∀ xϕ(x) → ∀ yϕ(y), ∃ xϕ(x) → ∃ yϕ(y) (с ограничениями).19. Лемма об истинности универсального замыкания. Леммы о двойной подстановке в термы и формулы.Теорема корректности для PCΩ .20.
Логическое следование. Теорема корректности и теорема о непротиворечивости для теорий первого порядка.21. Исчисление предикатов с равенством PC=Ω . Лемма о замене термов на равные им термы в атомарных формулах. Теоремы корректности и непротиворечивости для PC=Ω и для теорий первого порядка с равенством.122. Элементарная теория данной интерпретации. Полные теории первого порядка. Свойства полных теорий.Лемма Линденбаума.23. Экзистенциально полные теории. Теории Хенкина.24. Лемма о свежих константах. Лемма о расширении непротиворечивой теории до непротиворечивой теорииХенкина.25. Построение счетной модели для полной и экзистенциально полной теории без равенства в счетной сигнатуре.26.
Теорема Гёделя о полноте для исчисления предикатов без равенства (в двух формах: существование моделидля непротиворечивой теории и доказуемость общезначимых формул). Эквивалентность выводимости илогического следования. Теорема Лёвенгейма – Сколема для теорий первого порядка без равенства.27. Теорема о существовании нормальной модели для непротиворечивой теории с равенством.28.
Полнота исчисления предикатов с равенством. Теорема Лёвенгейма – Сколема для теорий первого порядкас равенством.29. Теорема компактности Гёделя – Мальцева для теорий первого порядка. Признак существования бесконечных моделей.30. Изоморфизм интерпретаций. Сохранение значений термов и формул при изоморфизме.31. Изоморфность и элементарная эквивалентность интерпретаций. Существование нестандартных моделейарифметики.32. Полнота теории как элементарная эквивалентность всех ее моделей.33. Сильная категоричность и счетная категоричность. Полнота счетно категоричных теорий без конечныхмоделей (признак Вота). Примеры счетной категоричности.34.
Сильная категоричность элементарной теории конечной интерпретации в конечной сигнатуре.Алгоритмы35. Общее понятие алгоритма. Система Поста. Вывод в системе Поста.36. Вариант определения выводимости в системе Поста с использованием одновременной подстановки. Выводимые (производные) правила. Лемма о постановке в выводимые правила.37. Перечислимые и разрешимые множества слов. Сохранение перечислимости для объединений и пересечений. Сохранение разрешимости для булевских операций.38.
Вычислимые частичные словарные функции. Разрешимость как вычислимость характеристической функции. Сохранение перечислимости для проекций.39. Кодирование систем Поста. Гёделев номер системы Поста. Построение универсальной системы Поста (теорема о нумерации).40. Построение перечислимого неразрешимого множества натуральных чисел.41.
Преобразование системы Поста в теорию первого порядка.42. Перечислимые и разрешимые теории. Перечислимость исчисления предикатов в конечной сигнатуре. Перечислимость теории с перечислимым множеством аксиом.43. Теорема Чёрча о неразрешимости исчисления предикатов в подходящей сигнатуре.Литература1. Н. К. Верещагин, А. Х. Шень. Лекции по математической логике и теории алгоритмов.
Часть 2: Языки ииcчисления. M., МЦНМО, 2000. Электронная версия на http://www.mccme.ru.2. В. А. Успенский, Н. К. Верещагин, В. Е. Плиско. Вводный курс математической логики. Издательство МГУ.М., 1991 и 1997. Физматлит, 2002.3. Справочная книга по математической логике под ред. Дж. Барвайса. Ч. 1. Теория моделей. М., Наука,1982.4. Э.
Мендельсон. Введение в математическую логику. М., 1984.5. П. Мартин-Лёф. Очерки по конструктивной математике. М., Мир, 1975.Последняя компиляция: 18 мая 2006 г.Обновления документа — на сайтах http://dmvn.mexmat.net,http://dmvn.mexmat.ru.Об опечатках и неточностях пишите на dmvn@mccme.ru.2Задачи к экзамену1. Докажите разрешимость множества всех чётных чисел.2. Докажите, что если f — вычислимая (частичная) функция из N в N, то область определения и множествозначений f перечислимы.3. Докажите, что формула Даммета (p → q) ∨ (q → p) истинна в линейно упорядоченных моделях Крипке,но невыводима в IL.4.
Пусть Т — полная теория с равенством, имеющая конечную модель. Докажите, что Т не имеет бесконечных моделей.5. Докажите, что сложение натуральных чисел является вычислимой функцией.6. Докажите, что формула p → ¬¬p является теоремой IL.7. Докажите, что тождественная функция, заданная на словах конечного алфавита, вычислима.8. Докажите разрешимость одноэлементного множества натуральных чисел.9.
Докажите, что не существует теории первого порядка в сигнатуре {+, ×, =, 0, 1}, моделями которой являются в точности все конечные поля. Аналогично — для полей ненулевой характеристики.10. Постройте формулу 1-го порядка без равенства, имеющую 2-элементную модель, но не имеющую 1-элементных моделей.11. Переведите текст в логическую символику (в подходящей сигнатуре) и постройте конечную модель полученной теории:12.13.14.15.16.17.18.19.20.Существуют по крайней мере две прямые.
Каждая прямая содержит более одной точки. Через любые 2различные точки проходит ровно одна прямая. Прямые параллельны тогда и только тогда, когда они неимеют общих точек. Через любую точку, не лежащую на данной прямой, проходит ровно одна прямая,параллельная данной.Постройте формулу 1-го порядка без равенства, имеющую 3-элементную модель, но не имеющую 2-элементных моделей.Докажите, что формула ¬(p ∨ q) → ¬p ∧ ¬q является теоремой CL.Докажите, что пустое множество слов в конечном алфавите разрешимо.Используя теорему о полноте, докажите, что формула ¬(p ∨ q) → ¬p ∧ ¬q является теоремой IL.Докажите, что формула ∀ x ∃ yP (x, y) → ∃ y ∀ xP (x, y) невыводима в исчислении предикатов.Пусть ϕn := ∀ x1 . . .
∀ xn ∃ x0 (x0 6= x1 ∧ . . . ∧ x0 6= xn ) (при n > 0). Докажите, что теория Т = {ϕn | n > 0}полна (в сигнатуре с одним символом =).Докажите, что если ⊢CL A, то ⊢IL ¬¬A (теорема Гливенко).Докажите, что композиция вычислимых всюду определенных функций из N в N вычислима.Докажите, что элементарная теория поля Q в сигнатуре {+, ×, =, 0, 1} не является счетно категоричной.Последняя компиляция: 18 мая 2006 г.Обновления документа — на сайтах http://dmvn.mexmat.net,http://dmvn.mexmat.ru.Об опечатках и неточностях пишите на dmvn@mccme.ru.3Старый вариант программы экзаменаЛогика высказываний1. Пропозициональные формулы. Аксиомы и правила вывода классического исчисления высказываний (CL) и интуиционистского исчисления высказываний (IL).2.
Доказательства (выводы) в исчислениях CL и IL. Теоремы (выводимые формулы). Доказательство формулы A→A.3. Вывод из множества формул (теории) Γ (в CL и IL). Теорема дедукции.4. Оценка пропозициональных переменных. Значение формулы при оценке. Тавтологии.5. Теорема корректности для CL.6. Непротиворечивые и полные пропозициональные теории.
Свойства полных теорий.7. Лемма Линденбаума. Выводимость формулы ¬¬A→A. Теорема полноты для CL.8. Выполнимые теории. Сильная теорема корректности и сильная теорема полноты для CL. Теорема компактностидля CL.9. Шкала Крипке. Модель Крипке. Истинность формулы в точке («мире») модели Крипке. Принцип сохранности.10. Теорема корректности для IL относительно моделей Крипке. Недоказуемость закона исключенного третьего (p∨¬p)в IL.Логика предикатов11. Сигнатура. Термы и формулы данной сигнатуры. Свободные и связанные вхождения переменной в формулу. Параметры формулы.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
