Материал: 5540
Министерство образования и науки Российской Федерации Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«Хабаровская государственная академия экономики и права»
Кафедра математики и математических методов в экономике
ДИСКРЕТНАЯ МАТЕМАТИКА
Учебное пособие
Хабаровск 2009
Министерство образования и науки Российской Федерации Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«Хабаровская государственная академия экономики и права»
Кафедра математики и математических методов в экономике
ДИСКРЕТНАЯ МАТЕМАТИКА
Учебное пособие
Хабаровск 2009
2
ББК В И 25
Ивлева А. И. Дискретная математика : учеб. пособие / А. И. Ивлева. – Хабаровск : РИЦ ХГАЭП, 2009. – 120 с.
Рецензенты : д-р физ.-мат. наук, проф. Намм Р.В., канд. физ.-мат. наук, доцент Диреев Ю. В.
В учебном пособии изложены основные понятия теории множеств,
отношений и отображений, элементы теории графов и математической
логики. Основные положения каждого раздела иллюстрируются
примерами, в каждом разделе приведены задачи для самостоятельного
решения.
Содержание учебного пособия отвечает требованиям рабочей программы дисциплины «Дискретная математика» для студентов
специальности 061800 «Математические методы в экономике»
Утверждено издательским библиотечным советом академии в качестве
учебного пособия для студентов
© Хабаровская государственная академия экономики и права, 2009
3
Содержание
Введение ………………………………………………………………………. 4
Глава 1. Элементы теории множеств………………………………………….4
1.1Основные понятия теории множеств. Операции над множествами. Основные тождества алгебры множеств ………………...…..5
1.2Бинарные отношения. Свойства бинарных отношений ………...14
1.3Эквивалентность и порядок. Операции над бинарными отношениями ……………………..………………………..………………….18
1.4Соответствия ……………………..………………………..……….23
1.5Функции и отображения……………………..…………..………...26 Глава 2. Булева алгебра ………………………………………………………28
2.1Операции логики Буля……………..……………………………... 29
2.2Формы представления булевых функций……………..………….35
2.3Методы доказательств в логике Буля……………..………………38
Глава 3. Логика высказываний……………..……………………………..…42
3.1Классическая логика….…………..……………………………..…42
3.2Высказывания….…………..…………………………………….…46
3.3Формулы алгебры высказываний….…………..……………….…52
3.4Эквивалентные преобразования….…………..………………...…57
3.5Основные логические законы….…………….………....…………62
3.6.Необходимое и достаточное условие импликации ….………….65
3.7Нормальные формы формул логики высказываний….………….69
3.8Логическое следствие….………………………………………….72
Глава 4. Логика предикатов….……………...……………………………….77
4.1Основные понятия….…………….……………………..………….77
4.2Кванторы….…………….……………………..…………...……….82
4.3Формулы логики предикатов. Выполнимость и истинность….…88
4.4Эквивалентные соотношения. Префиксная нормальная форма…93
Глава 5. Теория графов…………………………………………………….…97
5.1Основные понятия теории графов. Способы задания графов…..97
5.2Операции над частями графа. Графы и бинарные отношения...103
5.3Маршруты, пути, цепи, циклы. Дерево и лес…………………...105
Библиографический список ....……………………………………………...118
4
ВВЕДЕНИЕ
При исследовании, анализе и решении многих реальных экономических и управленческих ситуаций широко используются дискретные методы формализованного представления, являющиеся предметом рассмотрения в дискретной математике. К ним относятся методы, основанные на теоретико-множественных представлениях, графы, алгоритмы, формальные системы, математическая логика и др. Несмотря на разнообразие подобных методов, общим в них является дискретность описания объектов анализа. Методы дискретной математики пригодны для описания и последующего конструктивного анализа многих проблемных ситуаций, в том числе не поддающихся описанию традиционными средствами классической математики, и позволяют при необходимости активно использовать современную вычислительную технику, новые информационные технологии.
Дискретная математика предлагает:
универсальные средства (языки) формализованного представления;
способы корректной переработки информации, представленной на этих языках;
возможности и условия перехода с одного языка описания явлений на другой с сохранением содержательной ценности моделей. Задачей курса является освоение будущими экономистами основных
моделей и методов формализованного представления: теоретико-
множественных, логических, графических. Теория множеств, логика,
теория графов являются фундаментом дискретной математики.
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
В обычной речи мы часто употребляем слово «множество»: множество людей, множество книг, множество законов и т.д. Теория множеств создана в последней четверти XIX века чешским математиком С. Больцано, немецким ученым Г. Кантором и др. Данная теория была признана связующим звеном между логикой и математикой.
5