МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

1.

Ершов Ю.Л., Палютин Е.А.. Математическая логика. М., Наука, 1987.

2.

Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.,Наука,1984.

3.

Мальцев А.И. Алгоритмы и рекурсивные функции. М.,Наука.

4.

Кожухов И.Б. Математическая логика и теория алгоритмов. РИО МИЭТ.

5.

Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Ч.2. Языки и исчисления. М.; 2000; Ч.3. Вычислимые функции. М; 1999.

№

Содержание

Лекция 1

Предмет математической логики. Структура формул. Секвенции, правила вывода, доказательства. Исчисление высказываний генценовского типа.

Л-4, §1.1; Л-1.

Лекция 2

Эквивалентность формул. Приведение формулы к нормальному виду. Функциональная полнота исчисления высказываний.

Л-4, § 1.2,1.3; Л-1.

Лекция 3

Интерпретации. Теорема о полноте классического исчисления высказываний. Разрешимость исчисления высказываний.

Л-4, § 1.3; Л-1

Лекция 4

Исчисление высказываний гильбертовского типа. Вывод и квазивывод. Лемма о дедукции. Правило разбора случаев. Зависимость аксиом ИВ.

Л-4, § 1.4; Л-1, Л-5.

Лекция 5

Интуиционизм и конструктивизм. Аксиомы интуиционистской логики. Невыводимость закона исключенного третьего.

Л-4, § 1.5, Л-5

Лекция 6

Аксиоматические теории. Аксиоматика Пеано натуральных чисел. Аксиоматика действительных чисел.

Л-4, § 3.1.

Лекция 7

Множества. Отображения множеств. Эквивалентные множества. Теорема Шредера-Бернштейна. Счетные множества.

Л-4, § 2.1.