Кафедра математической логики и теории алгоритмов

Введение в математическую логику 2005-2006 (Пентус)

Лектор: Мати Рейнович Пентус
2005/2006, весенний семестр


Программа экзамена

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

Алфавит, буква, слово в алфавите. Высказывания и высказывательные формы. Логические операции. Формулы логики высказываний. Соглашения о скобках. Подформулы в логике высказываний. Истинностное значение формулы при данной оценке пропозициональных переменных. Таблица истинности формулы. Тавтологии, выполнимые формулы, тождественно ложные формулы, их взаимосвязь. Эквивалентность (равносильность) формул логики высказываний. Законы логики высказываний в форме равносильностей. Теорема о подстановке в логике высказываний. Теорема об эквивалентной замене в логике высказываний. Логическое следование в логике высказываний.

Приведение формул логики высказываний к нормальным формам (ДНФ, КНФ, СДНФ, СКНФ). Выражение одних логических операций через другие. Штрих Шеффера, стрелка Пирса. Полные системы булевых функций.

Логика предикатов

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

Общезначимые и выполнимые формулы языка первого порядка, их взаимосвязь. Примеры общезначимых формул. Равносильность формул языка первого порядка. Законы логики первого порядка в форме равносильностей. Теорема о подстановке в тавтологии (без доказательства). Теорема об эквивалентной замене в логике первого порядка. Переименование связанных переменных. Корректные подстановки. Теорема о корректной подстановке в общезначимую формулу (без доказательства), существенность условия корректности в этой теореме.

Предварённые формулы. Приведение формул к предварённой форме.

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

Модель множества замкнутых формул. Логическое следование в логике первого порядка. Теория первого порядка, её аксиомы и теоремы. Понятие совместной теории. Пример совместной теории, пример несовместной теории. Элементарная теория данной интерпретации. Понятие полной теории. Теории первого порядка с равенством. Примеры: теория полугрупп, теория групп, теория частично упорядоченных множеств, теория линейно упорядоченных множеств. Нормальные модели. Построение для каждого натурального k формулы, для которой произвольное множество тогда и только тогда является носителем какой-нибудь её нормальной модели, когда оно имеет мощность не более k (не менее k; ровно k).

Исчисление высказываний

Аксиомы и правила классического исчисления высказываний. Выводимые формулы. Вывод из гипотез. Вывод формулы A->A в классическом исчислении высказываний. Теорема о корректности классического исчисления высказываний. Теорема о дедукции для классического исчисления высказываний. Свойства выводимости из гипотез. Теорема о полноте классического исчисления высказываний.

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

Аксиомы и правила классического исчисления предикатов. Выводимые формулы. Вывод из замкнутых гипотез. Общезначимость аксиом классического исчисления предикатов. Теорема о корректности классического исчисления предикатов. Обобщённая теорема о корректности классического исчисления предикатов. Теорема о дедукции для классического исчисления предикатов.

Теорема Гёделя о полноте классического исчисления предикатов (без доказательства). Теорема компактности для логики предикатов. Локальная теорема Мальцева. Теорема о существовании нормальной модели совместной теории первого порядка. Неразличимость конечного и бесконечного.

Теория алгоритмов и арифметика

Основные понятия теории алгоритмов. Область возможных исходных данных и область возможных значений алгоритма. Пошаговый характер выполнения алгоритма. Возможные варианты развития процесса применения алгоритма к исходным данным. Область применимости алгоритма. Частичная функция, вычисляемая данным алгоритмом. Машины Тьюринга. Вычисление словарных и числовых функций на машинах Тьюринга. Тезис Чёрча. Теорема о вычислимости по Тьюрингу композиции функций.

Разрешимые множества. Свойства объединения, пересечения и дополнения разрешимых множеств. Сигнализирующее множество алгоритма. Полухарактеристическая функция. Полуразрешимые множества. Вычислимые последовательности. Перечислимые множества. Канторовская нумерующая функция для пар натуральных чисел. Нумерация кортежей фиксированной длины. Нумерация словарного пространства. Проекция множества. Пять эквивалентных определений перечислимого множества. Теорема Чёрча-Поста (критерий разрешимости). Свойства объединения и пересечения перечислимых множеств. Перечислимость области определения и области значений вычислимой функции. Теорема о графике вычислимой функции.

