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

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

贷款数: 5

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

• Алгебра и геометрия

*СomplexityDiscipline(zh-CN)*:

零件: Компонент по выбору

循环次数: Базовые дисциплины

Цель

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

Задача

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

Результат обучения: знание и понимание

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

Результат обучения: применение знаний и пониманий

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

Результат обучения: формирование суждений

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

Результат обучения: коммуникативные способности

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

Результат обучения: навыки обучения или способности к учебе

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

*TeachingMethods(zh-CN)*

Темы лекционных занятий

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

Основная литература

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

Дополнительная литература

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