курс лекций по логике и теории алгоритмов

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА Механико-математический факультет Курс лекций по логике и теории алгоритмов Лектор — Валентин Борисович Шехтман IV курс, 8 семестр, поток математиков Москва, 2006 г. Оглавление 1. 2. 3. Логика высказываний 1.1. Высказывания, формулы и правила вывода . . . . . . . . . . . . . . . . . . . . . 1.1.1. Высказывания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2. Формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.3. Аксиомы логики высказываний . . . . . . . . . . . . . . . . . . . . . . . . 1.1.4. Правило вывода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Корректность и полнота ИВ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1. Теорема корректности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2. Отступление об интуиционистской логике . . . . . . . . . . . . . . . . . . 1.2.3. Выводимость формулы. Подготовка к доказательству теоремы полноты 1.2.4. Путь к теореме полноты . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.5. Семантическая полнота и непротиворечивость теорий . . . . . . . . . . . 1.2.6. Доказательство теоремы полноты CL . . . . . . . . . . . . . . . . . . . . 1.3. Интуиционистская логика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Логика предикатов 2.1. Построение языка первого порядка . . . . . . . . . . . . . . . . . . . . . 2.1.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2. Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3. Интерпретация сигнатуры. Модель. Оценки . . . . . . . . . . . 2.1.4. Правила логики предикатов . . . . . . . . . . . . . . . . . . . . . 2.1.5. Теорема корректности исчисления предикатов . . . . . . . . . . 2.1.6. Теорема корректности и теорема непротиворечивости для теорий первого порядка . . . . . . . . . . . . . . . . . . . . . 2.1.7. Теории с равенством . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Теории Хенкина . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1. Экзистенциальная полнота . . . . . . . . . . . . . . . . . . . . . 2.2.2. Свойство Хенкина . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3. Вложение непротиворечивых теорий в полные теории Хенкина 2.3. Существование модели . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Случай теории без равенства . . . . . . . . . . . . . . . . . . . . 2.3.2. Случай теории с равенством . . . . . . . . . . . . . . . . . . . . . 2.4. Изоморфизм и элементарная эквивалентность интерпретаций . . . . . 2.4.1. Определения и основные свойства . . . . . . . . . . . . . . . . . 2.4.2. Сильная категоричность и счётная категоричность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 4 5 5 6 6 6 6 7 8 8 10 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 12 12 12 13 15 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .