Отношения на множествах

Июль 23, 2022

Главная
Математика
Отношения на множествах

Содержание

2. Декартово (прямое) произведение Декартово произведение множеств: A×B = { (a,b)| a∈A, b∈B} Прим. (a,b) ≠ (b,a)
3. Отношения на множествах Отношение R из множества A в множество B – это подмножество прямого произведения
4. Примеры отношений 1) Пусть N – множество натуральных чисел; Тогда можно писать 3 2) Пусть |
5. Примеры отношений 3) Пусть N – множество линий на плоскости; R – отношение «линии пересекаются» или
6. Образ и прообраз Для некоторого элемента а множества А поставлен в соответствие некоторый элемент b из
7. Операции над отношениями Над отношениями можно выполнять все теоретико-множественные операции, поскольку каждое отношение – это некоторое
8. Операции над отношениями Две специфические операции над отношениями: Если R1 : A → B, а R2
9. Операции над отношениями Графики прямых и обратных бинарных отношений, определенных на множестве действительных чисел, симметричны относительно
10. Свойства операций над отношениями (R-1)-1 = R - очевидно, по определению обратного отношения (R2 ° R1)-1
11. Представление отношений Список R = {(a,b),(a,c),(a,d),(d,b)} Порождающая процедура Характеристическое свойство R = {(a,b)| a,b – целые
12. Ядро отношений Если задано отношение R : A → B, то отношение ker R = R-1
13. Свойства отношений Будем рассматривать бинарное отношение R на A. Рефлексивность ∀a∈A aRa Симметричность ∀a,b∈A aRb ⇒
14. Свойства отношений Будем рассматривать бинарное отношение R на A. 7. Антитранзитивность ∀a,b,c∈A aRb, bRc ⇒ (a,c)
15. Свойства отношений Рассмотрим бинарные отношения R1 и R2 на множестве A студентов 1-го курса, где R1
16. Свойства отношений Если отношение рефлексивно, симметрично и транзитивно, то оно называется отношением эквивалентности. Если отношение антирефлексивно,
17. Рефлексивное замыкание Пусть R – бинарное отношение на множестве А. Рефлексивное замыкание R есть наименьшее рефлексивное
18. Симметричное замыкание Пусть R – бинарное отношение на множестве А. Симметричное замыкание R есть наименьшее симметричное
19. Транзитивное замыкание Пусть R – бинарное отношение на множестве А. Транзитивное замыкание R0 есть наименьшее транзитивное
20. Покрытия и разбиение Для заданного множества M конечное или счетное семейство подмножеств Mi (обозначается { Mi
21. Покрытия и разбиение Теорема: отношение эквивалентности на некотором множестве M порождает его разбиение на классы эквивалентности
22. Покрытия и разбиение Пример 1. Отношение тождественности. Пусть A – произвольное множество; I – отношение тождественности
23. Фактор-множество Множество классов эквивалентности множества A по отношению эквивалентности R называется фактор-множеством и обозначается A/R. Фактор-множество
24. Верхняя и нижняя границы и грани Пусть - отношение нестрогого порядка на множестве A. Будем говорить,
25. Верхняя и нижняя границы и грани Пример 1. Отношение включения множеств ⊂ Пусть ⊂ - отношение
26. Ограниченные множества Говорят, что в множестве с заданным на нем отношением порядка есть минимальный элемент a,
28. Скачать презентацию

Слайд 2

Декартово (прямое) произведение
Декартово произведение множеств:
A×B = { (a,b)| a∈A, b∈B}
Прим.

(a,b) ≠ (b,a)
A×B×C = (A×B)×C = {(a,b,c)| a∈A, b∈B, c∈C}
A0 = {∅}, A1 = A,
An = A×A×...×A – n-степень множества А

n раз

Слайд 3

Отношения на множествах
Отношение R из множества A в множество B –

это подмножество прямого произведения множества A на множество B:
R ⊆ A × B, R : A → B
Обозн. (a, b) ∈ R обычно записывают как aRb.
Если A = B, то говорят, что R ⊆ A × A - отношение на A.
Если отношение установлено между двумя множествами, то его называют бинарным.

Слайд 4

Примеры отношений
1) Пусть N – множество натуральных чисел; < - отношение

«меньше» на N.
Тогда можно писать 3 < 5 или (3, 5) ∈ <

2) Пусть | - отношение «делит» на N.: a | b, если b делится на a.
Например, 3 | 12, 5 | 5, 1 | k для любого k.
Отношение на дискретном множестве A можно изображать в виде графа, например, отношение «делит» на множестве { 1, 2, 3, 4, 5, 6 } может быть изображено в виде:

Слайд 5

Примеры отношений
3) Пусть N – множество линий на плоскости; R –

