ПРОГРАММА ЭКЗАМЕНА. Часть 2


  1. ЛОГИКА ВЫСКАЗЫВАНИЙ

    1. Формулы логики высказываний. Представление булевых функций формулами. (3.1.)
    2. Формулировка исчисления высказываний. Доказательство и доказательство в виде дерева. Теорема об эквивалентности этих понятий. (3.2.)
    3. Теорема об истинности доказуемых секвенций. (Теорема 3.5.)
    4. Эквивалентность формул. Булевы эквивалентности. (3.3.)
    5. Лемма о замене. (3.3)
    6. Эд и эк. Кнф и днф. Теоремы осуществовании кнф и днф для каждой формулы. (3.3.)
    7. Критерий доказуемости кнф. Критерий доказуемости эд.
    8. Теорема о доказуемости истинных секвенций. (3.3)

  2. ЛОГИКА ПРЕДИКАТОВ

    1. Алгебраические системы и базы данных. Сигнатура и схема базы данных. Примеры. Термы и формулы. Их значения на состоянии.
    2. Подсистемы. Теорема о подсистеме, порождённой подмножеством. (Базы данных. Теоремы 1.6 и 1.7. Определение 1.2.3.)
    3. Гомоморфизмы и их специальные случаи. Теорема о сохранении значений термов при гомоморфизмах и формул при изоморфизмах.
    4. Игры Эренфойхта. Критерий неразличимости двух систем формулой. (Базы данных. Определение 1.1.4 и теорема 1.1.)
    5. Неопределимость связности в логике предикатов. (Базы данных. Теорема 1.9.)
    6. Теорема о представимости рекурсивных функций в арифметике.
    7. Результат подстановки. Теоремы о независимости значения формулы от значений переменных, не входящих в неё свободно, о равенстве значений формул, получаемых из формулы подстановкой равных термов вместо переменной. (3.5.)
    8. Теорема о замене.
    9. Теорема о приведении к предварённой форме.
    10. Теорема о неразрешимости логики предикатов.
    11. Теорема о неразрешимости логики предикатов для конечных моделей.

  3. СЛОЖНОСТЬ

    1. Многоленточные машины Тьюринга со входом и выходом. Распознаватели. Сигнализирующие функции. (6.1.) Связь между временной и ёмкостной сигнализирующими. (Теорема 6.1.)
    2. Теорема о построении эквивалентной машины Тьюринга с одной входной и одной рабочей лентами.
    3. Теорема о возможности использования только двух букв на рабочих лентах.
    4. Полиномиальная сводимость. Теорема о замкнутости классов сложности относительно полиномиальной сводимости. (6.3.)
    5. NP-полные проблемы. Теорема о совпадении P и NP. (6.3.)
    6. Принадлежность SAT к NP.
    7. NP-полнота SAT.
    8. Машины Тьюринга со стеком.
    9. Первая теорема Кука.
    10. Вторая теорема Кука.