Дискретная математика в пакете MATLAB
Покупка
Тематика:
Дискретная математика
Издательство:
ФЛИНТА
Год издания: 2020
Кол-во страниц: 533
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-9765-4431-4
Артикул: 774958.01.99
Доступ онлайн
450 ₽
В корзину
В учебном пособии изложены некоторые классические разделы дискретной математики на базе широко известного пакета прикладных программ MATLAB. Материалы учебного пособия разделены на две части, олносимые к лекциям и семинарам соответственно. Лекционная часть не предполагает использование пакета MATLAB и представляет собой набор из семи разделов, составленных в виде набора презентаций. Семинарская часть учебного пособия опирается на использование компьютерного класса с предустановленным пакетом MATLAB. Если читателя интересует только теоретическая часть курса, то он может игнорировать вторую часть курса, состоящую из семинарских занятий. Если же читатель хочет получить оперативный навык расчета, зачастую сводимый к получению числа или графика, то ему необходимо освоить семинары, в которых лекционный материал дублируется вместе с набором программ, запускаемых с помощью пакета MATLAB. В рамках данного учебного пособия удалось охватить следующие темы, традиционно относимые к дискретной математике: теория множеств, алгебраические структуры, булевы функции, логические исчисления, комбинаторика, кодирование и теория графов. Следует отметить особую роль метода Монте-Карло в связи с преподаванием не только дискретной математики, но и других математических дисциплин на базе различного рода пакетов прикладных программ, подобных MATLAB. В частности, особая роль метода Монте-Карло выражается в активном использовании всевозможных генераторов псевдослучайных чисел, имеющихся в ассортименте в современных пакетах прикладных программ, а также идеологии статистических испытаний. Данный курс получил учебную апробацию на примере бакалавров первого года обучения Факультета прикладной математики и информационных технологий Финансового университета при Правительстве РФ в 2019 году. Курс может быть рекомендован студентам младших курсов тех вузов, где дискретная математика излагается с опорой на методы программирования по направлениям: прикладная математика, математическое моделирование, информационные технологии, информационная безопасность и ряд других направлений.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 01.03.01: Математика
- 01.03.02: Прикладная математика и информатика
- 01.03.03: Механика и математическое моделирование
- 01.03.04: Прикладная математика
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
К.Э. Плохотников ДИСКРЕТНАЯ МАТЕМАТИКА В ПАКЕТЕ MATLAB Учебное пособие Москва Издательство «ФЛИНТА» 2020 Таблица №2. Перечень булевых функций двух переменных Переменная ���� 0 0 1 1 Переменная ���� 0 1 0 1 №№ Название Обозначение Несущественные 1 Нуль 0 0 0 0 ����, ���� 2 Конъюнкция ×,∙,∧, & 0 0 0 1 3 0 0 1 0 4 0 0 1 1 ���� 5 0 1 0 0 6 0 1 0 1 ���� 7 Сложение по модулю 2 +, +2, ⨁ 0 1 1 0 8 Дизъюнкция ∨ 0 1 1 1 9 Стрелка Пирса1 ↓ 1 0 0 0 10 Эквивалентность ≡ 1 0 0 1 11 1 0 1 0 ���� 12 1 0 1 1 13 1 1 0 0 ���� 14 Импликация →, ⇒, ⊃ 1 1 0 1 15 Штрих Шеффера2 | 1 1 1 0 16 Единица 1 1 1 1 ����, ���� Таблица №3. Истинность (ложность) базовых логических операций ���� ���� ¬���� ����&���� ���� ∨ ���� ���� ⇒ ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ���� ����
УДК 519.17 ББК 22.176 П 39 Рецензенты: док. физ.-мат. наук, профессор П.Е. Рябов, канд. физ.-мат. наук, доцент С.А. Зададаев Плохотников К.Э. Дискретная математика в пакете MATLAB [Электронный ресурс]: учеб. пособие. — Москва: ФЛИНТА, 2020. — 533с. ISBN 978-5-9765-4431-4 В учебном пособии изложены некоторые классические разделы дискретной математики на базе широко известного пакета прикладных программ MATLAB. Материалы учебного пособия разделены на две части, относимые к лекциям и семинарам соответственно. Лекционная часть не предполагает использование пакета MATLAB и представляет собой набор из семи разделов, составленных в виде набора презентаций. Семинарская часть учебного пособия опирается на использование компьютерного класса с предустановленным пакетом MATLAB. Если читателя интересует только теоретическая часть курса, то он может игнорировать вторую часть курса, состоящую из семинарских занятий. Если же читатель хочет получить оперативный навык расчета, зачастую сводимый к получению числа или графика, то ему необходимо освоить семинары, в которых лекционный материал дублируется вместе с набором программ, запускаемых с помощью пакета MATLAB. В рамках данного учебного пособия удалось охватить следующие темы, традиционно относимые к дискретной математике: теория множеств, алгебраические структуры, булевы функции, логические исчисления, комбинаторика, кодирование и теория графов. Следует отметить особую роль метода Монте-Карло в связи с преподаванием не только дискретной математики, но и других математических дисциплин на базе различного рода пакетов прикладных программ, подобных MATLAB. В частности, особая роль метода Монте-Карло выражается в активном использовании всевозможных генераторов псевдослучайных чисел, имеющихся в ассортименте в современных пакетах прикладных программ, а также идеологии статистических испытаний. Данный курс получил учебную апробацию на примере бакалавров первого года обучения Факультета прикладной математики и информационных технологий Финансового университета при Правительстве РФ в 2019 году. Курс может быть рекомендован студентам младших курсов тех вузов, где дискретная математика излагается с опорой на методы программирования по направлениям: прикладная математика, математическое моделирование, информационные технологии, информационная безопасность и ряд других направлений. ISBN 978-5-9765-4431-4 © Плохотников К.Э., 2020 © Издательство «ФЛИНТА», 2020 П 39 УДК 519.17 ББК 22.176
— 3 — ОГЛАВЛЕНИЕ ЧАСТЬ I (ЛЕКЦИИ) .................................................................... 7 ЛЕКЦИЯ №1 ................................................................................. 8 ТЕОРИЯ МНОЖЕСТВ .............................................................................. 8 §1. Введение .................................................................................................................. 8 §2. Форматы задания дискретных множеств ............................................................ 10 §3. Операции над множествами ................................................................................. 13 §4. Мощность множества ........................................................................................... 15 §5. Декартово произведение множеств ..................................................................... 19 §6. Бинарные отношения между множествами ........................................................ 22 §7. Функциональное отношение между множествами............................................ 24 ЛЕКЦИЯ №2 ............................................................................... 28 АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ .................................................... 28 §1. Введение ................................................................................................................ 28 §2. Алгебра с одной операцией .................................................................................. 33 §3. Группы ................................................................................................................... 37 §4. Алгебра с двумя операциями ............................................................................... 41 §5. Векторное пространство ....................................................................................... 46 §6. Решетки и булева алгебра .................................................................................... 49 ЛЕКЦИЯ №3 ............................................................................... 54 БУЛЕВЫ ФУНКЦИИ .............................................................................. 54 §1. Введение ................................................................................................................ 54 §2. Булевы функции одной и двух переменных ....................................................... 56 §3. Реализация функций формулами ......................................................................... 59 §4. Алгебра булевых функций ................................................................................... 62 §5. Нормальные формы .............................................................................................. 65 §6. Минимальные дизъюнктивные формы ............................................................... 69 §7. Полнота .................................................................................................................. 74 ЛЕКЦИЯ №4 ............................................................................... 79 ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ ........................................................... 79 §1. Пропозициональная логика .................................................................................. 79 §2. Интерпретация логических формул .................................................................... 83 §3. Формальные теории .............................................................................................. 86 §4. Исчисление высказываний как формальная теория .......................................... 92 §5. Исчисление предикатов первого порядка ........................................................... 99 §7. Иллюстрация теорем Геделя .............................................................................. 102
— 4 — ЛЕКЦИЯ №5 ............................................................................. 112 КОМБИНАТОРИКА .............................................................................. 112 §1. Введение .............................................................................................................. 112 §2. Размещения, перестановки и сочетания ........................................................... 114 §3. Биномиальные коэффициенты ........................................................................... 120 §4. Комбинаторные задачи с ограничениями ......................................................... 123 §5. Производящие функции ..................................................................................... 129 ЛЕКЦИЯ №6 ............................................................................. 132 КОДИРОВАНИЕ ..................................................................................... 132 §1. Введение .............................................................................................................. 132 §2. Алфавитное кодирование ................................................................................... 134 §3. Минимизация длины кода сообщения .............................................................. 138 §4. Помехоустойчивое кодирование ....................................................................... 145 §5. Код Хэмминга для исправления одной ошибки замещения ........................... 151 §6. Криптография в части шифрования .................................................................. 155 §7. Шифрование с открытым ключом ..................................................................... 160 ЛЕКЦИЯ №7 ............................................................................. 165 ТЕОРИЯ ГРАФОВ .................................................................................. 165 §1. Введение .............................................................................................................. 165 §2. Иные формы графов ........................................................................................... 167 §3. Изоморфизм графов ............................................................................................ 170 §4. Характеристики графов и его составные элементы......................................... 171 §5. Виды графов и операции над графами .............................................................. 175 §6. Представление графов на компьютере ............................................................. 180 §7. Эйлеровы и гамильтоновы графы ..................................................................... 186 ЧАСТЬ II (СЕМИНАРЫ) ....................................................... 193 СЕМИНАР №1 .......................................................................... 194 ТЕОРИЯ МНОЖЕСТВ .......................................................................... 194 §1. Введение .............................................................................................................. 194 §2. Форматы задания дискретных множеств .......................................................... 196 §3. Операции над множествами ............................................................................... 200 §4. Мощность множества ......................................................................................... 205 §5. Декартово произведение множеств ................................................................... 210 §6. Бинарные отношения между множествами ...................................................... 214 §7. Функциональное отношение между множествами.......................................... 218 §8. Дополнительные задачи ..................................................................................... 222 СЕМИНАР №2 .......................................................................... 229 АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ .................................................. 229 §1. Введение .............................................................................................................. 229
— 5 — §2. Алгебра с одной операцией ................................................................................ 236 §3. Группы ................................................................................................................. 240 §4. Алгебра с двумя операциями ............................................................................. 245 §5. Векторное пространство ..................................................................................... 252 §6. Решетки и булева алгебра .................................................................................. 255 §7. Дополнительные задачи ..................................................................................... 261 СЕМИНАР №3 .......................................................................... 276 БУЛЕВЫ ФУНКЦИИ ............................................................................ 276 §1. Введение .............................................................................................................. 276 §2. Булевы функции одной и двух переменных ..................................................... 280 §3. Реализация функций формулами ....................................................................... 284 §4. Алгебра булевых функций ................................................................................. 288 §5. Нормальные формы ............................................................................................ 292 §6. Минимальные дизъюнктивные формы ............................................................. 297 §7. Полнота ................................................................................................................ 303 §8. Дополнительные задачи ..................................................................................... 309 СЕМИНАР №4 .......................................................................... 318 ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ ......................................................... 318 §1. Пропозициональная логика ................................................................................ 318 §2. Интерпретация логических формул .................................................................. 323 §3. Формальные теории ............................................................................................ 326 §4. Исчисление высказываний как формальная теория ........................................ 333 §5. Исчисление предикатов первого порядка ......................................................... 342 §6. Иллюстрация теорем Геделя .............................................................................. 344 §7. Дополнительные задачи ..................................................................................... 356 СЕМИНАР №5 .......................................................................... 370 КОМБИНАТОРИКА .............................................................................. 370 §1. Введение .............................................................................................................. 370 §2. Размещения, перестановки и сочетания ........................................................... 372 §3. Биномиальные коэффициенты ........................................................................... 381 §4. Комбинаторные задачи с ограничениями ......................................................... 386 §5. Производящие функции ..................................................................................... 394 §6. Дополнительные задачи ..................................................................................... 397 СЕМИНАР №6 .......................................................................... 407 КОДИРОВАНИЕ ..................................................................................... 407 §1. Введение .............................................................................................................. 407 §2. Алфавитное кодирование ................................................................................... 410 §3. Минимизация длины кода сообщения .............................................................. 415 §4. Помехоустойчивое кодирование ....................................................................... 425 §5. Код Хэмминга для исправления одной ошибки замещения ........................... 435 §6. Криптография в части шифрования .................................................................. 441 §7. Шифрование с открытым ключом ..................................................................... 447
— 6 — §8. Дополнительные задачи ..................................................................................... 454 СЕМИНАР №7 .......................................................................... 472 ТЕОРИЯ ГРАФОВ .................................................................................. 472 §1. Введение .............................................................................................................. 472 §2. Иные формы графов ........................................................................................... 475 §3. Изоморфизм графов ............................................................................................ 480 §4. Характеристики графов и его составные элементы......................................... 482 §5. Виды графов и операции над графами .............................................................. 491 §6. Представление графов на компьютере ............................................................. 499 §7. Эйлеровы и гамильтоновы графы ..................................................................... 508 §8. Дополнительные задачи ..................................................................................... 520
Плохотников К.Э. Дискретная математика в пакете MATLAB — 7 — Часть I (Лекции)
Плохотников К.Э. Дискретная математика в пакете MATLAB — 8 — Лекция №1 ТЕОРИЯ МНОЖЕСТВ Приводится введение в дискретную математику. Изучаются форматы задания дискретных множеств, а также операции над множествами. Обсуждаются: понятие мощности множества, декартово произведение множеств, определяется класс бинарных отношений, а также специальный класс бинарных отношений, именуемый функциональным. §1. Введение По теме дискретной математики существует множество учебников и учебных пособий 1. Все они в разном отношении соотносятся с теми или иными пакетами прикладных программ. Предлагаемое учебное пособие, наиболее тесно переплетено с таким пакетом прикладных программ, как MATLAB. Выбор пакета MATLAB связан с авторским предпочтением данного пакета2. Дискретная математика в отличие от непрерывной математики имеет дело с такими понятиями, как множество, элемент множества и пр. При этом как множества, так и соответствующие элементы должны быть отчетливо определены и отделены друг от друга. В дискретной математике множества, как правило состоят либо из конечного числа элементов, либо из счетно-бесконечного набора. Последнее свойство означает, что элементы множества могут быть перенумерованы, например, в формате 1, 2, … , ����, … Дать более конкретные определения каждому из понятий множество, элемент без относительно другого не представляется возможным. Приведем пример того, как трудно в реальности определить конкретное множество и его элементы. Пусть таким множеством выступает человечество. Возникает вопрос: каков элемент человечества? Если в качестве элемента человечества выступает отдельный человек, то как их различить? Если в качестве элемента человечества выступает этнос (народ), то как быть с теми, кто затрудняется в отнесении себя к тому или иному этносу. Если элементом человечества выступает отдельное государство, то человечество, как множество 1 Новиков Ф.А. Дискретная математика: Учебник для вузов. 2- изд. Стандарт третьего поколения, — СПб.: Питер, 2013. — 432с.; Хаггарти Р. Дискретная математика для программистов. М.: Техносфера, 2003. — 320с.; Чашкин А.В. Лекции по дискретной математике: учеб. пособие. — М.: МГУ, мехмат, 2007. — 261с.; Лорьер Ж.-Л. Системы искусственного интеллекта. — М.: Мир, 1991. — 568с.; Аршинов М.Н., Садовский Л.Е. Коды и математика (Рассказы о кодировании). — М.: Наука, 1983. — 144с.; Ерош И.Л., Сергеев М.Б., Соловьев Н.В. — Дискретная математика: учеб. пособие. — СПб: СПбГУАП, 2005. — 144с.; Макоха А.Н., Сахнюк П.А., Червяков Н.И. Дискретная математика: учеб. пособие. — М.: ФИЗМАТЛИТ, 2005. — 368с.; Редькин Н.П. Дискретная математика. — М.: ФИЗМАТЛИТ, 2009. — 264с.; Соболева Т.С., Чечкин А.В. Дискретная математика: учеб. для студ. вузов. — М.: Изд. центр “Академия”, 2006. — 256с.; Судоплатов С.В., Овчинникова Е.В. Дискретная математика. — Новосибирск, 2011. — 143с.; Яблонский С.В. Введение в дискретную математику: учеб. пособие для вузов. — М.: Наука, Гл. ред. Физ.-мат. лит., 1986. — 384с. 2 Плохотников К.Э. Вычислительные методы. Теория и практика в среде MATLAB: курс лекций. Учебное пособие для вузов. — 2-е изд., испр. — М.: Горячая линия – Телеком, 2013. — 496с.; Плохотников К.Э. Методы разработки математических моделей и вычислительный эксперимент на базе пакета MATLAB. — Курс лекций. — М.: СОЛОН-Пресс, 2017. — 628с.; Плохотников К.Э. Базовые разделы математики для бакалавров в среде MATLAB: учебное пособие / Плохотников К.Э., – 2-е изд. – М.: НИЦ ИНФРАМ, 2018. – 1114 с.
Плохотников К.Э. Дискретная математика в пакете MATLAB
— 9 —
становится иным, скорее это глобальное геополитические целое. Таким образом, очевидно, что, меняя толкование элемента, можно поменять смысл исходного множества и, наоборот.
Дискретная математика3 как математическая дисциплина имеет дело с
вполне определенными множествами, когда соответствующие элементы
также вполне хорошо определены. Роль дискретной математики4 как отдельной дисциплины заметно возросла в последнее время в связи с наступлением
компьютерной индустрии вообще и программирования в частности. Наши занятия по дискретной математике будут проходить в пакете прикладных программ MATLAB5.
Множества можно создать, перечисляя его элементы. Построим, используя средства пакета прикладных программ MATLAB все слова, состоящие из
двух букв русского алфавита.
Пример №1. Построить множество слов, ���� состоящих из двух букв русского алфавита.
Решение. Нетрудно сообразить, что всего таких слов будет 332 = 1089.
На семинаре №1 разобрана подходящая программа, которая генерирует все
двухбуквенные слова и составляет соответствующее множество ����. Итог работы программы приведен на рис.1. Программа создала множество ����, состоящего из 1089 двухбуквенных слов, которые все выведены в командное окно
MATLAB.
Рис.1. Множество двухбуквенных слов русского алфавита
Принадлежность элемента ���� множеству ���� записывается в виде ���� ∈ ����.
Наоборот, когда ���� не принадлежит множеству ���� пишут: ���� ∉ ����. Например, элемент ���� = ′яя′ принадлежит двухбуквенному множеству слов русского алфавита, ����, т.е. ���� = ′яя′ ∈ ����, а элемент ����2 = ′я′ не принадлежит, т.е. ����2 = ′я′ ∉ ����.
Набор элементов некоторого множества, зачастую, помещается в фигурные скобки. Так, согласно примеру №1, множество ���� = {аа, аб, … , яя} состоит
3 Новиков Ф.А. Дискретная математика: Учебник для вузов. 2- изд. Стандарт третьего поколения, —
СПб.: Питер, 2013. — 432с.
4 Хаггарти Р. Дискретная математика для программистов. М.: Техносфера, 2003. — 320с.
5 MATLAB — это высокоуровневый язык и интерактивная среда для программирования, численных
расчетов и визуализации результатов. С помощью MATLAB можно анализировать данные, разрабатывать
алгоритмы, создавать модели и приложения: https://matlab.ru/products/matlab
Плохотников К.Э. Дискретная математика в пакете MATLAB
— 10 —
из 1089 элементов. Принято множества обозначать прописными буквами, а
элементы множества строчными буквами латинского алфавита.
Среди всех возможных множеств есть особое множество, которое не содержит элементов, для него вводят специальное обозначение ∅. Например,
можно говорить о множестве квадратных кругов на плоскости. Поскольку таких фигур не может существовать, постольку такое множество является пустым.
В предыдущем примере было построено конечное множество двухбуквенных слов, оно состояло из 1089 слов. Можно говорить о множестве, которое включает бесконечное количество элементов. Например, известно, что во
множестве натуральных чисел {1,2, … , ����, … } имеется бесконечное количество
простых чисел.
Пример №2. Построить график зависимости числа простых чисел из
набора {1, … , ����} в зависимости от ����.
Решение. Так, в наборе {1, … ,5} простыми являются числа 2,3,5 соответственно, а в наборе {1, … ,10} — 2,3,5,7. На рис.2 приведен итог работы соответствующей программы. С учетом графика рис.2 оказывается, что в наборе
{1,2, … , 103} содержится 168 простых чисел.
Рис.2. Зависимость числа простых чисел из набора 1, … , ���� от ����
§2. Форматы задания дискретных множеств
Различают несколько способов задания дискретных множеств. Рассмотрим более подробно три способа: 1) путем прямого перечисления элементов множества; 2) с помощью характеристического предиката; 3) путем использования
некоторой порождающей процедуры.
Плохотников К.Э. Дискретная математика в пакете MATLAB
— 11 —
Пусть в качестве множества выступают все трехбуквенные слова русского алфавита, которых, очевидно, имеется 333 = 35′937. Запишем данное
множество путем прямого перечисления, т.е.
���� = {ааа, ааб, … , яяя
35′937 элементов
}.
(1)
Перечисление элементов в (1) представлено компактно с помощью операции “ … ” или операции и “так далее”. В пакете MATLAB можно вывести в
командное окно все 35′937 элементов множества не используя оператор “ … ”.
Для второго формата определения дискретного множества необходимо
определить предикат ���� = ����(����), который, как правило, в логической форме
проверяет принадлежность элемента ���� множеству ����. Запись в этом случае принято делать в форме:
���� = {����|����(����)}.
(2)
Запись (2) расшифровывается следующим образом: множество ���� состоит из тех элементов ����, предикат которых ����(����) принимает значение “истина”. Вертикальная черта в (2) отделяет элемент множества ���� от условия, которое выражается в виде предиката ����(����).
Отметим, что при задании множества с помощью предиката без какихлибо ограничений возможны парадоксы, один из которых известен как парадокс Рассела. Пусть ���� множество всех множеств, ����, которые не содержат в
качестве элемента самих себя, т.е. ���� = {����|���� ∉ ����}.
Парадокс возникает на пути ответа на вопрос: содержит или нет множество ���� себя в качестве элемента. Действительно, допустим вначале, что ���� ∈ ����,
тогда ���� ∉ ����. Если положить, что ���� ∉ ����, то ���� ∈ ����. Возникает неустранимое логическое противоречие, которое может быть преодолено несколькими способами. За подробностями по этому поводу можно обратиться к более продвинутым учебникам по дискретной математике.
Для иллюстрации второго способа задания множества рассмотрим пример. Пусть в качестве предиката выступает свойство натурального числа ���� делиться без остатка на некоторое ����, т.е. ����(����) = mod(����, ����) = 0. В последнем
уравнении введена функция mod(����, ����), которая находит остаток от деления ����
на ����.
Пример №3. Выбрать из набора ���� = {1,2, … , ����} числа, которые делятся
без остатка на пять, ����5(����). Вычесть из последних единицу, тогда получим множество ����(����) = ����5(����) − 1. Найти среди набора ����(����) число простых чисел
����(����), построить график зависимости числа простых чисел ����(����) от ����.
Решение. С учетом формата записи (2) определим искомое множество
���� = {����|���� ∈ ℕ & mod(���� + 1,5) = 0}.
(3)
В (3) введен символ ℕ, который обычно обозначает множество натуральных чисел, т.е. ℕ = {1,2, … }. Кроме того, в (3) присутствует символ &6, который символизирует союз “и” в перечне условий (после знака “|”), определяющих элементы множества ����.
6 & — амперсанд, от английского слова ampersand
Плохотников К.Э. Дискретная математика в пакете MATLAB
— 12 —
На семинаре№1 приведена подходящая программа, которая производит
все необходимые вычисления и строит искомый график, итог работы которой
приведен на рис.3. Так, количество простых чисел среди набора (3) при ���� =
103, т.е. когда ���� < ���� = 103, равняется 38.
Рис.3. Зависимость числа простых чисел ����(����) от ����
Рассмотрим пример порождающей множество процедуры. Пусть в качестве множества ���� выступают числа последовательности, ����1, … , ��������, …, которые
порождаются итерационной процедурой вида:
��������+1 =
��������2+2
2�������� , ���� = 1,2, … ; ����1 = 1.
(4)
Очевидно, что итерационная процедура (4) порождает бесконечное дискретное множество ����, которое может быть представлено в виде:
���� = {��������|���� ∈ ℕ & ��������+1 =
��������2+2
2�������� & ����1 = 1}.
(5)
Отметим, что последовательность чисел ����1, … , ��������, … сходится к числу
√2.
Пример №4. Найти первые шесть чисел множества ���� из (5), а также оценить, насколько построенные числа близки числу √2.
Решение. Привлекая подходящую программу для подсчета искомых чисел, найдем в Command Window ответ в виде первых шести членов последовательности, а также в виде ошибки, которая оценивает модуль отличия найденных чисел от числа √2. На рис.4 приведен примерный формат ответа.
Согласно рис.4 видно, что шестое число последовательности ����6 =
886731088897/627013566048 имеет точность приближения к числу √2
лучше, чем пятнадцать десятичных знаков после запятой.
Плохотников К.Э. Дискретная математика в пакете MATLAB
— 13 —
Рис.4. Первые шесть членов последовательности, а также ошибка, которая
оценивает модуль отличия найденных чисел от числа √2
§3. Операции над множествами
Обычно рассматривают следующие операции над множествами: объединение,
“ ∪ ”; пересечение, “ ∩ ”; разность, “\”; симметричная разность, “ △ ”. Кроме
того, рассматривается также операция дополнения, которая подразумевает,
что, помимо множества ����, дополнение которого ����̅ необходимо найти, существует некоторое объемлющее множество ����, тогда ����̅ ≝ ����\����, где формат ≝
обозначает “по определению”.
Введем по определению указанные операции, тогда
���� ∪ ���� ≝ {����|���� ∈ ���� ∨ ���� ∈ ����};
���� ∩ ���� ≝ {����|���� ∈ ���� & ���� ∈ ����};
����\���� ≝ {����|���� ∈ ���� & ���� ∉ ����};
���� △ ���� ≝ (���� ∪ ����)\(���� ∩ ����) = {����|(���� ∈ ���� & ���� ∉ ����) ∨ (���� ∉ ���� & ���� ∈ ����)}.
Выше введен символ “ ∨ ”, который обозначает союз “или”.
Рассмотрим в качестве множества ���� набор элементов, перенумерованных числами от 1 до ����.
Пример №5. Случайно сгенерировать подмножества ���� и ���� из множества
���� и определить указанные выше операции над подмножествами ���� и ����.
Рис.5. Случайно сгенерированные множества ���� и ����, а также их
пересечение ���� ∩ ����, которое обозначено, как Inter_A_B.
Плохотников К.Э. Дискретная математика в пакете MATLAB — 14 — Решение. На семинаре №1 приведен подходящий код MATLAB, который генерирует множества ����, ����, ����, а также операции над множествами, которые введены выше. На рис.5 приведен один из возможных результатов работы программы листинга №5 в виде ответа, выведенного в Command Window. На рис.5 приведены случайно сгенерированные множества ���� и ����, а также их пересечение ���� ∩ ����, которое обозначено, как Inter_A_B. Изучим так называемые диаграммы Венна7, которые иллюстрируют операции над множествами с помощью геометрических фигур на плоскости. Пример №6. Нарисовать диаграммы Венна на примере построения многоугольников на плоскости. Нарисовать пересечение, объединение, разность и симметричную разность пары многоугольников ���� и ����. Решение. Итог работы соответствующей программы приведен на рис.6. Итог операций над парой множеств ���� и ���� очерчен черным пунктиром и красной заливкой. В пакете MATLAB операции над полигонами: пересечения, объединения, вычитания и симметричной разности, осуществляются функциями: intersect, union, subtract, xor соответственно. Рис.6. Примеры диаграмм Венна, пересечение, объединение, разность и симметричная разность пары множеств ���� и ���� Пересечение, объединение, разность, дополнение пары подмножеств некоторого множества ���� не выводит за пределы этого множества. Операции над подмножествами обладают рядом важных свойств. Пусть ����, ����, ���� ⊂ ����. В этом случае имеют место следующий набор свойств. 1. Идемпотентность: ���� ∪ ���� = ����, ���� ∩ ���� = ����. 2. Коммутативность: ���� ∪ ���� = ���� ∪ ����, ���� ∩ ���� = ���� ∩ ����. 3. Ассоциативность: ���� ∪ (���� ∪ ����) = (���� ∪ ����) ∪ ����, ���� ∩ (���� ∩ ����) = (���� ∩ ����) ∩ ����. 4. Дистрибутивность: ���� ∪ (���� ∩ ����) = (���� ∪ ����) ∩ (���� ∪ ����), ���� ∩ (���� ∪ ����) = (���� ∩ ����) ∪ (���� ∩ ����). 5. Поглощение: (���� ∩ ����) ∪ ���� = ����, (���� ∪ ����) ∩ ���� = ����. 7 Джон Венн (1834 – 1923) — английский логик и философ.
Доступ онлайн
450 ₽
В корзину