Тема 1. «Совершенные дизъюнктивные нормальные формы (СДНФ) и совершенные конъюнктивные нормальные формы (СКНФ) в алгебре высказываний (АВ)». Формулы АВ. Эквивалентность формул АВ. Понятия дизъюнктивной нормальной формы (ДНФ), конъюнктивной нормальной формы (КНФ), СДНФ, СКНФ.
Тема 2. «Логическое следствие в алгебре высказываний». Понятия логического следствия. Связь между понятиями логического следствия, противоречивого множества формул, тождественно ложной формулы и тождественно истинной формулы.
Тема 3. «Исчисление высказываний (ИВ). Доказуемые формулы ИВ». Понятие исчисления. Язык ИВ. Определение формулы ИВ. Аксиомы и правила вывода ИВ. Доказуемые и выводимые формулы ИВ. Примеры доказуемых и выводимых формул ИВ.Теорема о дедукции в ИВ. Эквивалентные формулы ИВ.
Тема 4. «Логика предикатов (ЛП). Алгебраические системы. Подсистемы».Понятия сигнатуры, алгебраической системы данной сигнатуры, подсистемы, подсистемы, порожденной множеством. Примеры. Понятия терма данной сигнатуры, значение терма на кортеже в алгебраической системе. Теорема о подсистеме, порожденной множеством.
Тема 5. «Формулы ЛП».Понятие формулы данной сигнатуры. Определение истинности формулы ЛП на кортеже элементов в алгебраической системе. Примеры.
Тема 6. «Истинность формулы ЛП в алгебраической системе».
Тема 7. «Логическое следствие в ЛП. Эквивалентные формулы ЛП». Понятия логического следствия, противоречивого множества формул ЛП, тождественно истинной формулы ЛП. Связь между этими понятиями. Определение эквивалентных формул ЛП. Основные эквивалентности в ЛП.
Тема 8. «Исчисление предикатов (ИП). Доказуемые формулы ИП». Язык ИП. Определение формулы ИП. Аксиомы и правила вывода ИП. Доказуемые и выводимые формулы ИП. Примеры доказуемых и выводимых формул ИП. Тавтологии. Связь между тавтологией и доказуемой формулой. Эквивалентные формулы ИП.
Тема 9. «Пренексная нормальная форма для формул ИП». Понятия ДНФ и ПНФ для формул ИП. Теорема о существовании для любой формулы ИП эквивалентной ей ПНФ.
Тема 10. «Машины Тьюринга». Определение машины Тьюринга. Понятие функций, вычислимых по Тьюрингу. Примеры таких функций.
Тема 11. «Примитивно рекурсивные функции».Понятия базисных функций, операторов суперпозиции, примитивной рекурсии, примитивно рекурсивных функций. Примеры.
Тема 12. «Частично рекурсивные функции». Понятия оператора минимизации, частично рекурсивных функций. Примеры. Эквивалентность классов функций, вычислимых по Тьюрингу, с классом частично рекурсивных функций.