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

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

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

МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП
Дисциплина входит в вариативную часть математического и естественно-научного цикла и требует освоения «Дискретной математики», «Программирования», «Информатики», используется далее при изучении «Экспертных систем», «Функционального и логического программирования», «Теории языков программирования и методов трансляции», «Системного анализа».

ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Процесс изучения дисциплины направлен на формирование следующих общекультурных (ОК), профессиональных (ПК) и профессионально-специализированных компетенций (ПСК):

  1. владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения (ОК-1);
  2. использует основные законы естественнонаучных дисциплин в профессиональной деятельности, применяет методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10).
В результате изучения дисциплины студент должен:
Знать: основные понятия математической логики: формальной теории, исчисления; структуру исчислений высказываний и предикатов 1-го порядка; основные понятия теории алгоритмов: интуитивная концепция алгоритма, уточнения понятия алгоритма (машины Тьюринга и нормальные алгоритмы Маркова), понятия вычислимости, разрешимости, перечислимости; основные неразрешимые массовые проблемы.
Уметь: доказывать формулы в исчислении высказываний и предикатов 1-го порядка; составлять программы машин Тьюринга и схемы нормальных алгоритмов для решения простых вычислительных задач.

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

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

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

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

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