Бинарное отношение подмножество декартового произведения

Транзитивность не только про тройки элементов!

Отношение эквивалентно если оно рефлексивно, симметрично и транзитивно

Классы эквивалентности – подмножества образованные в результате разбиение множества отношением эквивалентности

Порядок и упорядоченность это разные свойства!

Как строится замыкание и зачем вообще оно нужно

47.27M

Category: $mathematics$ mathematics

Конса БО

1. Бинарные отношения

2. Бинарное отношение подмножество декартового произведения

А x В - множество всех упорядоченных пар, где на первой
позиции стоит элемент из множества A, а на второй из
множества В
Сколько всего существует вариантов БО заданного на множествах A и B?

3. Бинарное отношение подмножество декартового произведения

4. Способы задания

11. Свойства

12.

Рефлексивность
Симметричность
Транзитивность

13.

Рефлексивность
1. Рефлексивно – каждый
элемент находится в
отношении сам с собой
Симметричность
Транзитивность

14.

Рефлексивность
1. Рефлексивно – каждый
элемент находится в
отношении сам с собой
2. Антирефлексивно –
каждый элемент не
находится в отношении
сам с собой
Симметричность
Транзитивность

Рефлексивность
1. Рефлексивно – каждый
элемент находится в
отношении сам с собой
2. Антирефлексивно –
каждый элемент не
находится в отношении
сам с собой
3. Нерефлексивно – есть
случаи 1 и 2, то есть есть
как элементы с
петельками так и без
Симметричность
1. Симметрично – если у
пары элементов есть
связь в одну сторону, то
также есть связь и в
обратную
Транзитивность

17.

18.

Рефлексивность
Симметричность
1. Рефлексивно – каждый
элемент находится в
отношении сам с собой
1. Симметрично – если у
пары элементов есть
связь в одну сторону, то
также есть связь и в
обратную
2. Антирефлексивно –
каждый элемент не
находится в отношении
сам с собой
3. Нерефлексивно – есть
случаи 1 и 2, то есть есть
как элементы с
петельками так и без
2. Асимметричные и Антисимметричные
3. Несимметричные –
есть случаи 1 и 2
Транзитивность

19.

Рефлексивность
Симметричность
1. Рефлексивно – каждый
элемент находится в
отношении сам с собой
1. Симметрично – если у
пары элементов есть
связь в одну сторону, то
также есть связь и в
обратную
2. Асимметричные –
2. Антирефлексивно –
каждый элемент не
находится в отношении
сам с собой
и Антисимметричные
3. Нерефлексивно – есть
случаи 1 и 2, то есть есть
как элементы с
петельками так и без
3. Несимметричные – есть
случаи 1 и 2
Транзитивность
1. Транзитивность –

20.

Рефлексивность
Симметричность
1. Рефлексивно – каждый
элемент находится в
отношении сам с собой
1. Симметрично – если у
пары элементов есть
связь в одну сторону, то
также есть связь и в
обратную
2. Асимметричные –
2. Антирефлексивно –
каждый элемент не
находится в отношении
сам с собой
и Антисимметричные
3. Нерефлексивно – есть
случаи 1 и 2, то есть есть
как элементы с
петельками так и без
3. Несимметричные – есть
случаи 1 и 2
Транзитивность
1. Транзитивность –
2. Антитранзитивность

21.

Рефлексивность
Симметричность
1. Рефлексивно – каждый
элемент находится в
отношении сам с собой
1. Симметрично – если у
пары элементов есть
связь в одну сторону, то
также есть связь и в
обратную
2. Асимметричные –
2. Антирефлексивно –
каждый элемент не
находится в отношении
сам с собой
и Антисимметричные
3. Нерефлексивно – есть
случаи 1 и 2, то есть есть
как элементы с
петельками так и без
3. Несимметричные – есть
случаи 1 и 2
Транзитивность
1. Транзитивность –
2. Антитранзитивность
3. Нетранзитивность –
есть случаи 1 и 2

22. Транзитивность не только про тройки элементов!

Транзитивность двух
элементов:
Транзитивность одного
элемента!

23. Исключения из свойств

Исключение – мы не можем подставить формулы свойств к
графу и отнести к одному из видов свойств, то есть мы не
можем однозначно определить свойство

24. Исключения

Рефлексивно
Симметрично и
антисимметрично
Транзитивно
Антирефлексивно
Асимметрично +
антисимметрично
Транзитивно и
антитранзитивно
Антирефлексивно
Симметрично и
асимметрично +
антисимметрично
Транзитивно и
антитранзитивно
Рефлексивно и
антирефлексивно
Симметрично и асимметрично
и антисимметрично
Транзитивно и
антитранзитивно

25. Эквивалентность

26. Отношение эквивалентно если оно рефлексивно, симметрично и транзитивно

27. Отношение эквивалентно если оно рефлексивно, симметрично и транзитивно

28. Отношение эквивалентно если оно рефлексивно, симметрично и транзитивно