отношение «линии пересекаются» или «линии параллельны».
4) Пусть N – студентов, живущих в общежитии ЧелГУ; R – отношение «соседи по одной комнате», или «знакомы», или «нравится» и т.д.

Слайд 6

Образ и прообраз
Для некоторого элемента а множества А поставлен в

соответствие некоторый элемент b из множества B, который называется образом элемента а и записывается b = R(a).
Тогда а = R-1(b) — прообраз элемента
Пример. А — множество парабол,
В — множество точек плоскости,
R — соответствие «вершина параболы»,
то R(a) — точка, являющаяся вершиной параболы a,
a R-1(b) состоит из всех парабол аi с вершиной в точке b

Слайд 7

Операции над отношениями
Над отношениями можно выполнять все теоретико-множественные операции, поскольку каждое

отношение – это некоторое множество.
Пусть на множестве натуральных чисел N заданы отношения «меньше» (<), «равны» (=) и «делит» (|). Тогда можно рассмотреть следующие отношения:
< ∪ = - в результате получается отношение ≤
< ∩ | - в результате получается отношение «делит, но не равно»
| \ = - в результате также получается отношение «делит, но не равно»
< - (дополнение до N x N) - в результате получается отношение ≥

Слайд 8

Операции над отношениями
Две специфические операции над отношениями:
Если R1 : A →

B, а R2 : B → C, то отношением R2°R1 (композиция R1 и R2) будет называться отношение
R = R2°R1, R:A→C, R = {(a,c)| ∃b∈B: (a,b)∈R1, (b,c)∈R2}
Если R : A → B, то отношением R-1 (обратное к R отношение) будет называться отношение R-1 : B → A, R-1 = { (b,a) | (a,b)∈R }
Например:
| ° < a (| ° <) b, если найдется c такое, что a < c и c | b.
<-1 a(<-1) b, если b < a, поэтому (<-1) = (>)

Слайд 9

Операции над отношениями
Графики прямых и обратных бинарных отношений, определенных на множестве

действительных чисел, симметричны относительно биссектрисы I и III квадрантов.
Это свойство обратных бинарных отношений используют при построении графиков обратных функций, например: у = log2x и у=2х
Пример 1.
у = х2 и у = √x,
где х ≥ 0

Слайд 10

Свойства операций над отношениями
(R-1)-1 = R - очевидно, по определению обратного отношения
(R2

° R1)-1 = R1-1 ° R2-1 - действительно, (a,b) ∈ (R2 ° R1)-1 ⇔ (b,a) ∈ (R2 ° R1),
то есть найдется c такое, что (b,c) ∈ R1 и (c,a) ∈ R2,
то есть (c,b) ∈ R1-1 и (a,c) ∈ R2-1 ⇔ (a,b) ∈ (R1-1 ° R2-1)

-1

Слайд 11

Представление отношений
Список
R = {(a,b),(a,c),(a,d),(d,b)}
Порождающая процедура
Характеристическое свойство
R = {(a,b)| a,b –

целые и a2 + b2 > 100}
Граф
Матрица

Слайд 12

Ядро отношений
Если задано отношение R : A → B, то отношение

ker R = R-1 ◦ R называется ядром отношения R.
ker R – это отношение из A и A.

Слайд 13

Свойства отношений
Будем рассматривать бинарное отношение R на A.
Рефлексивность ∀a∈A aRa
Симметричность ∀a,b∈A aRb ⇒

bRa
Транзитивность ∀a,b,c∈A aRb, bRc ⇒ aRc
Рассматривают еще:
4. Антирефлексивность ∀a∈A aRa
5. Антисимметричность ∀a,b∈A aRb, bRa ⇒ a = b
6. Асимметричность ∀a,b∈A aRb ⇒ bRa

Слайд 14

Свойства отношений
Будем рассматривать бинарное отношение R на A.
7. Антитранзитивность ∀a,b,c∈A aRb, bRc

⇒ (a,c) ∉R
8. Связность
Прим. 1. Каждое конкретное отношение может обладать или не обладать указанным свойством.
Прим. 2. Если отношение не облает свойством рефлексии, это не означает, что оно является антирефлексивным. Отношение может быть не рефлексивным и не антирефлексивным.

или

Слайд 15

Свойства отношений
Рассмотрим бинарные отношения R1 и R2 на множестве A студентов

1-го курса, где
R1 – отношение «родились в одном месяце»
R2 – отношение «выше по росту».
Рефлексивность ∀a∈A aRa
Симметричность ∀a,b∈A aRb ⇒ bRa
Транзитивность ∀a,b,c∈A aRb, bRc ⇒ aRc
4. Антирефлексивность ∀a∈A aRa
5. Антисимметричность ∀a,b∈A aRb, bRa ⇒ a = b
6. Асимметричность ∀a,b∈A aRb ⇒ bRa
7. Антитранзитивность ∀a,b,c∈A aRb, bRc ⇒ (a,c) ∉R
8. Связность

