Л. А. Телешева, Н. Н. Шадрина
Теория множеств
Комбинаторика
Учебно-методическое пособие
Улан-Удэ • 2021
Стр.1
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
БУРЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИМЕНИ ДОРЖИ БАНЗАРОВА
Л. А. Телешева, Н. Н. Шадрина
Теория множеств. Комбинаторика
Рекомендовано УМС БГУ
дляв качестве учебно-методического пособия
09.03.02обучающихся по направлениям подготовки
Информационные системы и технологии
09.03.03 Прикладная информатика
Издательство Бурятского госуниверситета
2021
Улан-Удэ
Стр.2
УДК 510.6
ББК 22.126, 22.181
Т 48
Утверждено к печати
редакционно-издательским советом Бурятского госуниверситета,
протокол №2 от 10.03.2021 г.
Текст в авторской редакции
Рецензенты:
кандидат физико-математических наук, доцент кафедры ПМиДУ ИМИ БГУ
им. Доржи Банзарова И. Б. Юмов
кандидат педагогических наук, доцент кафедры информатики и ИТЭ БГСХА
им. В. Р. Филиппова Т. Ж. Базаржапова
Телешева Л. А.
Т48 Теория множеств. Комбинаторика: учебно-методическое пособие / Л. А. Телешева,
Н. Н. Шадрина — Улан-Удэ.: Изд-во Бурятского госуниверситета, 2021.—57 с.
ISBN 978-5-9793-1590-4
В учебно-методическом пособии изложены основные вопросы дискретной математики.
Рассмотрены темы: Теория множеств, Комбинаторика. В тексте содержатся примеры и задачи
по каждой теме, даны иллюстрации. Пособие предназначено для обучающихся по направлениям
подготовки 09.03.02 Информационные системы и технологии, 09.03.03 Прикладная
информатика.
ББКУДК 510.6
22.126, 22.181
-c Л. А. Телешева, Н. Н. Шадрина 2021
-c Бурятский государственный университет
имени Доржи Банзарова, 2021
ISBN 978-5-9793-1590-4
Стр.3
Оглавление
Предисловие
1 Элементы теории множеств
6
8
1.1 Основные определения теории множеств . . . . . . . 8
1.1.1 Понятие множества . . . . . . . . . . . . . . . . . . 8
1.1.2 Способы задания множества . . . . . . . . . . . . . 10
1.1.3 Подмножества . . . . . . . . . . . . . . . . . . . . . 11
1.1.4 Операции над множествами . . . . . . . . . . . . . . 13
1.1.5 Задания к главе 1.1. . . . . . . . . . . . . . . . . . . 16
1.2 Отношения . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2.1 Основные понятия отношений . . . . . . . . . . . . 19
1.2.2 Свойства отношений . . . . . . . . . . . . . . . . . . 24
1.2.3 Эквивалентность отношений . . . . . . . . . . . . . 30
1.2.4 Основные понятия отображений . . . . . . . . . . . 32
1.3 Задания к главе 1.2. . . . . . . . . . . . . . . . . . . . . . . 35
2 Комбинаторика
37
2.1 Перестановки, сочетания и размещения без повторений
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.1 Перестановки без повторений . . . . . . . . . . . . . 37
2.1.2 Сочетания без повторений . . . . . . . . . . . . . . . 38
2.1.3 Размещения без повторений . . . . . . . . . . . . . . 39
2.1.4 Задания к главе 2.1. . . . . . . . . . . . . . . . . . . 40
2.2 Перестановки, сочетания и размещения с повторениями
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.2.1 Перестановки с повторениями . . . . . . . . . . . . . 46
2.2.2 Сочетания с повторениями . . . . . . . . . . . . . . 47
4
Стр.4
2.2.3 Размещения с повторениями . . . . . . . . . . . . . 49
2.2.4 Задания к главе 2.2. . . . . . . . . . . . . . . . . . . 50
2.3 Правило сложения и правило умножения комбинаций 50
2.3.1 Правило сложения комбинаций . . . . . . . . . . . . 50
2.3.2 Правило умножения комбинаций . . . . . . . . . . . 51
2.4 Бином Ньютона . . . . . . . . . . . . . . . . . . . . . . . 52
2.4.1 Формула бинома Ньютона . . . . . . . . . . . . . . . 52
2.4.2 Свойства биномиальных коэффициентов . . . . . . 52
2.4.3 Треугольник Паскаля . . . . . . . . . . . . . . . . . 53
2.4.4 Задания к главе 2.3. . . . . . . . . . . . . . . . . . 53
Методические указания
Библиографический список
55
56
5
Стр.5
Предисловие
Настоящее учебное издание представляет собой учебно-методическое
пособие для дисциплины «Дискретная математика» в рамках реализации
образовательных программы высшего образования по направлению
подготовки 09.03.03 Прикладная информатика, 09.03.02 Информационные
системы и технологии очной формы обучения и подготовлено в соответствии
с требованиями Федерального государственного образовательного
стандарта высшего образования.
Дисциплина «Дискретная математика» относится к обязательным дисциплинам
базовой части. Изучение дисциплины направлено на формирование
общепрофессиональных компетенций: ОПК-2 Способен использовать
современные информационные технологии и программные средства,
в том числе отечественного производства, при решении задач профессиональной
деятельности.
В результате освоения дисциплины обучающийся должен:
- знать методы теории множеств, математической логики, алгебры высказываний,
теории автоматов, теории алгоритмов.
- уметь использовать методы дискретной математики при изучении дисциплин
математического и естественно - научного и профессионального
цикла.
- владеть навыками моделирования прикладных задач, методами дискретной
математики.
Основной задачей настоящего учебно-методического пособия является
обобщение материала в рамках дисциплины «Дискретная математика».
Пособие состоит из двух разделов курса дискретной математики: (I)
элементы теории множеств; (II) комбинаторика. Это первая часть курса.
Во второй части планируется рассмотреть темы: (III) алгебра логики; (IV)
теория графов.
6
Стр.6
В разделе "Элементы теории множеств" рассмотрены следующие темы:
основные определения теории множеств, понятие множества, способы
задания множества, подмножества,операции над множествами, диаграммы
Эйлера-Венна; объединение, пересечение, разность и симметрическая
разность множеств; отображения, соответствия, отношения.
В разделе "Комбинаторика" представлены темы: перестановки, сочетания
и размещения без повторений; перестановки, сочетания и размещения
с повторениями; правило сложения и правило умножения комбинаций,
формула бинома Ньютона, свойства биномиальных коэффициентов, треугольник
Паскаля, формулы включений и исключений, полиномиальные
формы.
Каждый раздел разбит на главы, которые, в свою очередь, разбиты на
параграфы. Каждый параграф представляет собой отдельную тему, логически
связанную с последующими и(или) предыдущими. В параграфах
приводится теоретический материал, необходимый для понимания данной
темы, рассматриваются соответствующие примеры. В конце каждой
главы расположены наборы заданий по вариантам для самостоятельного
выполнения.
7
Стр.7