Разбиение:

29. Отношение эквивалентно если оно рефлексивно, симметрично и транзитивно

Разбиение:

30. Отношение эквивалентно если оно рефлексивно, симметрично и транзитивно

Разбиение:

31. Классы эквивалентности – подмножества образованные в результате разбиение множества отношением эквивалентности

32. Классы эквивалентности – подмножества образованные в результате разбиение множества отношением эквивалентности

Порождающий элемент – некоторый элемент, находящийся в
отношении со всеми элементами своего класса

33. Тренировка

Что является разбиением:
а) {{1, 2}, ∅, {3, 4, 5}, {6, 7}}
б) {{1, 2}, {3, 4, 5}, {6, 7}}
в) {{1, 7}, {3, 4, 6}}
г) {{1, 5}, {3, 4, 5}, {2, 6, 7}}
д) {{1, 2, 3, 4, 5, 6, 7}}

34. Тренировка

Выясните, какие из следующих отношений на множестве
A={0,1, 2, 3, 4, 5, 6, 7, 8, 9} являются отношениями
эквивалентности. Найдите классы эквивалентности.
1.R₁: aR₁b ⇔ a ≡ b (mod 3)
2.R₂: aR₂b ⇔ a² ≡ b² (mod 10)
3.R₁ ∩ R₂

35. Порядок и упорядоченность

36. Порядок

1. Строгий
2. Нестрогий
3. Нет порядка

37. Порядок

1. Строгий
2. Нестрогий
3. Нет порядка

38. Порядок

1. Строгий
2. Нестрогий
3. Нет порядка – все что не имеет набора свойств 1 или 2

39. Упорядоченность

Линейная
Частичная

40. Упорядоченность

Линейная
Частичная

41. Упорядоченность

Линейная
Частичная

42. Упорядоченность

Линейная
Частичная

43. Упорядоченность

Линейная
Частичная

44. Упорядоченность

Линейная
Частичная

45. Упорядоченность

Линейная
Частичная - все остальное!

46. Линейная упорядоченность

1. Проверяем, что нет симметричных пар
2. Находим исток и заносим его в линию в конец
3. Удаляем исток –> образуется новый (если нет – не
линейное)
4. Повторяем пункт 2 и 3 пока есть вершины
5. Полученную последовательность связываем
стрелками
6. Вы прекрасны

47. Порядок и упорядоченность это разные свойства!

Задание Вам: показать все 6 возможных комбинаций, чтобы
увидеть, что у мы не ограничены (как например, что рефл отменяет
антитранз)

48. Отношения соответствия

49. Взаимно-однозначное

Круто, да это ж круто:
Вообще отстой:

50. Одно-многозначное и Много-однозначное

51. Много-многозначное

52. Тренировка

Даны бинарные отношения R₁, R₂, …, R₉ на указанных множествах.
1. «a ∈ A на 4 больше, чем b ∈ B», где A — множество всех целых чисел; A = B
2. «a ∈ A есть делитель b ∈ B», где A = {2, 3, 5}, B = {4, 8, 9, 25, 27, 125}
3. «пассажир a ∈ A едет в вагоне b ∈ B», где A — множество пассажиров поезда; B — множество вагонов; |B| > 1; в каждом вагоне
более одного пассажира
4. «a ∈ A слушает лекцию в аудитории b ∈ B», где A — множество студентов; B — множество аудиторий; |B| > 1; в каждой
аудитории более одного студента
5. «2a ≠ 3b», где a, b ∈ {1, 2, 8}
6. «a − b = 0», где a, b — натуральные числа
7. «a ≥ b», где a ∈ {6, 7, 9}; b ∈ {3, 4}
8. «a + b — нечётное число», где a ∈ {2, 3, 4, 5}; b ∈ {6, 7, 8, 9}
9. «скрипка a ∈ A находится в футляре b ∈ B», где A — множество скрипок, B — множество футляров
Указать:
• а) взаимно-однозначное соответствие
• б) одно-многозначные соответствия
• в) много-однозначные соответствия
• г) много-многозначные соответствия

53. Функциональные отношения

54. Функциональные БО

Всюдуопр.
Частичноопр.

55. Функциональные БО

Всюдуопр.
Частичноопр.

56. Функциональные БО

Всюдуопр.
Частичноопр.

57. Функциональные БО

Всюдуопр.
Частичноопр.

58. Функциональные БО

Всюдуопр.
Частичноопр.

59. Функциональные БО

Всюдуопр.
Частичноопр.

60. Функциональные БО

НЕ ФУНКЦИОНАЛЬНОЕ БО ТК У 3 БОЛЬШЕ 1 Y
Всюдуопр.
Частичноопр.

61. Биекция/инъекция/сюръекция

Инъективность означает, что разные аргументы X дают
разные значения Y.

62. Биекция/инъекция/сюръекция

Сюръективность означает, что достигается каждый элемент

English Русский Rules