Канатников А.Н. Дискретная математика. Конспект лекций

М.: МГТУ им. Н.Э.Баумана, 2006, 84 с.Лекции читаются на 6-ом семестре (3-й курс) в МГТУ имени Н.Э. Баумана студентам, обучающимся по специальности "Прикладная математика".СодержаниеБулевы функции.
Булевы алгебры. Булевы функции. ДНФ и КНФ. Критерий Поста. Минимизация ДНФ.Логика высказываний.
Алгебра высказываний. Тавтологии и эквивалентность формул. Способы получения эквивалентных формулИсчисление высказываний.
Введение. Основные положения теории N. Правила естественного вывода. Глобальные свойства теории NАлгебра предикатов.
Предикаты и кванторы. Логико-математические языки. Переменования и подстановки. Семантика логико-математического языка. Логические законы. Замены. Упрощение формулИсчисление предикатов.
Построение теории P. Правила естественного вывода. Глобальные свойства теории PАлгоритмы на графах.
Введение. Деревья. Остов графа наименьшего веса. Задача о путях в размеченном графе. Циклы, разрезы и задача Эйлера