Математическая логика и теория алгоритмов

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ.
Понятие множества. Объединение, пересечение, теоретико-множественна разность множеств. Прямое (или декартово) произведение множеств.
Бинарные отношения и их свойства (рефлексивность, симметричность, иррефлексивность, антисимметричность, транзитивность).
Понятия функции и взаимно однозначной функции. Равномощные множества. Теорема о равномощности множеств как об отношении эквивалентности.
Понятие счетного множества. Примеры счетных множеств. Теорема о счетности подмножества счетного множества.
Теорема о счетности счетного объединения счетных множеств. Счетность множества слов в конечном или счетном алфавите. Теорема о множестве значений функции, определенной на счетном множестве.
Теорема об эквивалентности всех бесконечных счетных множеств. Канторовский диагональный метод.
Кардинальные числа (мощность множества). Теорема Кантора-Бернштейна. Теорема Кантора о мощности множества всех подмножеств.
Парадоксы теории множеств. Аксиоматическая теория множеств (система аксиом Цермело-Френкеля).
Понятие высказывания и переменной. Свободные и связанные переменные. Высказывательная форма и ее параметры. Логические операции (связки). Таблица истинности. Пропозициональные операции.
Пропозициональные переменные. Пропозициональные формулы и индуктивное правило их построения. Понятие тавтологии и логического закона.
Кванторы. Правила определения истинности выражений, содержащих кванторы.
Понятия субъекта и предиката. Предикат как функция.
Логико-математические языки первого порядка. Сигнатура языка первого порядка. Термы и формулы языка первого порядка и индуктивные правила их построения. Замкнутые формулы. Подстановки. Понятие терма, свободного для переменной в формуле. Примеры языков первого порядка.
Интерпретация сигнатуры языка первого порядка. Примеры интерпретаций.
Формальное определение истинности. Оцененные формулы и оцененные термы. Индуктивный способ построения оцененного терма. Индуктивный способ определения истинности формулы в интерпретации.
Общезначимые и выполнимые формулы. Примеры. Теорема об общезначимости тавтологии.
Равносильность формул. Теоремы о равносильностях формул при различных условиях. Теорема о равносильности произвольной формулы формуле, не содержащей связок конъюнкции, импликации и эквивалентности.
Предваренные формулы. Теорема о равносильности произвольной формулы некоторой предваренной формуле.
Булевы функции. Задание булевой функции ее таблицей истинности. Отрицание, дизъюнкция, конъюнкция, импликация, эквивалентность. Операции над булевыми функциями.
Дизъюнктивная и конъюнктивная нормальные формы булевых функций. Лемма о дизъюнктивной нормальной форме булевой функции.
Булево сложение и его свойства. Булева степень булевой переменной. Многочлены Жегалкина. Теорема о представимости единственным образом булевой функции в виде многочлена Жегалкина.
Замкнутые классы булевых функций: функции, сохраняющие ноль, функции, сохраняющие единицу, линейные функции, самодвойственные функции, монотонные функции.
Полные классы булевых функций. Теорема Поста о полном классе булевых функций и ее следствие.
Контактные схемы. Реле с замыкающим и размыкающим контактами. (r,s)- полюсники. Примеры контактных схем. Параллельное и последовательное соединение контактных схем.
Связь контактных схем и булевых функций: функция проводимости схемы. Функция проводимости между полюсами.
П-схемы. Функция проводимости П-схемы. Теорема о существовании П-схемы, функцией проводимости которой является заданная булева функция. Теорема о форме функции проводимости П-схемы. Построение минимальной П-схемы.
Понятие алгоритма. Ансамбли конструктивных объектов и их свойства. Область применимости алгоритма. Частична функция. Функция, вычисляемая алгоритмом (вычислимая функция). Примеры вычислимых функций. Теорема о существовании невычислимой функции.
Разрешимые множества. Примеры разрешимых множеств. Теорема о разрешимости объединения, пересечения и дополнения разрешимых множеств. Существование неразрешимого множества.
Полуразрешимые множества и их свойства. Примеры полуразрешимых множеств. Теорема о полуразрешимости разрешимого множества.
Свойство вычислимой равномощности ансамблей и теорема о «нумерации» элементов ансамбля вычислимой функцией.
Теорема о вычислимости обратной функции.
Проекция множества. Теорема о полуразрешимости проекции разрешимого множества.
Вычислимые последовательности. Теорема о полуразрешимости множества значений вычислимой последовательности.
Перечислимые множества. Теорема о равносильности свойства полуразрешимости множества, перечислимости множества и некоторых других его свойств.
Теорема о перечислимости объединения и пересечения перечислимых множеств и проекции перечислимого множества.
Теорема Поста об эквивалентности разрешимости множества и перечислимости множества и его дополнения.
Теорема о графике вычислимой функции.
Универсальная вычислимая функция. Теоремы об универсальной вычислимой функции.
Продолжение частичной функции. Теорема о существовании вычислимой частичной функции, не имеющей всюду определенного вычислимого продолжения. Теорема о существовании перечислимого неразрешимого множества.
Машина Тьюринга. Работа машины Тьюринга на заданном входе. Примеры работы машины Тьюринга.
Вычислимые по Тьюрингу (в сильном и в слабом смысле) функции. Примеры вычислимых по Тьюрингу функций.
Теорема о существовании для вычислимой в сильном смысле функции машины Тьюринга, вычисляющей функцию в сильном смысле и зацикливающейся там, где функция не определена.
Теорема об эквивалентности вычислимости по Тьюрингу в сильном смысле и в слабом смысле.
Универсальна вычислимая по Тьюрингу функция. Теорема о вычислимости по Тьюрингу композиции вычислимых по Тьюрингу функций (без доказательства). Теорема об универсальной вычислимой по Тьюрингу функции (без доказательства).
Теорема о неразрешимости проблемы остановки машины Тьюринга.
Тезис Чёрча.
15

Приложенные файлы

  • doc 8958354
    Размер файла: 33 kB Загрузок: 0

Добавить комментарий