Лекции читаются на 6-ом семестре (3-й курс) в МГТУ имени Н.Э. Баумана студентам, обучающимся по специальности "Прикладная математика".

Содержание

Булевы функции.
Булевы алгебры. Булевы функции. ДНФ и КНФ. Критерий Поста. Минимизация ДНФ.

Логика высказываний.
Алгебра высказываний. Тавтологии и эквивалентность формул. Способы получения эквивалентных формул

Исчисление высказываний.
Введение. Основные положения теории N. Правила естественного вывода. Глобальные свойства теории N

Алгебра предикатов.
Предикаты и кванторы. Логико-математические языки. Переменования и подстановки. Семантика логико-математического языка. Логические законы. Замены. Упрощение формул

Исчисление предикатов.
Построение теории P. Правила естественного вывода. Глобальные свойства теории P

Алгоритмы на графах.
Введение. Деревья. Остов графа наименьшего веса. Задача о путях в размеченном графе. Циклы, разрезы и задача Эйлера