или

Слайд 16

Свойства отношений
Если отношение рефлексивно, симметрично и транзитивно, то оно называется отношением

эквивалентности.
Если отношение антирефлексивно, асимметрично и транзитивно, то оно называется отношением строгого порядка.
Если отношение рефлексивно, антисимметрично и транзитивно, то оно называется отношением нестрогого порядка.
Нестрогий порядок P называется полным (или линейным), если ∀a,b∈A aPb или bPa. Строгий порядок P называется полным, если для любых различных a и b верно aPb или bPa. Если порядок не полный, то он называется частичным.

Слайд 17

Рефлексивное замыкание
Пусть R – бинарное отношение на множестве А.
Рефлексивное замыкание

R есть наименьшее рефлексивное отношение на А, содержащее R как подмножество.
…или другими словами…
Пусть I = {(a,a)| для некоторого a ∈ A}.
Тогда R ∪ I есть рефлексивное замыкание R.
Пример. Рефлексивное замыкание для отношения < - это ≤.

Слайд 18

Симметричное замыкание
Пусть R – бинарное отношение на множестве А.
Симметричное замыкание

R есть наименьшее симметричное отношение на А, содержащее R как подмножество.
…или другими словами…
R ∪ R -1 есть симметричное замыкание R.
Пример. Симметричное замыкание для отношения < - это ≠.

Слайд 19

Транзитивное замыкание
Пусть R – бинарное отношение на множестве А.
Транзитивное замыкание

R0 есть наименьшее транзитивное отношение на А, содержащее R как подмножество.
…или другими словами…
Транзитивное замыкание R0 состоит из таких и только таких пар элементов a,b из A , для которых в A существует цепочка из k + 2 элементов A , k ≥ 0, a,c1,c2 ,...,ck ,b , между соседними элементами которой выполняется R , т. е.
R0 ={(a,b)| (a,c1),(c1,c2),...,(ck,b) ∈ R}.
Пример. Если R – отношение «быть сыном», то R0 – «быть прямым потомком».
Прим. Если отношение R транзитивно, то R = R0.

Слайд 20

Покрытия и разбиение
Для заданного множества M конечное или счетное семейство подмножеств

Mi (обозначается { Mi }) называется покрытием M, если
Покрытие { Mi } называется разбиением M, если множества Mi не пересекаются:
Mi ∩ Mj = ∅ при i ≠ j.
Пусть N+ - множество натуральных чисел, больших единицы, а Ni – множество натуральных чисел, делящихся на i. Тогда семейство образует покрытие N+.
Пусть для заданного m Mi – множество целых чисел n таких, что n ≡ i mod m. Тогда семейство образует разбиение множества всех целых чисел.

Слайд 21

Покрытия и разбиение
Теорема: отношение эквивалентности на некотором множестве M порождает его

разбиение на классы эквивалентности – множества элементов, эквивалентных между собой.
Если R – отношение эквивалентности, то мы говорим, что a эквивалентно b, если aRb.
Ясно, что можно говорить о множествах элементов, эквивалентных между собой, поскольку отношение эквивалентности рефлексивно, симметрично и транзитивно.
Ясно, что классы эквивалентности образуют покрытие множества, поскольку каждый элемент множества эквивалентен, по крайней мере, самому себе (по рефлексивности).
Ясно, что классы эквивалентности не пересекаются, поскольку любой элемент, принадлежащий двум разным классам, будет эквивалентен всем элементам как первого, так и второго класса (по транзитивности).
Значит, классы эквивалентности образуют разбиение множества M, и теорема доказана.

Слайд 22

Покрытия и разбиение
Пример 1. Отношение тождественности.
Пусть A – произвольное множество; I

– отношение тождественности на нем: aIb тогда и только тогда, когда a и b – один и тот же элемент. Классы эквивалентности, порожденные этим отношением – это все одноэлементные множества, содержащие элементы множества A.
Пример 2. Отношение сравнимости по заданному модулю.
Пусть N – множество натуральных чисел; Rm – отношение на нем: aRmb тогда и только тогда, когда a ≡ b mod m. Классы эквивалентности, порожденные этим отношением – это подмножества натуральных чисел, имеющих один и тот же остаток при делении на m.

Слайд 23

Фактор-множество
Множество классов эквивалентности множества A по отношению эквивалентности R называется фактор-множеством

