- •Содержание
- •1. Множества 10
- •2. Математическая логика 39
- •3. Теория графов 96
- •Тема 1. Множества 168
- •Тема 2. Математическая логика 169
- •Тема 3. Теория графов 171
- •Тема 1.
- •Множества
- •1.1. Операции над множествами. Мощность множеств. Отображение множеств
- •Упражнение 1.1.1
- •Упражнение 1.1.2
- •1.2. Отношения на множествах
- •Будет ли пустое множество V каким-либо подмножеством некоторого множества?
- •Тема 2.
- •Математическая логика
- •2.1. Алгебра высказываний
- •Логические операции
- •Функции алгебры высказываний
- •2.2. Проблемы разрешимости. Нормальные формы Логические отношения
- •2. Отношение эквивалентности.
- •3. Несовместимость.
- •Проверка правильности рассуждений
- •Нормальные формы формул алгебры высказываний
- •Совершенные нормальные формы
- •Построение формулы алгебры высказываний по заданной логической функции
- •Моделирование алгебры высказываний с помощью релейно-контактных схем
- •2.3. Исчисление высказываний Символы, формулы, аксиомы исчисления высказываний. Правила вывода
- •Теорема дедукции
- •Проблемы непротиворечивости, полноты, независимости аксиом исчисления высказываний
- •2.4. Логика предикатов
- •Кванторы
- •Кванторы как обобщение логических связок.
- •Отрицание кванторных предикатов
- •Тема 3.
- •Теория графов
- •3.1. Графы
- •Степень вершины графа. Число ребер графа
- •Связность
- •Эйлеровы и гамильтоновы цепи и циклы. Теоремы Эйлера
- •Изоморфизм графов
- •Планарность. Плоские графы
- •Числа, характеризующие граф
- •Операции над графами. Объединение графов
- •Пересечение (произведение) графов
- •Прямое произведение графов
- •Матрицы для графов
- •Матрица инциденций
- •Матрицы достижимостей и контрадостижимостей
- •3.2. Деревья
- •Постановка задачи
- •Алгоритм Краскала
- •3.3. Экстремальные задачи на графах Задача о кротчайшем пути между двумя вершинами ориентированного графа и ее экономическая интерпретация
- •Алгоритм
- •Сети. Отношение порядка между вершинами ориентированного графа
- •Задача о пути максимальной длины между двумя вершинами ориентированного графа в сетевом планировании
- •Алгоритм
- •Сетевое планирование. Скорейшее время завершения проекта
- •Контрольное задание №1
- •Контрольное задание №2
- •Контрольное задание №3
- •Контрольное задание №4
- •Контрольное задание №5
- •Контрольное задание №6
- •Контрольное задание №7
- •Контрольное задание №8
- •Контрольное задание №9
- •Контрольное задание №10
- •Контрольное задание №11
- •Контрольное задание №12.
- •Контрольное задание №13.
- •Контрольное задание №14.
- •Контрольное задание №15
- •Список рекомендуемой литературы
- •Интернет-ресурсы
- •Тема 2. Математическая логика
- •Тема 3. Теория графов
Международный консорциум «Электронный университет»
Московский государственный университет экономики,
статистики и информатики
Евразийский открытый институт
Э.Л. Балюкевич
Л.Ф. Ковалева
А.Н. Романников
Дискретная математика
Учебно-практическое пособие
Москва 2009
УДК – 519.1
ББК – 22.176
К – 56
Балюкевич Э.Л., Ковалева Л.Ф., Романников А.Н. ДИСКРЕТНАЯ МАТЕМАТИКА: Учебно-практическое пособие – М.: Изд. центр ЕАОИ, 2009. – 173 с.
ISBN 5–7764–0252–2 © Балюкевич Э.Л., 2009
© Ковалева Л.Ф., 2009
© Романников А.Н. 2009
© Оформление. АНО «Евразийский открытый институт», 2009
Содержание
Сведения об авторах 5
Цели и задачи дисциплины и её место в учебном процессе 7
Введение 9
1. Множества 10
1.1. Операции над множествами. Мощность множеств. Отображение множеств 10
1.2. Отношения на множествах 27
Тест 33
2. Математическая логика 39
2.1. Алгебра высказываний 39
2.2. Проблемы разрешимости. Нормальные формы 56
2.3. Исчисление высказываний 73
2.4. Логика предикатов 80
Тест 85
3. Теория графов 96
3.1. Графы 96
3.2. Деревья 121
3.3. Экстремальные задачи на графах. 128
Вопросы для самопроверки. 140
Контрольные задания 142
Контрольное задание №1 142
Контрольное задание №2 142
Контрольное задание №3 145
Контрольное задание №4 145
Контрольное задание №5 146
Контрольное задание №6 147
Контрольное задание №7 150
Контрольное задание №8 151
Контрольное задание №9 152
Контрольное задание №10 152
Контрольное задание №11 152
Контрольное задание №12. 155
Контрольное задание №13. 156
Контрольное задание №14. 159
Контрольное задание №15 162
Список рекомендуемой литературы 167
Руководство по изучению дисциплины 168
Тема 1. Множества 168
Тема 2. Математическая логика 169
Тема 3. Теория графов 171
Сведения об авторах
Балюкевич Эдуард Людвигович, к.э.н., с.н.с., профессор кафедры прикладной математики МГУЭСИ.
Перечень работ по данной дисциплине, изданных автором:
-
Балюкевич Э.Л. (в соавторстве) Дискретный анализ : учебное пособие. – М. : МЭСИ, 1980. 5,5 п/л.
-
Балюкевич Э.Л. Математические методы в проектировании АСУ. – М. : МЭСИ, 1984, 3 п/л.
-
Балюкевич Э.Л. (в соавторстве) Сборник задач по курсу «Дискретный анализ» : учебное пособие. – М. : МЭСИ, 1987, 4,1 п/л.
-
Балюкевич Э.Л. (в соавторстве) Методические указания к выполнению курсовой работы по курсу «Дискретный анализ». – М. : МЭСИ, 1991, 1 п/л.
-
Балюкевич Э.Л. (в соавторстве) Дискретная математика : учебное пособие. – М. : МГУЭСИ, 2003. 16 п/л.
-
Балюкевич Э.Л. Учебно-практическое пособие. – М. : МГУЭСИ, 2009, 10 п/л (электронная версия).
Ковалева Лидия Федоровна к.т.н., доцент.
Перечень работ по данной дисциплине, изданных автором:
-
Ковалева, Л.Ф. Дискретная математика. – ч. I. – М. : МЭСИ, 2000 (электронное).
-
Ковалева, Л.Ф. (в соавторстве). Дискретная математика. – М. : МЭСИ, 1988.
-
Ковалева, Л.Ф. Применение дискретной математики в экономических задачах. – М. : МЭСИ, 1979.
-
Ковалева, Л.Ф. (в соавторстве). Применение теории графов в экономических задачах. – М. : МЭСИ, 1977.
-
Ковалева, Л.Ф. Математическая логика и теория графов. – ч. I, II. – М. : МЭСИ, 1976, 1977.
-
Ковалева, Л.Ф. (в соавторстве) Дискретный анализ. – М. : МЭСИ, 1980.
-
Ковалева, Л.Ф. Методические указания и контрольные работы по курсу «Дискретная математика» (специальность – «информатика», заочная форма обучения). – М. : МЭСИ, 1998.
-
Ковалева, Л.Ф Методические указания по изучению курса «Дискретная математика» с упражнениями. Задачник. – М. : МЭСИ, 1986.
-
Ковалева, Л.Ф. (в соавторстве). Методические указания и контрольные задания по курсу «Дискретный анализ» для студентов заочного обучения, специальность – экономическая кибернетика. – М. : МЭСИ, 1992.
-
Ковалева, Л.Ф. (в соавторстве). Методические указания по изучению курса «Дискретная математика» (с упражнениями), специальность прикладная математика, АСУ. – М. : МЭСИ, 1986.
-
Ковалева, Л.Ф. (в соавторстве). Методические указания по изучению курса «Дискретный анализ» для студентов заочной формы обучения, специальность - механизированная обработка экономической информации. – М. : МЭСИ, 1987.
-
Ковалева, Л.Ф. (в соавторстве). Методические указания к выполнению курсовой работы.
а) по курсу «Дискретный анализ» для студентов специальности – экономическая кибернетика и АСУ (0715). – М. : МЭСИ, 1991, 1989.
б) по курсу «Дискретная математика» для студентов специальности – прикладная математика (0102). – М. : МЭСИ, 1989.
Цели и задачи дисциплины и её место в учебном процессе
«Дискретная математика» является математической основой курсов, изучающих современные прикладные экономико-математические методы.
Целью изучения данной дисциплины является прочное усвоение студентами теоретических основ дискретной математики, составляющих фундамент ряда математических дисциплин и дисциплин прикладного характера. Содержание курса «Дискретной математики» используется в курсах: «Теория систем и системный анализ», «Информатика и программирование», «Теория вероятностей и математическая статистика», «Исследование операций и методы оптимизации», «Математическое и имитационное моделирование», «Управление проектом».
Задачей дисциплины является формирование у обучающихся следующих компетенций:
-
способности при решении профессиональных задач анализировать социально-экономические проблемы и технико-экономические процессы с применением методов системного анализа и математического моделирования;
-
способности применять методы анализа прикладной области на концептуальном, математическом, логическом и алгоритмическом уровнях;
-
способности применять системный подход и математические методы в формализации решения прикладных задач.
В результате изучения дисциплины студент должен:
Знать:
-
принципы использования языка, средств, методов и моделей дискретной математики в дисциплинах, которым её изучение должно предшествовать, а также в проблемах прикладного характера.
Уметь:
-
использовать методы дискретной математики, при изучении дисциплин математического, естественнонаучного и профессионального циклов.
Владеть:
-
всем арсеналом методов дискретной математики, который необходим для формирования профессиональных компетенций.
Форма активных методов обучения:
использование учебно-методических комплексов и информационно-компьютерных образовательных технологий, включающих оценочные средства для текущего контроля успеваемости и промежуточной аттестации, разработанных в Московском Государственном Университете Экономики, Статистики и Информатики.
Список дисциплин, знание которых необходимо для изучения дискретной математики:
-
Курс школьной математики.
Введение
Данное пособие рассчитано на читателя, впервые знакомящегося с курсом дискретной математики.
В пособии изложены основные понятия теории множеств и алгебры высказываний, простейшего основного раздела математической логики, сведения из теории графов, рассмотрены задачи по определению экстремальных путей на графе, что позволяет решить такие задачи экономического содержания, как построение самого дешевого нефтепровода, определение скорейшего времени завершения проекта и др.
Данное пособие не претендует на исчерпывающую полноту и абсолютную строгость изложенного материала.