Математическая логика и теория алгоритмов
Содержание
назад
|
вперед
Введение
Логические исчисления
Логика высказываний
Понятие формальной теории
Исчисление высказываний (ИВ)
Теорема дедукции
Непротиворечивость и полнота ИВ
Методы проверки выводимости формул ИВ
Контрольные вопросы
Понятие предиката
Логические эквивалентности с кванторами
Термы и формулы в исчислении предикатов (ИП)
Аксиомы и правила вывода в ИП
Теоремы об ИП первого порядка
Контрольные вопросы
Элементы теории алгоритмов и рекурсивных функций
Понятие алгоритма
Машина Тьюринга (МТ)
Вычисление функций на МТ
Алгоритмически неразрешимые задачи
Примитивно рекурсивные функции
Частично рекурсивные функции
Характеристики сложности алгоритмов
Классы сложности P и NP
Контрольные вопросы
Литература
Предметный указатель
назад
|
вперед