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

Лектор: профессор Е.А. Палютин

2-3 семестры

Введение

Проблема обоснования математики. Парадокс Рассела. Аксиоматический метод - один из основных объектов изучения в математической логике.

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

Формулы ИВ. Лемма о начале формулы ИВ. Свойства подформул в формулах ИВ. Единственность дерева построения формулы ИВ. Аксиомы и правила вывода ИВ. Доказательства и теоремы ИВ. Допустимые правила вывода. Теорема о подстановке. Основные эквивалентности ИВ. Теорема о замене. Дизъюнктивные и конъюнктивные нормальные формы, теоремы существования. Истинность формул и секвенций ИВ. Теорема о непротиворечивости ИВ. Теорема о функциональной полноте ИВ. Теоремы о существовании и единственности совершенных д.н.ф. и к.н.ф. Основная лемма о доказуемости в ИВ. Теорема о полноте ИВ. Исчисление высказываний гильбертовского типа (ИВ1). Вывод в ИВ1, теорема о дедукции. Теорема о равносильности ИВ и ИВ1. Теорема о полноте ИВ1.

Теория множеств

Система аксиом Цермело-Френкеля (ZFC). Упорядоченные пары и наборы, декартовы произведения множеств. Двухместные отношения, их основные типы. Эквивалентности и разбиения, их равносильность. Отображения, их типы, свойства композиции и обращения. Частично упорядоченные множества. Наибольшие (наименьшие) и максимальные (минимальные) элементы ч.у.м. Верхние грани и отрезки в линейно упорядоченных множествах. Принцип максимума. Вполне упорядоченные множества. Принцип полного упорядочения. Теорема об изоморфизме вполне упорядоченных множеств. Теорема о кардинальном упорядочении. Сравнение множеств по мощности, теорема Кантора-Бернштейна. Теорема Кантора. Конечные, счетные и несчетные множества. Теорема о мощности квадрата бесконечного множества и ее следствия. Ординалы и их свойства. Кардиналы.

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

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

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

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