Математическая логика. Алехина М.А. - 6 стр.

7        Лекции
    1.   Логические исчисления. Модели.
         (a) Исчисление высказываний. Аксиомы. Правила вывода.
         (b) Тождественная истинность выводимых формул.
         (c) Непротиворечивость исчисления высказываний.
         (d) Предикаты. Логический операции над предикатами и их теоретико-
             множественный смысл.
         (e) Кванторы. Геометрический смысл квантора существования.
         (f) Модели. Формулы. Свободные и связанные переменные.
         (g) Истинность формул в модели, на множестве. Общезначимые
             формулы.
         (h) Эквивалентные     формулы      логики    предикатов.    Правила
             преобразования формул в эквивалентные. Нормальная форма.
         (i) Исчисление предикатов. Аксиомы. Правила вывода.
         (j) Тождественная истинность выводимых формул.
         (k) Непротиворечивость исчисления предикатов.
         (l) Формулировка теоремы о полноте исчисления предикатов.
    2.   Вычислимые функции.
         (a) Машины Тьюринга.
         (b) Вычислимые функции.
         (c) Тезис Чёрча.
         (d) Примеры вычислимых функций.
         (e) Рекурсивные, рекурсивно перечислимые          множества   и   их
             алгоритмическая характеристика.
         (f) Теорема Поста.
         (g) Примеры алгоритмически неразрешимых проблем.
         (h) Неразрешимость проблем самоприменимости, применимости.
         (i) Теорема Поста – Маркова о существовании ассоциативного
             исчисления с алгоритмически неразрешимой проблемой равенства.
    3.   Рекурсивные функции.
         (a) Операции суперпозиции и примитивной рекурсии. Примитивно-
             рекурсивные функции.
                                          6