Содержание
- 2. Лекция 1 Множества Цель лекции – познакомить студентов: 1) с общими понятиями теории множеств; 2) с
- 3. 5) с кортежами и с декартовыми произведениями; 6) с отношениями, с бинарными отношениями и их свойствами;
- 4. Введение Дискретная математика – направление в математике, объединяющее отдельные её разделы, ранее сформированные как самостоятельные теории.
- 5. Дискретная математика использует средства, разработанные в классической математике. Однако характер объектов, исследуемых дискретной математикой, настолько разнообразен,
- 6. Совокупность элементов, объединённых некоторым признаком, свойством, составляет понятие множество. Например, множество книг в библиотеке, множество студентов
- 7. Множества удобно изображать с помощью кругов Эйлера. Множество K на рис. 1.1 называют подмножеством множества М
- 8. Универсальным называется множество U, состоящее из всех возможных элементов, обладающих данным признаком. Если множество не содержит
- 9. Множество, элементами которого являются подмножества множества М, называется семейством множества М или булеаном этого множества и
- 10. Множество считается заданным, если перечислены все его элементы, или указано свойство, которым обладают те и только
- 11. Примеры задания множества Множество всех чисел, являющихся неотрицательными степенями числа 2 можно задать: а) перечислением элементов:
- 12. 1.2. Основные операции над множествами Суммой или объединением двух множеств Х и Y называется множество, состоящее
- 13. Пересечением множеств Х и Y называется множество, состоящее из элементов, входящих одновременно и во множество Х,
- 14. Дополнением множества до универсального множества U (рис. 1.6) является множество
- 15. Симметрической разностью множеств X и Y называется множество Z, содержащее либо элементы множества X, либо элементы
- 16. Вместо выражения «любое х из множества Х» можно писать , где перевёрнутая латинская буква А взята
- 17. Множество A можно разбить на классы (непересекающиеся подмножества) Ai, если: объединение всех подмножеств совпадает с множеством
- 18. Для операций над множествами справедливы следующие тождества: законы коммутативности объединения и пересечения законы ассоциативности объединения и
- 19. законы дистрибутивности пересечения относительно объединения и объединения относительно пересечения законы поглощения законы склеивания законы Порецкого Операция
- 20. законы идемпотентности объединения и пересечения законы действия с универсальным (U) и пустым ( ∅ ) множествами
- 21. Пары задают соответствие между множествами A и B, если указано правило R, по которому для элемента
- 22. Образ множества A при соответствии R называется множеством значений этого соответствия и обозначается , если состоит
- 23. Для описания соответствий между множествами используют понятие отображения. Для задания отображения f необходимо указать: множество, которое
- 24. При записи подразумевается, что отображение f определено всюду на A, т.е. A – полный прообраз отображения
- 25. Классификация отображений по мощности На множество «сюръекция»; На множество «биекция»; Во множество «инъекция».
- 26. На множество - «сюръекция» Соответствие. при котором каждому элементу множества А указан единственный элемент множества В,
- 27. На множество - «биекция» Отображение множества А на множество В, при котором каждому элементу множества В
- 28. Во множество - «инъекция» Соответствие. при котором каждому элементу множества А указан единственный элемент множества В,
- 29. Пусть множество А отображается взаимно-однозначно на множество В, т.е. . Тогда отображение , при котором каждому
- 30. 1.4. Классификация множеств. Мощность множества Множество, содержащее конечное число элементов, называется конечным. Пустое множество является конечным
- 31. Основная теорема о конечных множествах Теорема. Любое конечное множество не эквивалентно никакому его собственному подмножеству, кроме
- 32. Кортежем длины n из элементов множества А называется упорядоченная последовательность элементов этого множества. Кортежи и называются
- 33. В отличие от элементов множества элементы кортежа могут совпадать. Например, в прямоугольной системе координат координаты точек
- 34. Существуют кортежи, элементы которых являются только нулями или единицами. Кортеж из нулей и единиц можно рассматривать
- 35. Декартовым (прямым) произведением множеств называется множество , состоящее из всех кортежей длины n, в которых ,
- 36. 1.6. Отношения. Бинарные отношения и их свойства Подмножество называется n-местным отношением R на непустом множестве М.
- 37. симметричность: антисимметричность: асимметричность:
- 38. транзитивность: антитранзитивность: связность: или
- 39. Каждое конкретное отношение может обладать или не обладать указанным свойством. Примеры рефлексивных отношений: «быть не больше»;
- 40. Примеры антисимметричных отношений: «быть меньше или равным»; «быть делителем»; «быть подмножеством»; Примеры асимметричных отношений; «быть больше»;
- 41. Примеры отношений связности: «быть больше», «быть меньше» на множестве N, R; «быть больше или равным», «быть
- 42. Непересекающиеся подмножества, на которые разбивается множество М отношением эквивалентности, называются классами эквивалентности. На множестве обыкновенных дробей
- 43. Отношение эквивалентности – частный случай отношения толерантности. Отношения «быть другом», «быть знакомым», - отношения толерантности, так
- 44. Множество М, которое обладает отношением порядка, называется упорядоченным. Отношение порядка антисимметричность транзитивность + рефлексивность + антирефлексивность
- 45. Отношение называется отношением полного порядка, если сравнимы все элементы множества, на котором задано это отношение. Пример.
- 46. 1.7. Элементы комбинаторики Раздел математики, занимающийся подсчётами количества различных комбинаций между объектами, называется комбинаторикой. Все комбинаторные
- 47. Правило произведения. Если элемент α можно выбрать k способами, а элемент β - m способами, то
- 48. Перестановки. Упорядоченные множества (кортежи), состоящие из n различных элементов, называются перестановками (без повторений). Обозначение : .
- 49. Пример. Из цифр 3, 5, 7, 9 можно составить 4! кортежей, так как n=4, то Р4=4!=4⋅3⋅2⋅1=24,
- 50. Размещения (без повторений). Упорядоченное подмножество m элементов (кортеж), составленное из всего множества, содержащего n элементов, называется
- 51. Сочетания без повторений. Сочетаниями из n элементов по m называется неупорядоченное подмножество (выборка), состоящее из m
- 52. Перестановки с повторениями. Кортеж, имеющий повторяющиеся элементы, называется перестановкой с повторениями. Пусть в кортеже длины n
- 53. 1.8. Подстановки Дано множество . Взаимнооднозначное отображение множества на себя называется подстановкой степени n. Если прообразы
- 54. Чтобы из подстановки получить обратную, нужно поменять местами образы и прообразы, т.е. верхнюю и нижнюю строчки,
- 55. Подстановку вида называют тождественной, так как она каждый элемент множества отображает в этот же элемент. Произведением
- 56. Порядком подстановки называется наименьшее натуральное число λ, такое что . Например, для подстановки λ=3. В подстановке
- 58. Скачать презентацию