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

О курсе

Технологии в информатике меняются очень быстро. Инженер-программист должен осваивать новые информационные технологии каждые 2-5 лет. Однако при этом концептуальные, базисные теоретические основы информационных технологий остаются неизменными.

Математическая логика относится к теоретическому фундаменту, на котором основаны все существующие и будущие информационные технологии. С помощью логики выражаются семантика языков программирования, спецификация программ (что программа делать), выполняется верификация программ (проверяется, делает ли программа в точности то, что от нее ожидают).

Курс состоит из трех частей. Первая часть посвящена базе математической логики – теории двоичных функций. Вторая часть излагает базовые разделы математической логики, наиболее часто применяемые в практике информационных технологий: методы формализации умозаключений, алгоритмы формального логического вывода, аксиоматические теории. Заключительная часть посвящена методам верификации распределенных алгоритмов и систем.

Результат

В результате изучения дисциплины студент должен:

знать понятия, определения, термины, методы, алгоритмы, способы решения задач логики высказываний; логики предикатов и соответствующих исчислений.
уметь оценить сложность алгоритмов, выделить легко и трудноразрешимые задачи, оценить классы задач P и NP.
овладеть базовыми методами и алгоритмами проверки логического следования, проверки корректности программ, способами определения сложности вычислений и организации эффективных алгоритмов.

Формируемые компетенции

ОПК-1 способность использовать базовые знания естественных наук, математики и информатики, основные факты, концепции, принципы теорий, связанных с фундаментальной информатикой и информационными технологиями

ПК-2 способность понимать, совершенствовать и применять современный математический аппарат, фундаментальные концепции и системные методологии, международные и профессиональные стандарты в области информационных технологий

ПК-6 способность эффективно применять базовые математические знания и информационные технологии при решении проектно-технических и прикладных задач, связанных с развитием и использованием информационных технологий

О преподавателях

Карпов Юрий ГлебовичПрофессор СПбПУ

Шошмина Ирина ВладимировнаСтарший преподаватель

Входные требования

Достаточно знания математики в объеме средней школы. В первом разделе излагается материал из курса "Дискретная математика", в объеме необходимом для уверенного использования его в "Математической логике". Студенты, знакомые с дискретной математикой, могут

пропустить этот раздел, сдав контрольные работы.

Содержание курса

Модуль 1. Введение в теорию двоичных функций

Тема 1. Булевы функции
Тема 2. Нормальные формы представления булевых функций
Тема 3. Теорема Поста
Тема 4. Применение булевых функций
Тема 5. Бинарные решающие диаграммы
Тема 6. Конечные автоматы и их применение

Модуль 2. Логика высказываний

Тема 7. Основные понятия логики высказываний
Тема 8. Логический вывод в логике высказываний

Модуль 3. Логика предикатов

Тема 9. Основные понятия логики предикатов
Тема 10. Логический вывод в логике предикатов

Модуль 4. Аксиоматические теории. Исчисление высказываний

Тема 11. Основные компоненты аксиоматических теорий
Тема 12. Теорема Геделя о полноте

Модуль 5. Дедуктивная верификация программ

Тема 13. Программа как преобразователь предикатов
Тема 14. Индуктивный метод Флойда

Модуль 6. Проверка корректности реагирующих программ

Тема 15. Темпоральные логики LTL, CTL
Тема 16. Алгоритм проверки выполнимости для CTL

Профессии, специальности и направления подготовки	27.00.00 Управление в технических системах 09.00.00 Информатика и вычислительная техника 11.00.00 Электроника, радиотехника и системы связи 02.00.00 Компьютерные и информационные науки
Область деятельности	Инженерное дело, технологии и технические науки Математические и естественные науки
Дата окончания записи	03.10.2023
Трудоёмкость в з.е.	3.0
Количество лекций	13
Дата ближайшего старта	04.09.2023
Дата окончания	22.01.2024
ID курса	47d896a1c579467f9fcb021654ac15b5
К-во обучающихся на версии курса	18969
Язык	Русский
Длительность	16 недель
Сертификат	Есть
Версия	7