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

ТРУДОЕМКОСТЬ ДИСЦИПЛИНЫ
Общая трудоемкость дисциплины составляет 5 ЗЕТ (180 часов).

ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ
Целью дисциплины является освоение студентами теоретических основ формальных систем и приобретения практических навыков при формализации реальных систем и построении формальных непротиворечивых теорий.

СОДЕРЖАНИЕ ДИСЦИПЛИНЫ. ОСНОВНЫЕ РАЗДЕЛЫ
Логика высказываний (пропозициональная логика). Высказывания и истинностные значения высказываний. Логические операции. Формулы логики высказываний (пропозициональные формулы). Истинностные функции. Тавтологии. Эквивалентность формул. Замена эквивалентным и двойственность. Дизъюнктивная и конъюнктивная нормальные формы. Классическое исчисление высказываний. Аксиомы и правила вывода. Вывод формул и вывод формул из гипотез. Теорема о дедукции. Теоремы полноты и непротиворечивости. Исчисление предикатов. Предикаты и кванторы. Предикатные формулы. Интерпретация предикатных формул. Выполнимость, истинность. Логическая общезначимость. Аксиомы и правила вывода исчисления предикатов 1-го порядка. Структура теории 1-го порядка. Нормальные алгоритмы и машины Тьюринга. Вычисление словарных функций нормальными алгоритмам и машинами Тьюринга. Принцип нормализации и тезис Тьюринга. Универсальные алгоритмы. Теоремы сочетания. Разрешимость и перечислимость. Неразрешимые массовые проблемы.

ВИДЫ УЧЕБНОЙ РАБОТЫ
Лекции, практические занятия.

ФОРМА АТТЕСТАЦИИ ПО ДИСЦИПЛИНЕ
Изучение дисциплины заканчивается экзаменом.

Методические материалы:

1. Сафьянова Е. Н. Математическая логика и теория алгоритмов: методические указания по самостоятельной и индивидуальной работе студентов / Томск: ТУСУР, 2013. – 7 с.