и обозначается A/R.
Фактор-множество является подмножеством булеана A: A/R ⊂ 2A.
Пример. Отношение сравнимости по заданному модулю.
Пусть Z – множество целых чисел; R5 – отношение на нем: aR5b тогда и только тогда, когда a ≡ b mod 5.
Классы эквивалентности: {1,6,11,16,…},{2,7,12,…},{3,8,13,…},{4,9,14,…},{0,5,10,…}.
Фактор-множество: Z/R5 = {[1],[2],[3],[4],[0]}

Слайд 24

Верхняя и нижняя границы и грани
Пусть - отношение нестрогого порядка на

множестве A. Будем говорить, что c – нижняя граница для элементов a и b, если c a и c b.
Аналогично, будем говорить, что c – верхняя граница для элементов a и b, если a c и b c.
Будем говорить, что c – нижняя грань для элементов a и b, если c – наибольшая нижняя граница этих элементов, то есть для любой нижней границы d элементов a и b d c. Обозначение: c = inf (a, b).
Аналогично, c – верхняя грань для элементов a и b, если c – наименьшая верхняя граница этих элементов, то есть для любой верхней границы d элементов a и b c d. Обозначение: c = sup (a, b).
Теорема: если нижняя грань для заданных двух элементов существует, то только одна.

Слайд 25

Верхняя и нижняя границы и грани
Пример 1. Отношение включения множеств ⊂
Пусть

⊂ - отношение «есть подмножество» на булеане некоторого множества U. Для любых двух множеств A и B существуют их верхняя и нижняя грани. inf(A,B) = A ∩ B; sup(A,B) = A ∪ B.
Пример 2. Отношение делимости
Пусть | - отношение «делит» на множестве натуральных чисел N. Для любых двух чисел a и b существуют их верхняя и нижняя грани. inf(a,b) = НОД(a,b); sup(a,b) = НОК(a,b).

Слайд 26

Ограниченные множества
Говорят, что в множестве с заданным на нем отношением порядка

есть минимальный элемент a, если a есть нижняя граница для любых двух элементов множества (ограниченное снизу множество).
Говорят, что в множестве с заданным на нем отношением порядка есть максимальный элемент a, если a есть верхняя граница для любых двух элементов множества (ограниченное сверху множество).
Множество называется ограниченным, если в нем есть минимальный и максимальный элементы.

Отношения на множествах

Содержание

Декартово (прямое) произведение Декартово произведение множеств: A×B = { (a,b)| a∈A, b∈B}Прим.

Отношения на множествахОтношение R из множества A в множество B –

Примеры отношений1) Пусть N – множество натуральных чисел; < - отношение

Примеры отношений3) Пусть N – множество линий на плоскости; R –

Образ и прообраз Для некоторого элемента а множества А поставлен в

Операции над отношениямиНад отношениями можно выполнять все теоретико-множественные операции, поскольку каждое

Операции над отношениямиДве специфические операции над отношениями:Если R1 : A →

Операции над отношениямиГрафики прямых и обратных бинарных отношений, определенных на множестве

Свойства операций над отношениями(R-1)-1 = R - очевидно, по определению обратного отношения(R2

Представление отношенийСписокR = {(a,b),(a,c),(a,d),(d,b)}Порождающая процедураХарактеристическое свойство R = {(a,b)| a,b –

Ядро отношенийЕсли задано отношение R : A → B, то отношение

Свойства отношенийБудем рассматривать бинарное отношение R на A.Рефлексивность ∀a∈A aRaСимметричность ∀a,b∈A aRb ⇒

Свойства отношенийБудем рассматривать бинарное отношение R на A.7. Антитранзитивность ∀a,b,c∈A aRb, bRc

Свойства отношенийРассмотрим бинарные отношения R1 и R2 на множестве A студентов

Свойства отношенийЕсли отношение рефлексивно, симметрично и транзитивно, то оно называется отношением

Рефлексивное замыканиеПусть R – бинарное отношение на множестве А. Рефлексивное замыкание

Симметричное замыканиеПусть R – бинарное отношение на множестве А. Симметричное замыкание

Транзитивное замыканиеПусть R – бинарное отношение на множестве А. Транзитивное замыкание

Покрытия и разбиениеДля заданного множества M конечное или счетное семейство подмножеств

Покрытия и разбиениеТеорема: отношение эквивалентности на некотором множестве M порождает его

Покрытия и разбиениеПример 1. Отношение тождественности.Пусть A – произвольное множество; I

Фактор-множествоМножество классов эквивалентности множества A по отношению эквивалентности R называется фактор-множеством

Верхняя и нижняя границы и граниПусть - отношение нестрогого порядка на

Верхняя и нижняя границы и граниПример 1. Отношение включения множеств ⊂Пусть

Ограниченные множестваГоворят, что в множестве с заданным на нем отношением порядка

Похожие презентации