Математическая логика и теория алгоритмов. Экзаменационные вопросы
-
Основной предмет математической логики: математические доказательства и математические вычисления. Логические значения и операции над ними. Операции над высказываниями. Кодирование слов в различных алфавитах двоичными словами. Кодирование пар и кодирование цепочек слов двоичными словами. Линейный порядок на двоичных словах.
-
Отношения, функции, как отношения. Действия, проверки. Исчисления. Породимые множества. Породимость объединения и пересечения породимых множеств.
-
Операции над функциями и их описаниями. Понятие ячейки. График. Композиция. Ветвление. Цикл.
-
Алгоритм. Вычислимые функции, перечислимые множества, разрешимые множества; Теоремы замкнутости.
-
Связь породимости и вычислимости.
-
Множество описаний алгоритмов. Универсальное действие. Универсальный алгоритм. Универсальная вычислимая функция. Универсальное породимое множество. Сложность объекта как длина самого короткого описания. Теорема Колмогорова об оптимальном способе описания.
-
Существование невычислимой функции. Диагональ несчетности (Кантора). Таблица универсальной вычислимой функции. Диагональ невычислимости. Алгоритмические проблемы. 10-я проблема Гильберта.
-
Грамматики. Выводимость в грамматике. «Тезис Поста». Алгоритмы Маркова («нормальные алгорифмы»). «Тезис Чёрча».
-
Логика высказываний. Логические константы, логические имена. Логические связки: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность. Скобки. Индуктивное определение (построение) формулы. Однозначность анализа формул.
-
Интерпретация логики высказываний, значение формулы логики высказываний при данной интерпретации. Булевы (двоичные) функции, таблица функции, функция, задаваемая формулой. Тавтологии. Алгоритм (тривиальный) проверки общезначимости. Подстановка формулы в формулу, синтаксис и семантика.
-
Построение формулы по функции. Теорема о совершенной дизъюнктивной нормальной форме. ДНФ.
-
Модальная логика. Шкалы Крипке, интерпретация. Исчисление модальной логики. Теорема о непротиворечивости (истинность формул, выводимых в исчислении Крипке).
-
Модальная логика. Противоречивое множество формул. Выводимость из множества формул. Замкнутое множество. Полное множество формул. Теорема о полноте (выводимость в исчислении Крипке любой истинной формулы).
-
Логики, определяемые классами шкал. Логика универсальной модальности S5. Логика "предсказуемого завтра" SL. Логика "неопределенного завтра" D.
-
Структуры, сигнатуры и интерпретации. Логика отношений, синтаксис. Алфавиты свободных и связанных переменных. Термы. Атомные формулы. Кванторы всеобщности и существования. Свободные и связанные имена (переменные). Индуктивное определение формулы заданной сигнатуры, анализ. Логика отношений, семантика. Предваренная нормальная форма (семантическое доказательство). Общезначимость. Выполнимость. Теория структуры.
-
Формулы, эквивалентные в заданной структуре. Определимость отношения в данной структуре. Замыкание класса отношений. Многообразие отношений. Пересечение и объединение многообразий отношений.
-
Арифметика натуральных чисел. Примеры определимости в ней: бета-функция Гёделя, экспонента. Утверждение об определимости вычислимых функция (без доказательства). Арифметическая иерархия.
-
Поле действительных чисел как структура. Алгебраические и полуалгебраические множества. Элиминация кванторов и алгоритм разрешения для теории действительных чисел, следствие для элементарной геометрии. (Теорема Тарского – Зайденберга.)
-
Теории и их модели. Соответствие Галуа между классами моделей и теориями. Семантика: следствие, противоречивость, полнота. Полнота и непротиворечивость теории.
-
Модель пары множеств (положительных и отрицательных формул), построение модели, лемма Кёнига. Теорема компактности Мальцева для счётного множества формул. Теорема о перечислимости множества общезначимых формул.
-
Исчисление отношений (предикатов), частные случаи тавтологий логики высказываний в логике отношений, аксиомы и правила вывода исчисления отношений, примеры выводов в исчислении отношений. Теорема о непротиворечивости (об истинности выводимых замкнутых формул). Теорема Геделя о полноте (об истинности формул, выводимых в исчислении отношений (без доказательства).
-
Теория равенства. Теория с равенством. Нормальная структура. Преобразование модели в нормальную. Гомоморфизмы, вложения, изоморфизмы, автоморфизмы структур.
-
Элементарная эквивалентность структур. Подструктура. Элементарная подструктура. Элементарное расширение. Критерий элементарности вложения одной структуры в другую. Критерий элементарности подструктуры.
-
Теорема Лёвенгейма – Сколема об элементарной подмодели. Категоричная теория. Признак Лося – Воота. Теорема Лёвенгейма – Сколема об элементарном расширении.
-
Линейные порядки, операции на них. Теория всех линейно упорядоченных множеств. Плотный неограниченный линейный порядок, полнота теории. Теория дискретного линейного порядка с наименьшим элементом без наибольшего. Пример полной теории, некатегоричной в счетной мощности. Примеры категоричных и некатегоричных теорий упорядоченных множеств. Полные аксиоматизации.
-
Нестандартные арифметики. Галактики. Нестандартные арифметики, как упорядоченные множества.
-
Соответствие Галуа между подгруппами группы всех биекций структуры и многообразиями отношений, метод Падоа доказательства неопределимости отношения. Теорема Свенониуса. Описание одноместных отношений, выразимых в порядке на натуральных числах. Классификация Семенова отношений, выразимых в порядке на рациональных числах.
-
Парадокс лжеца. Аксиоматика Пеано. Кодирование формул и их последовательностей. Модели с определимостью подстановки. Гёделева диагональ. Теорема Тарского о неопределимости арифметической истины.
-
Структуры с определимостью выводимости. Теорема Гёделя о неполноте. Истинные, но не доказуемые в Арифметике Пеано утверждения; червь Беклемишева.
-
Аксиоматическая теория множеств. Парадокс Рассела. Теория множеств Цермело - Френкеля ZF. Аксиома объемности. Аксиомы подмножеств. Аксиомы замены. Аксиома степени. Аксиома бесконечности. Аксиома регулярности (фундирования). Аксиома пустого множества. Аксиома пары.
-
Теория множеств Цермело – Френкеля ZF, неупорядоченная и упорядоченная пара множеств, упорядоченная тройка множеств, функция, область определения функции, область значений функции, инъективная функция, построение множества натуральных чисел, утверждение индукции для натуральных чисел, определение порядка, сложения, умножения для натуральных чисел в ZF.
-
Вполне упорядоченные множества. Ординалы. Свойства полного порядка. Предельные элементы вполне упорядоченного множества. Операции над упорядоченными классами (арифметика ординалов). Начальные отрезки вполне упорядоченного множества, кофинальность. Теорема о возрастающем отображении вполне упорядоченного класса. Теорема о вложении полных порядков. Порядок на упорядоченных классах. Трансфинитная индукция.
-
Функция выбора. Теорема Цермело. Аксиома выбора. Мощность множества. Равномощность. Возможность сравнения мощностей. Теорема Кантора – Бернштейна, Сравнение мощностей. Теорема Кантора о мощности степени. Континуум-гипотеза, Первая проблема Гильберта.
-
Без доказательства: утверждения о независимости Аксиомы выбора, Континуум-гипотезы и их отрицаний от ZF, Парадокс Банаха – Тарского, Игра Банаха – Мазура, Аксиома детерминированности игр, ее соотношение с ZF. Счётные модели теории множеств. Независимость аксиомы бесконечности от остальных аксиом ZF.
-
Идея нестандартного анализа. Аксиомы нестандартного анализа, Принцип переноса. Гипердействительные числа, стандартные числа, нестандартные числа, бесконечно большие и бесконечно малые числа, конечные гипердействительные числа, гипернатуральные числа, бесконечно близкие гипердействительные числа, стандартная часть гипердействительного числа. Неопределимость свойства гипердействительного числа "быть конечным натуральным числом". Нестандартные определения предела, предельной точки, фундаментальности стандартной последовательности.
-
Нестандартные доказательства: теоремы о существовании предельной точки у ограниченной последовательности, теоремы о сходимости фундаментальной последовательности. Нестандартное определение непрерывной функции, равномерно непрерывной функции. Расширения множеств в нестандартном анализе, ограниченные множества. Нестандартные доказательства ограниченности, равномерной непрерывности, промежуточных и максимальных значениях функций, непрерывных на отрезке.
-
Нестандартное определение производной функции. Нестандартное доказательство теоремы Ролля. Нестандартное определение интеграла. Конструктивное действительное число. Приблизительная формулировка теоремы Маркова.
-
Сложность вычислений. Существование универсальных переборных задач. Проблема перебора.
Достарыңызбен бөлісу: |
