Mathematical logic and discrete mathematics

Description: Основные понятия аксиоматической теории множеств. Исчисление высказываний. Теорема о полноте, другие аксиоматизации. Узкое исчисление предикатов, кванторы. Модели, выполнимость, общезначимость. Теорема о существовании моделей. Теорема компактности Мальцева. Введение в теорию графов. Основные оптимизационные алгоритмы на графах.

Amount of credits: 5

Пререквизиты:

• Algebra and Geometry

Course Workload:

Component: Component by selection

Cycle: Base disciplines

Goal

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

Objective

• 1. приобретения практических навыков в решении задач аксиоматического метода построения математической теории, метода математической индукции, минимизации булевых функции.

Learning outcome: knowledge and understanding

• 1. иметь представление о современном состоянии и проблемах математики, прикладной математики и информатики, истории и методологии их развития.

Learning outcome: applying knowledge and understanding

• 1. способность к самостоятельному видению главных смысловых аспектов в научно-технической и естественно-научной проблеме, умение ставить задачу и строить корректную математическую модель

Learning outcome: formation of judgments

• 1. умение извлекать актуальную научно-техническую информацию из электронных библиотек, специализированных сайтов и форумов в Интернете, реферативных журналов и т.п. Формулировать устно и письменно свою точку зрения, принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность. .

Learning outcome: communicative abilities

• 1. способность демонстрировать в речевом общении личную и профессиональную культуру, духовно-нравственные убеждения

Learning outcome: learning skills or learning abilities

• 1. способность самостоятельно изучать новые научные публикации по математическому моделированию и смежным разделам математики, осваивать современные методы математического моделирования и применять их в своей практической деятельности.

Teaching methods

Topics of lectures

• Парадоксы канторовской теории множеств
• Основные логические связки
• Построение формальных теорий
• Исчисление высказываний гильбертовского типа
• Другие аксиоматизации исчисления высказываний
• Предикаты и кванторы
• Модели, выполнимость и общезначимость
• Теорема о существовании модели
• Применения матлогики в математике и информатике
• Определения, начальные понятия теории графов
• Простые (обыкновенные) графы
• Изоморфные графы
• Метрические характеристики графов
• Обходы
• Некоторые оптимизационные алгоритмы на графах: Дейкстры, Прима, Краскала

Key reading

• В.А. Емеличев и др. Лекции по теории графов.– М.: Наука. 2012.
• С.Г. Горбатов Фундаментальные основы дискретной математики.– М.: Наука, 2000
• И.А. Лавров, Л.Л. Максимова. Задачи по теории множеств, математической логике и теории алгоритмов. - М: Наука, 2012г.
• И.В. Латкин. Дискретная математика с элементами математической логики. Усть-Каменогорск: ВКГТУ, 2016
• И.В. Латкин Конспект лекций по дискретной математике. – Усть-Каменогорск: ВКГТУ, 2010.
• Н. Кристофидес Теория графов. Алгоритмический подход. – М.: Мир, 1978
• С.Д. Шапорев Математическая логика.- Спб, 2015г.
• Н.Г. Хисамиев, А.Н. Хисамиев. Элементы математической логики. - ВКГТУ, Усть-Каменогорск, 2012г.

Further reading

• М.О. Асанов, В.А. Баранский, В.В. Расин Дискретная математика: графы, матроиды, алгоритмы. – Москва, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2011.
• Ф.А. Новиков Дискретная математика для программистов.–СПб: Питер, 2011.
• С.В. Яблонский Введение в дискретную математику.– М., Наука, 2009.
• И.В. Латкин Дискретная математика. – Методические указания и задания по выполнению контрольных работ заочной формы обучения. Усть-Каменогорск, ВКТУ, 2003
• Г.П. Гаврилов, А.А. Сапоженко Задачи и упражнения по курсу дискретной математики.– М.: Наука, 1992