Основы дискретной математики и теории алгоритмов. Основные понятия теории множеств. Тема 1 презентация
Содержание
- 2. Раздел 1. Множества
- 3. Тема 1. Основные понятия теории множеств
- 4. Определения, термины, символы Множество — совокупность различимых между собой объектов, объединяемых в целое некоторым общим признаком.
- 5. а∈А — а принадлежит множеству А; а∉А – а не принадлежит множеству А. Записью а1, а2,
- 6. Задание множеств Перечислением элементов: А={ a1, a2, ... , ak }; Указанием характеристического свойства (хар. предикатом):
- 7. Характеристический предикат – это некоторое условие, выраженное в форме логического утверждения или процедур, возвращающей логическое значение
- 8. Подмножество множества А — множество В, у которого все его элементы принадлежат и А : В⊆А
- 9. Мощностью множества А (|A|) называется количество элементов множества А. Множество, не содержащее ни одного элемента, называется
- 10. Универсальное множество (U) – это множества всех элементов, которые могут встретиться в данном исследовании. В различных
- 11. Разбиением множества А называется такая совокупность F непустых подмножеств множества А , что каждый элемент множества
- 12. Основные числовые множества Натуральные числа N = {1;2;3;…;n;…} Целые числа Z = {…;-n;…;-2;-1;0;1;2;…;n;…} Рациональные числа Q
- 13. Множество, число элементов которого конечно называется конечным и бесконечным в противном случае. Бесконечные множества разделяются на
- 14. Равномощные множества Взаимно однозначным соответствием между двумя множествами А и В называется такое правило (закон) f,
- 15. Условные обозначения ∀ – любое, для всех ∃ – существует ∃! – существует и единственый =>
- 16. Добавление и удаление элементов Если А – множество, а x – элемент, причём х∉А, то х
- 17. Теорема 1. Любое непустое конечное множество равномощно некоторому отрезку натурального ряда. ∀А| A≠∅ ∧ |A| ∃k∈N|A|=|1…k|
- 18. Пример: Пусть А – множество всех натуральных чётных чисел, а В – множество всех натуральных чисел,
- 19. Операции над множествами Равенство множеств Множества А и В равны, А=В, тогда и только тогда, когда
- 20. Пересечение множеств Пересечением множеств А и В называется множество С, состоящее из всех элементов, которые принадлежат
- 21. Разность множеств Разностью множеств А и В называется множество С, состоящее из тех элементов множества А,
- 22. Симметрическая разность множеств Симметрической разностью множеств А и В (обозначение АΔВ) называется множество (А\В)∪(В\А). Дополнение множеств
- 23. Названные операции и свойства могут быть продемонстрированы с помощью Диаграмм Венна. Порядок выполнения операций Сначала выполняется
- 24. Алгебраические свойства операций над множествами 1) А∪А=А 1') А∩А=А — идемпотентность 2)А∪В=В∪А 2’) А∩В=В∩А — коммутативность
- 25. 8) ∅=U 8') U= ∅ 9) А∪(А ∩ В)=А 9') А∩(А∪В)=А — законы поглощения 10) A∪B=A
- 26. Докажем, что (А\В)∪(В\А) = (А∪В)\(А∩В). Пусть А и В произвольные подмножества некоторого универсального множества U. На
- 27. Тема 2. Упорядоченное множество (кортеж)
- 28. Кортеж – это последовательность элементов, т.е. совокупность элементов, а которой каждый элемент занимает определённое место. Кортеж
- 29. Кортежи длиной 2 называются упорядоченными парами или просто парами. Кортежи длинной 3 называются тройками. В общем
- 30. Два конечных кортежа равны, если они имеют одинаковую длину и соответствующие компоненты равны: (а1, …, аm)
- 31. Пример. Пусть А:= {1, 2}, В:= {1, 3, 4}. Тогда: А × В= {(1, 1), (1,
- 32. Операция прямого произведения легко распространяется на любое количество множеств. Прямым произведением множеств А1, А2,…,Аr, r∈N называется
- 33. Проекция кортежа Проекцией кортежа v = (v1, …, vn), n∈N, на i-ю ось (обозначение прiv) называется
- 34. Пусть V–множество кортежей одинаковой длины. Тогда проекция множества V на i-ую ось называется множество проекций всех
- 35. Булева алгебра Пусть задано множество U, P(U) – булеан множества U. Алгебра В = (P(U), ∪,
- 36. Пусть U – универсальное множество, А, В, С – произвольные подмножества U. На рис. приведены диаграммы
- 37. На рис. приведены диаграммы Эйлера – Венна для алгебраических выражений (А∩В)∪С (объединение заштрихованных множеств) и (А∪С)∩(В∪С)
- 38. Установление тождеств алгебры множеств с помощью диаграмм Эйлера – Венна в ряде случаев оказывается неудобным. Доказательство
- 39. Будем использовать метод двустороннего включения. Предположим, что х∈ , т. е. что х∉А∪В. Это значит, что
- 40. Симметрическая разность Симметрической разностью множеств А и В (обозначение АΔВ) называется множество (А\В)∪(В\А). Очевидно, что ВΔА
- 41. Тема 3. Соответствия
- 42. Пусть X и Y – два непустых множества. Если определен способ сопоставления элементов Y элементам Х,
- 43. Кроме рассмотренных множеств X, Y и Q с каждым соответствием неразрывно связаны еще два множества: множество
- 44. Множество всех у∈Y, соответствующих элементу х∈Х, называется образом х в Y при соответствии q. Множество всех
- 45. Соответствие q называется функциональным (или однозначным), если образом любого элемента х∈пр1Q является единственный элемент у∈пр2Q. Соответствие
- 46. Пример. Пусть Х = {1, 2}, Y = {3, 5}, значит, Х × Y = {(1,
- 47. Обозначим qi соответствие с графиком Qi, Рассмотрим соответствие q9. Областью определения соответствия q9 является пр1Q9 =
- 48. На рис. изображено геометрическое представление соответствия q11. Графиком обратного соответствия q11–1 является множество Q11–1={(3, 1), (5,
- 49. Примеры соответствий Англо-русский словарь Различные виды кодирования Представление чисел в различных системах счислений Секретные шифры Кодирование
- 50. Композиция двух соответствий Композицией двух соответствий называется последовательное применение двух соответствий. Композиция двух соответствий есть операция
- 51. Композицию соответствий q и р будем обозначать р°q (знак ° аналогичен умножению и часто опускается), а
- 52. Естественно, что операцию композиции можно распространить и на большее, чем два, число соответствий. Композиция n соответствий
- 53. Пусть f: X→Y – функция. Будем обозначать D(f) область определения функции и E(f) область значений функции
- 54. Функция, полученная из f1, …, fn некоторой подстановкой их друг в друга и переименованием аргументов, называется
- 55. 1. Наиболее простой способ задания функций – это табличный. Таблицы при этом представляют собой конечные списки
- 56. Рассмотрим множество Х := {1, 2, 3} и два преобразования этого множества – функции α и
- 57. 2. Аналитический, или формула, описывающая функцию с помощью суперпозиции других(исходных) функций. Если способ вычисления исходных функций
- 58. Приведем некоторые свойства функций и их композиций. 1. Композиция сюръективных функций сюръективна (следует из определений). 2.
- 59. Оператор Оператором называется функциональное отображение l: X → Y, в котором Х и Y являются множествами
- 60. Пример. Рассмотрим предложенную фон Нейманом блок-схему ЭВМ, которая состоит из множества взаимосвязанных устройств М= {a, b,
- 61. Построим матрицу данного отношения:
- 62. Бинарное отношение Бинарное отношение - это отношение между двумя объектами. Бинарное отношение можно определить как совокупность
- 63. Некоторым из наиболее известных отношений присваивают специальные названия и обозначения. Примеры: эквивалентность (=), отношение порядка(>) или(>),
- 64. Полем бинарного отношения R называют объединение его левой и правой областей: F (R)= R_∪ R+. Бинарное
- 65. Способы задания бинарных отношений Способы задания отношений зависят от свойств бинарного отношения. Различают следующие способы задания
- 66. 3. Графическое задание бинарного отношения предполагает графическое представление элементов левой и правой областей отношения в виде
- 67. 4. Бинарное отношение можно задать в табличной форме. В этой таблице указываются все элементы поля отношения
- 68. Операции над бинарными отношениями Так как всякое бинарное отношение– это множество упорядоченных пар, то над бинарными
- 69. Например, пусть рассматриваются отношения R = {(1, 1), (1, 2), (1, 3), (3, 3)} и S
- 70. Композицией бинарных отношений R и S называют бинарное отношение Т, состоящее из всех упорядоченных пар (а,b),
- 71. Свойства бинарных отношений Бинарное отношение R называют рефлексивным, если для любого элемента а ∈F(R) имеет место
- 72. Бинарное отношение R симметричное, если из aRb следует bRa. Примерами таких отношений являются отношение равенства (=),
- 73. Бинарное отношение R называют транзитивным, если из aRb и bRc следует aRc. Примерами транзитивных отношений являются
- 74. Классом эквивалентности Ra называют множество всех вторых компонентов упорядоченных пар отношения эквивалентности R, у которых первой
- 75. Пример. Бинарное отношение S1 является отношением эквивалентности. В нем каждый класс эквивалентности состоит также из одного
- 77. Скачать презентацию