Содержание

В.А. Пинаев, Я.В. Славолюбова

ДИСКРЕТНАЯ МАТЕМАТИКА:

ТЕОРИЯ МНОЖЕСТВ, КОМБИНАТОРИКА

Учебное пособие

Кемерово 2012

УДК 519.1

ББК 22.17

П32

Рецензенты:

Н.А. Петрик,канд. техн. наук, доцент, зав. кафедрой высшей

и прикладной математики Кемеровского института (филиала) РГТЭУ;

Е.В. Прокопенко, канд. физ.-мат. наук, доцент кафедры прикладных информационных технологий Кузбасского государственного

технического университета им. Т.Ф. Горбачёва

П32 Пинаев, В.А. Дискретная математика: теория множеств, ком-бинаторика [Текст] : учебное пособие / В.А. Пинаев, Я.В. Сла-волюбова ; Кемеровский институт (филиал) РГТЭУ. − Кемерово : Кемеровский институт (филиал) РГТЭУ, 2012. – 68 с.

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

Предназначено для студентов по направлениям 230700 «Прикладная информатика в экономике», 080500 «Бизнес-информатика».

УДК 519.1

ББК 22.17

© Кемеровский институт (филиал) РГТЭУ, 2012

Содержание

Введение……………………………………………………….…...…5

1 Теория множеств…………………………………………………7

1.1 Основные понятия и определения теории множеств…………..7

1.2 Два принципа интуитивной теории множеств…………………8

1.3 Сравнение множеств………………………………………....…11

1.4 О парадоксах теории множеств……………………………...…13

1.5 Основные операции над множествами……………………...…15

1.6 Диаграммы Эйлера-Венна……………………………………...19

1.7 Свойства операций над множествами…………………………19

1.8 Отношения на множествах. Бинарные отношения…….……..22

1.8.1 Упорядоченные пары и прямое произведение множеств..22

1.8.2 Бинарные отношения…………………………………...…..23

1.9 Примеры решения задач………………………………………..26

1.10 Задачи для самостоятельного решения………………………36

2 Комбинаторика……………………………………………….....41

2.1 Задача о коммивояжере……………………………………...…41

2.2 Принципы подсчета………………………………………….….43

2.2.1 Принцип умножения…………………………………….…….43

2.2.2 Принцип сложения…………………………………………….44

2.2.3 Принцип разбиения множеств………………………….…….45

2.3 Комбинаторные формулы………………………………...…….48

2.3.1 Перестановки, размещения, сочетания, размещения с повторениями………………………………………………………..48

2.3.2 Перестановки и сочетания с повторениями…………………51

2.3.3 Формула включений и исключений……………………….…53

2.4 Примеры решения задач…………………………………..…….55

2.5 Задачи для самостоятельного решения……………………...…63

Контрольные вопросы…………...……………………………….....66

Список литературы…………………………………………….……67