Кодирование программ посредством слов в алфавите программ. Лямбда-обозначения. Существование универсальной машины Тьюринга. Универсальные функции. Построение вычислимой универсальной функции для класса всех вычислимых k -местных числовых функций. Пример вычислимой функции, не имеющей тотального вычислимого продолжения. Существование неразрешимого перечислимого множества.

Главные универсальные функции. Главность вычислимой универсальной функции, построенной по нумерации машин Тьюринга. Задача распознавания свойств вычислимых функций по их программам. Теорема Райса.

Плотные линейно упорядоченные множества без первого и последнего элемента

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

Понятие разрешимой теории. Разрешимо аксиоматизируемые теории. Теорема о полной разрешимо аксиоматизируемой теории. Разрешимость теории плотных линейно упорядоченных множеств без первого и последнего элемента.


Список вспомогательной литературы для подготовки к экзамену

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

[2, 1.1-1.2]
[7, 2.1-2.3]
[10, 2.1-2.11, 3.1-3.2]
[5, II.1-II.2]

Логика предикатов

[10, 5.4-5.10]
[7, 2.1, 2.4-2.14, 3.1-3.3, 3.7]
[2, 3.1-3.6, 3.9, 4.1, 4.2, 4.6, 4.7, 5.1, 5.3]
[19, 16-20]
[5, II.4-II.5]

Исчисление высказываний

[2, 2.1-2.3]
[10, 4.1-4.2]

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

[10, 6.1-6.4]
[2, 4.2-4.7]
[7, 3.4-3.6, 4.1-4.6]

Теория алгоритмов

[8, 1-7]
[11, 1-14, 24-27]
[7, 5.1-5.9]
[3, 1.1-4.4, 9.1-9.3]
[5, III.1-III.3]

Плотные линейно упорядоченные множества без первого и последнего элемента

[2, 3.6]
[7, 5.6]

Литература

Рекомендуемая литература

  1. Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. — М.: МЦНМО, 1999. — 128 с. PDF
  2. Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления. — М.: МЦНМО, 2000. — 288 с. PDF
  3. Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. — 176 с. PDF
  4. Колмогоров А. Н., Драгалин А. Г. Математическая логика. — М.: УРСС, 2004. — 240 с.
  5. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. — 3-е изд. — М.: Физматлит, 1995. — 256 с.
  6. Мендельсон Э. Введение в математическую логику. — М.: Наука, 1971. — 320 с.
  7. Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. 2-е изд. — М.: Физматлит, 2002. — 128 с.

Конспекты из Интернета

  1. Крупский В. Н. Лекции по теории алгоритмов для первого курса мехмата (2004). — 20 с. — PDF.
  2. Крупский В. Н. Подборка задач по теории алгоритмов. — 7 с. — PDF.
  3. Плиско В. Е. Математическая логика: Курс лекций. — 86 с. — PDF.
  4. Плиско В. Е. Теория алгоритмов: Курс лекций. — 38 с. — PDF.
  5. Bilaniuk S. A Problem Course in Mathematical Logic. — 2003. — XII, 152 p.

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

  1. Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 1977. — 368 с.
  2. Архангельский А. В. Канторовская теория множеств. — М.: Изд-во МГУ, 1988. — 112 с.
  3. Булос Дж., Джеффри Р. Вычислимость и логика. — М.: Мир, 1994. — 396 с.
  4. Гиндикин С. Г. Алгебра логики в задачах. — М.: Наука, 1972. — 288 с. http://www.mccme.ru/free-books/djvu/algebra/gindikin.htm
  5. Гладкий А. В. Математическая логика. — М.: РГГУ, 1998. — 479 с.
  6. Ершов Ю. Л., Палютин Е. А. Математическая логика. — 2-е изд., испр. и доп. — М.: Наука. Гл. ред. физ.-мат. лит., 1987. — 336 с.
  7. Клини С. К. Математическая логика. — М.: Мир, 1973. — 480 с.
  8. Логический подход к искусственному интеллекту: От модальной логики к логике баз данных / Тейз А., Грибомон П., Юлен Г. и др. — М.: Мир, 1998. — 494 с.
  9. Столл Р. Множества, логика, аксиоматические теории. — М.: Просвещение, 1968. — 231 с.
  10. Фейс Р. Модальная логика. — М.: Наука, 1974. — 520 с.
  11. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. — М.: Наука, 1983. — 360 с.
  12. Чёрч А. Введение в математическую логику. — М.: ИЛ, 1960. — 484 с.
  13. Шёнфилд Дж. Математическая логика. — М.: Наука, 1975. — 528 с.