Дискретная математика в примерах и задачах
Покупка
Основная коллекция
Тематика:
Дискретная математика
Издательство:
Сибирский федеральный университет
Год издания: 2018
Кол-во страниц: 132
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-7638-3967-8
Артикул: 765665.01.99
Изложен краткий теоретический материал по разделам дискретной математики: множества, отношения, комбинаторика, математическая логика, графы. Приведены примеры и задачи с решениями. Даны задачи и упражнения для самостоятельной работы. Предназначено студентам укрупненных групп направлений подготовки 11.00.00 «Электроника, радиотехника и системы связи», 12.00.00 «Фотоника, приборостроение, оптические и биотехнические системы и технологии», направлений 27.03.05 «Инноватика», 09.03.03 «Прикладная информатика», 38.03.05 «Бизнес-информатика» и специальности 25.05.03 «Техническая эксплуатация транспортного радиооборудования».
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.03: Прикладная информатика
- 12.03.03: Фотоника и оптоинформатика
- 27.03.05: Инноватика
- ВО - Специалитет
- 25.05.03: Техническая эксплуатация транспортного радиооборудования
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Министерство науки и высшего образования Российской Федерации Сибирский федеральный университет Т. В. Моисеенкова ДИСКРЕТНАЯ МАТЕМАТИКА В ПРИМЕРАХ И ЗАДАЧАХ Учебное пособие Красноярск СФУ
УДК 519.1(07) ББК 22.174я73 М748 Р е ц е н з е н т ы: Я. Н. Нужин, доктор физико-математических наук, профессор Сибирского федерального университета; И. В. Шевелева, кандидат физико-математических наук, доцент Сибирского федерального университета Моисеенкова, Т. В. М748 Дискретная математика в примерах и задачах : учеб. пособие / Т. В. Моисеенкова. – Красноярск : Сиб. федер. ун-т, 2018. – 132 с. ISBN 978-5-7638-3967-8 Изложен краткий теоретический материал по разделам дискретной математики: множества, отношения, комбинаторика, математическая логика, графы. Приведены примеры и задачи с решениями. Даны задачи и упражнения для самостоятельной работы. Предназначено студентам укрупненных групп направлений подготовки 11.00.00 «Электроника, радиотехника и системы связи», 12.00.00 «Фотоника, приборостроение, оптические и биотехнические системы и технологии», направлений 27.03.05 «Инноватика», 09.03.03 «Прикладная информатика», 38.03.05 «Бизнес-информатика» и специальности 25.05.03 «Техническая эксплуатация транспортного радиооборудования». Электронный вариант издания см.: УДК 519.1(07) http://catalog.sfu-kras.ru ББК 22.174я73 ISBN 978-5-7638-3967-8 © Сибирский федеральный университет, 2018
ВВЕДЕНИЕ В настоящее время дискретная математика является интенсивно развивающимся разделом математики. Повсеместное распространение кибернетических систем, языком описания которых она является, привело к тому, что в последнее время дискретная математика сформировалась как учебный курс, вошедший в учебные планы многих инженернотехнических, экономических и других специальностей. Кроме того, дискретная математика является теоретической базой информатики, которая уже очень глубоко проникла не только в науку и технику, но и в повседневную жизнь. Современный бакалавр и специалист не может обойтись без использования компьютерной техники. Это не только специальные текстовые и иные редакторы, системы документационного обеспечения, но и более сложные системы поддержки принятия решений, экспертные и другие интеллектуальные системы. Необходимость владения методами дискретной математики обусловлена ещё и тем, что современная техника переработки информации базируется на дискретных представлениях. Дискретная математика предлагает универсальные средства формализованного представления, способы корректной переработки информации, а также возможности и условия перехода с одного языка описания явлений на другой с сохранением содержательной ценности моделей. Методы дискретной математики пригодны для описания и последующего конструктивного анализа многих проблемных ситуаций, в том числе не поддающихся описанию традиционными средствами классической математики, и позволяют при необходимости активно использовать современную вычислительную технику, новые информационные технологии. Цель данного пособия – дать необходимый теоретический материал, который предусмотрен программами данной дисциплины и рассмотреть различные задачи для его более быстрого и прочного усвоения и применения на практике. Пособие содержит четыре главы: «Элементы теории множеств и отношения», «Элементы комбинаторики», «Элементы математической логики», «Элементы теории графов». Все они входят в состав семестрового курса дискретной математики. В начале каждой главы кратко и в доступной для студента первого курса форме дается теоретический материал с сопровождающими примерами. Приведены задачи с решениями, рассмотрены не только базовые алгоритмы, используемые при решении стандартных задач, но и нестандартные задачи, позволяющие глубже усвоить материал главы.
Для закрепления полученных знаний и формирования навыков самостоятельного решения задач в конце каждого параграфа приведены задачи для самостоятельной работы, которые охватывают все темы и понятия данного параграфа, позволяют отработать все основные методы и алгоритмы. Количество и разнообразие приведенных задач различной сложности позволяет применять их не только на аудиторных практических занятиях, но и организовать самостоятельную работу студентов различной интенсивности. В основу данного учебного пособия положен курс лекций и практических занятий по дисциплине «Дискретная математика», который автор многие годы читает для студентов различных укрупненных групп и направлений подготовки, указанных в аннотации. Надеюсь, что пособие будет полезно не только студентам на практических аудиторных занятиях, но и всем, кто изучает основы дискретной математики.
В пособии будем использовать следующие обозначения: N – множество натуральных чисел; Z – множество целых чисел; Q – множество рациональных чисел; R – множество действительных чисел; C – множество комплексных чисел; P+ – множество всех положительных чисел из множества P; P+ 0 – множество всех неотрицательных чисел из множества P; [x] – наибольшее целое число, не превосходящее x∈R; ⇒– если . . . , то . . . ; ⇔– . . . , тогда и только тогда . . . ; C =(cij)m×n – матрица C размерности m×n, состоящая из элементов cij; i=1, 2, . . . , m; j =1, 2, . . . , n.
1. Элементы теории множеств
1.1. Множества. Операции над множествами
Через ∈обзначается отношение принадлежности, т. е. x∈A означает, что элемент x принадлежит множеству A. Если x не является элементом множества A, то это записывается x /∈A.
Интуитивный принцип объемности. Множества A и B считаются равными, если они состоят из одних и тех же элементов.
Записывают A=B, если A и B равны, и A̸=B в противном случае.
Свойство, которым обладают элементы множества A и только они,
называется характеристическим свойством множества A.
Под «формой от x» будем понимать конечную последовательность, состоящую из слов и символа x такую, что если каждое вхождение
x в эту последовательность заменить одним и тем же именем некоторого
предмета соответствующего рода, то в результате получится истинное
или ложное предложение. Обозначим форму от x через P(x).
Пример 1.1.1. «x2=4», «x – сосед Петрова» – формы от x, а выражение
«существует такой x, что x2−2x=4» не является формой от x.
Интуитивный принцип абстракции. Любая форма P(x) определяет некоторое множество A, а именно множество тех и только
тех предметов a, для которых P(a) — истинное предложение.
Множество A, определяемое формой P(x), обозначается
A={x|P(x)}.
Множество, элементами которго являются обьекты a1, ..., an и только
они, обозначают {a1, ..., an}.
Пример 1.1.2.
Множество A={1, 2, 3} можно следующим образом
представить формой P(x):
A={x|x — целое положительное число, меньшее 4},
A={x|x∈Z, 0<x<4},
A={x|x3−6x2+11x−6=0}.
Если каждый элемент множества A является одновременно элементом множества B, то B называют подмножеством множества A и
пишут A⊆B.
Если A⊆B, но A̸=B, то B называют
собственным подмножеством множества A и пишут A⊂B.
Множество, не содержащее элементов, называется пустым множеством и обозначается ∅. Все рассматриваемые множества являются подмножествами некоторого множества U — универсального множества.
Множество всех подмножеств множества A называется булеан или
множество степень множества A и обозначается B(A).
Пример 1.1.3. Если A={1, 2, 3}, то
B(A)={∅, {1}, {2}, {3}{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
Заметим, что пустое множество является подмножеством любого множества, т. е. ∅⊆A, и что 1̸={1}, так как 1∈A, а {1}⊆A.
Операции на множествах
Для произвольных множеств A, B определяются операции:
Объединение множеств A и B:
A∪B ={x|x∈A или x∈B}.
Пересечение множеств A и B:
A∩B ={x|x∈A и x∈B}.
Разность множеств A и B:
A\B ={x|x∈A и x /∈B}.
Дополнение множества A:
A={x|x /∈A}.
Симметрическая разность множеств A и B:
A△B =(A\B)∪(B\A).
Для наглядности представления отношений между подмножествами какого-либо универсального множества используются диаграммы Эйлера – Венна. Универсальное множество U изображают в виде прямоугольника, а его подмножества в виде кругов, расположенных внутри
прямоугольника. На рис. 1 представлены диаграммы Эйлера — Венна,
иллюстрирующие операции над множествами.
A\B
A∆B
A
A
A∪B
A∩B
A
B
U
A
B
U
A
U
A
U
A
B
U
A
B
U
Рис. 1
Пример 1.1.4. Дано:
a) A={1, 3, 4, 5, 9}, B ={2, 4, 5, 10}, U=Z;
б) A={x|x∈Z, −3<x<4 }, B ={x|x∈Z, |x−3|<2};
в) A={x|x∈R, −3<x<4 }, B ={x|x∈R, |x−3|<2}.
Найти A∪B, A∩B, A\B, B\A, A△B, B\A.
Решение. a) по определению операций на множествах получим
A∪B ={1, 2, 3, 4, 5, 9, 10}, A∩B ={4, 5}, A\B ={1, 3, 9},
B\A={2, 10}, A△B ={1, 2, 3, 9, 10}, B\A={4, 5}.
б) зададим множества перечислением элементов:
U=Z, A={−2, −1, 0, 1, 2, 3} B ={2, 3, 4}. Тогда
A∪B ={−2, −1, 0, 1, 2, 3, 4}, A∩B ={2, 3}, A\B ={−2, −1, 0, 1},
B\A={4}, A△B ={−2, −1, 0, 1, 4}, B\A={2, 3}.
в) A∪B ={x|x∈R, −3<x<5}, A∩B ={x|x∈R, 1<x<4},
A\B ={x|x∈R, −3<x<1}, B\A={x|x∈R, 4<x<5},
A△B ={x|x∈R, x∈(−3, 1)∪(4, 5)}, B\A={x|x∈R, 1<x<4}.
Свойства операций на множествах
Для любых подмножеств A, B, C универсального множества U
выполняются следующие тождества:
Коммутативность:
1. A∪B =B ∪A;
1∗. A∩B =B ∩A.
Ассоциативность:
2. A∪(B ∪C)=(A∪B)∪C;
2∗. A∩(B ∩C)=(A∩B)∩C.
Дистрибутивность:
3. A∪(B ∩C)=(A∪B)∩(A∪C);
3∗. A∩(B ∪C)=(A∩B)∪(A∩C).
Действия с константами:
4. A∪∅=A, A∪U=U;
4∗. A∩∅=∅, A∩U=A.
5. A∪A=U;
5∗. A∩A=∅.
Идемпотентность:
6. A∪A=A;
6∗. A∩A=A.
Законы де Моргана:
7. A∪B =A∩B;
7∗. A∩B =A∪B.
Законы поглощения:
8. A∪(A∩B)=A;
8∗. A∩(A∪B)=A.
Закон двойного дополнения:
9. A=A.
Для доказательства тождества A=B достаточно показать включения A⊆B и B ⊆A, используя определения операций над множествами.
Пример 1.1.5. Доказать тождество A∩B =A∪B (закон де Моргана).
Решение. Докажем, что A∩B ⊆A∪B.
Пусть x∈A∩B =⇒x /∈A∩B =⇒x /∈A или x /∈B =⇒x∈A или
x∈B =⇒x∈A∪B.
Докажем, что A∩B ⊆A∪B.
Пусть x∈A∪B =⇒x∈A или x∈B =⇒x /∈A или x /∈B =⇒
x /∈A∩B =⇒x∈A∩B.
Из A∩B ⊆A∪B и A∩B ⊆A∪B =⇒A∩B =A∪B.
Декартово произведение множеств
Декартовым (прямым) произведением множеств A и B называется множество
A×B ={(a, b)|a∈A, b∈B}.
Декартово произведение A×A=A2 называется декартовым квадратом множества A.
Пример 1.1.6. Пусть A={1, 2, 3}, B ={a, b}. Тогда
A×B ={(1, a); (1, b); (2, a); (2, b); (3, a); (3, b)}.
B ×A={(a, 1); (a, 2)(a, 3); (b, 1); (b, 2); (b, 3)}.
Пример 1.1.6 показывает, что A×B ̸=B ×A при A̸=B.
Декартовым (прямым) произведением множеств A1, A2, ..., An
называется множество
A1×A2×...×An={(a1, a2, ..., an)|ai∈Ai; i=1, 2, ..., n}.
Если A1=A2=...=An, то декартово произведение
A×A×...×A=An
называется n-й декартовой степенью множества A.
Конечные множества
Множество A называется конечным, если оно содержит конечное
число элементов. Это число называется
мощностью
множества A и
обозначается через |A|.
Для конечных множеств A и B справедливы следующие формулы:
|A∪B|=|A|+|B|−|A∩B|;
(1)
|A∪B ∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B ∩C|+|A∩B ∩C|; (2)
|B(A)|=2|A|;
(3)
|A×B|=|A|·|B|.
(4)
Пусть A1, A2, ..., An — конечные множества, тогда
|A1×A2×...×An|=|A1|·|A2|·...·|An|.
(5)
Пример 1.1.7. Пусть |A|=n, |B|=m, n≥m. Выразить через n и m
мощности следующих множеств: max |A∪B|, min |A∪B|, max |A∩B|,
min |A∩B|, max |A\B|, min |A\B|.
Решение. Покажем на диаграммах Эйлера — Венна (рис. 2), в каких случаях объединение, пересечение и разность множеств будут принимать максимальное и минимальное значения соответственно.
Получаем
max |A∪B|=n+m, min |A∪B|=n, max |A∩B|=m,
min |A∩B|=0, max |A\B|=n, min |A\B|=n−m.