Печать презентации сем4 (1076840)
Текст из файла
ОТНОШЕНИЯ И СООТВЕТСТВИЯСпециальные свойствабинарных отношений• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если (∀x ∈ A)((x, x) ∈ ρ) ,т.е. idA ⊆ ρ .2) иррефлексивным, если (∀x ∈ A)((x, x) ∈/ ρ) ,т.е. idA ∩ρ = ∅ .3) симметричным, если (∀x∀y)((x, y) ∈ ρ ⇒ (y, x) ∈ ρ) ,т.е. ρ−1 = ρ .4) антисимметричным, если(∀x∀y)(((x, y) ∈ ρ ∧ (y, x) ∈ ρ) ⇒ (x = y))т.е. ρ ∩ ρ−1 ⊆ idA (в частности, м.
б., что ρ ∩ ρ−1 = ∅ !).Эквивалентное определение:(∀x∀y)(((x, y) ∈ ρ ∧ x 6= y) ⇒ ((y, x)) ∈/ ρ).• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit5) транзитивным, если(∀x∀y∀z)(((x, y) ∈ ρ ∧ (y, z) ∈ ρ) ⇒ ((x, z) ∈ ρ)),т.е. ρ ◦ ρ ⊆ ρ .6) плотным, если(∀x∀y)(((x, y) ∈ ρ ⇒ (∃z)((z 6= x) ∧ (z 6= y) ∧ ((x, z) ∈ ρ) ∧ ((z, y) ∈ ρ)).• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение называется:1) эквивалентностью, если оно рефлексивно, симметрично итранзитивно;2) толерантностью, если оно рефлексивно и симметрично;3) порядком (или частичным порядком), если оно рефлексивно,антисимметрично и транзитивно;4) предпорядком (или квазипорядком), если оно рефлексивно итранзитивно;5) строгим порядком, если оно иррефлексивно, антисимметрично итранзитивно;6) строгим предпорядком, если оно иррефлексивно и транзитивно;Говорят: отношение эквивалентности, толерантности, порядка, предпорядка . .”.
“ и т.п.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 1.Рассмотрим отношение ρ на множестве всех подмножеств некоторогомножества U : A ρ B ⇔ A ∩ B 6= ∅ и ∅ ρ ∅.Покажем, что это отношение толерантности, т.е. рефлексивно исимметрично.Поскольку для любого множества A ∈ U, A 6= ∅, A ∩ A = A 6= ∅ и∅ ρ ∅, отношение ρ является рефлексивным.Поскольку из A ∩ B 6= ∅ следует, что B ∩ A 6= ∅, отношение ρявляется симметричным.Вывод: это отношение толерантности.Покажем, что ρ — не эквивалентность.Поскольку из A ∩ B 6= ∅ и B ∩ C 6= ∅ в общем случае не следует, чтоA ∩ C 6= ∅, что легко видеть что, отношение ρ не транзитивно.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 2.Зададим на множестве натуральных чисел N следующее отношение:a | b в том и только том случае, когда a является делителем b “.”Это отношение рефлексивно, поскольку любое число является делителемсамого себя.Покажем антисимметричнсть.Пусть a делит b и, с другой стороны, bделит a .Тогда найдется натуральное число t1 , такое, что b = at1 ,инайдется t2 , такое, что a = bt2 .Отсюда b = bt2t1 , что на множественатуральных чисел возможно только при t1 = t2 = 1 .Следовательно,a = b.Покажем транзитивность.Если a делит b , а b делит c , то найдутсятакие натуральные числа t1 , t2 , такие, что b = at1 и c = bt2 .
Отсюдаимеем c = at1t2 , т.е. a — делитель c .Таким образом, отношение делимости на множестве N является отношением порядка.Это отношение на множество целых чисел Z будет только предпорядком, поскольку не будет антисимметричным.Например, 2 делится на −2 , и −2 делится на 2 , однако 2 6= −2 .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 3.Рассмотрим множество всех подмножеств множества A — 2(A) . Покажем, что отношение включения ⊆ на множестве 2(A) есть порядок.Это отношение рефлексивно, т.к.
для любого множества X справедливоX⊆X.Поскольку для любых двух множеств X и Y из (X ⊆ Y ) и (Y ⊆ X)следует, что X = Y , рассматриваемое отношение антисимметрично.Из определения включения вытекает, что если (X ⊆ Y ) и (Y ⊆ Z) ,то X ⊆ Z . Следовательно, отношение транзитивно.Таким образом, отношение рефлексивно, антисимметрично и транзитивно, т. е. это отношение порядка.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадачи.4.1 Исследовать свойства (рефлексивность, иррефлексивность, симметричность, антисимметричность, транзитивность) следующих отношений:(а) M = {a, b, c, d} ,Φ = {(a, a), (a, b), (c, a), (b, d), (a, d), (b, c)};(б) x ϕ y, если (x − y) ≤ 2 , x ∈ R , y ∈ R .4.2 Пусть X = {x | x ∈ [0, 1]} , ρ = {(x, y) | x, y ∈ X, x < y и |x − y| <0.5} .
Построить графики отношений ρ и ρ−1 . Исследовать свойстваотношения ρ . Что можно сказать о свойствах обратного отношения?4.3 Пусть τ — отношение на N × N : (a, b) τ (c, d) , если a ≤ c иb ≤ d . Является ли τ отношением порядка и почему?4.4 Пусть υ определено на множестве положительных рациональныхчисел: (a/b)υ(с/d) , если ad ≤ bc . Показать, что υ являетсяотношением линейного порядка.• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit4.5 Пусть A — произвольное множество и σ — отношение намножестве 2A ×2A ( прямом произведении множества всех подмножествA на себя):(P, Q)σ(X, Y ), если(P ⊆ X) и (Q ⊆ Y );Является ли σ отношением порядка?4.6 Рассмотрим множество квадратных матриц размером 2 × 2 ,элементами которых являются целые числа.
Является ли заданное нижеотношение τ отношением порядка? Линейного порядка?(а) Aτ B , если aij ≤ bij , i, j = 1, 2 ;(б) Aτ B , если aij ≤ bij , i, j = 1, 2 и хотя бы для одной пары элементовнеравенство строгое.4.7 Пусть F — множество функций, непрерывных на [a, b] . Исследовать свойства отношенияτ: Z bZ bf (x) dx ≤f (x)τ g(x) , еслиaнием предпорядка? порядка?g(x) dx .Является ли τ отноше-a• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОтношение эквивалентности.Определение 4.1. Бинарное отношение называется: эквивалентностью, если оно рефлексивно, симметрично и транзитивно.Определение 4.2.
Пусть ρ ⊆ A2 — экивалентность. Множество[x]ρ = {y | yρx}называют классом эквивалентности элемента x по отношению ρ .Определение 4.3. Множество всех классов эквивалентности поданному отношению эквивалентности ρ на множестве A называетсяфактор-множеством множества A по отношению ρ и обозначаетсяA/ρ , т.е.A/ρ = {[x]ρ | x ∈ A}.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 4.
На множестве целых чисел Z определим отношениеm ≡(mod 2) n ( m равно n по модулю 2 “ ) имеющее место тогда итолько тогда,”когда m − n делится на 2 : 2 | m − n .Это отношение рефлексивно и симметрично, поскольку m − m = 0делится на 2, и из того, что m − n делится на 2, вытекает, что n − mделится на 2.Покажем транзитивность. Пусть m ≡(mod 2) n и n ≡(mod 2) p.
Если m−nделится на 2 и n−p делится на 2, то числа m, n и p либо все четные,либо нечетные.Поэтому m−p делится на 2, что означает m ≡(mod 2) p.Таким образом, ≡(mod 2) — транзитивность.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitНайдем фактор-множество множества целых чисел Z по данномуотношению эквивалентности.Рассмотрим множество чисел, связанных отношением ≡(mod 2) с числом0. Разность некоторого числа n и 0 будет нацело делиться на 2 толькоесли число n — четное. Таким образом, [0]≡(mod 2) — множество четныхчисел.Рассмотрим множество чисел, связанных отношением ≡(mod 2) с числом1. Разность некоторого числа m и 1 будет нацело делиться на 2 толькоесли число m — нечетное.
Таким образом, [1]≡(mod 2) — множествонечетных чисел.В итоге получаем ровно 2 попарно различных классов эквивалентностипо данному отношению: [0]≡(mod 2) и [1]≡(mod 2) .Можем записатьZ/ ≡(mod 2) ∼ {0, 1}.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 4.8 На множестве рациональных дробей вида a/b , a ∈ Z ,b ∈ N задано бинарное отношениеτ = {(a/b, c/d) | ad = cb}.Показать, что τ является отношением эквивалентности. Что является фактор-множеством множества рациональных дробей по данномуотношению?Задача 4.9 Пусть в R3 задана плоскость ax + by + cz = 0 .Точки с радиус-векторами r1 и r2 связаны отношением τ , если((r1 − r2), n) = 0 , где n — нормаль к плоскости, а (·, ·) — скалярноепроизведение.
Показать, что τ — отношение эквивалентности. Накакие классы эквивалентности разбивается R3 . Что будет фактормножеством множества R3 по данному отношению эквивалентности.Задача 4.10 Пусть F — множество функций, непрерывных на [a, b] .Исследовать свойстваZ отношенияZ τ:bf (x)τ g(x) , еслиbf (x) dx =aем эквивалентности?g(x) dx .
Является ли τ отношениa• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitИндексированное семейство множеств {Bi}i∈I называется разбиением [множества A , если:1)Bi = A ,i∈I2) если i 6= j , то Bi ∩ Bj = ∅ .Таким образом, разбиение множества A — это семейство попарно непересекающихся подмножеств A , объединение которых равно A .Например, множества [0, 1/3) , [1/3, 2/3) и [2/3, 1] образуют разбиениеотрезка [0, 1] .Теорема. Любое отношение эквивалентности определяет однозначно некоторое разбиение данного множества и обратно, любое разбиениемножества однозначно определяет некоторое отношение эквивалентности на нем.Задача 4.11 Пусть A — конечное множество.
Какое отношение эквивалентности на нем дает наибольшее число классов эквивалентности.Сколько? Сколькими способами можно задать отношение эквивалентности, разбивающее A на два класса?• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitДомашнее задание4.12 Отношение σ связывает клетки шахматной доски: две клеткисвязаны, если с одной на другую можно перейти ходом коня. Записатьотношение с помощью логических высказываний, исследовать его свойства.4.13 Пусть π — отношение на N × N : (a, b) π (c, d) , если a ≤ c иb ≥ d .
Является ли π отношением порядка и почему?4.14 Пусть A — произвольное множество и ρ — отношение намножестве 2A ×2A ( прямом произведении множества всех подмножествA на себя).(P, Q)ρ(X, Y ) , если (P 4Q) ⊆ (X4Y ) ;Является ли ρ отношением порядка?4.15 Пусть M —некоторое множество, а 2M \ {∅} — множествовсех его подмножеств без пустого множества. Два множества из 2Mсвязаны отношением τ , если они имеют хотя бы одно непустое общееподмножество. Является ли в общем случае τ отношением порядка.Какими свойствами будет обладать отношение τ , если M = {a, b}• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit4.16 Пусть f : R → R — отображение, и x1 τ x2 если и только еслиf (x1) = f (x2) .
Показать, что τ является отношением эквивалентности.Указать фактор-множество R/τ .• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
