Печать семинар 3 (1076830)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Семинар 3.3.1. Бинарные отношенияОпределение 3.1. n -арным (или n -местным ) отношением на множествахA1 , . . . , An называется произвольное подмножество ρ декартова произведения A1 × . . . ×An :ρ ⊆ A1 × . . . × An .В частности, при ρ = ∅ получаем пустое отношение, а при ρ , совпадающем совсем указанным декартовым произведением — универсальное отношение.Важный частный случай получаем при n = 2 : тогда говорят о соответствии измножества A1 в множество A2 .Если A1 = A2 = . . . = An = A , то ρ называют n -арным отношением намножестве A ; при n = 2 получаем бинарное отношение на множестве A .Рассмотрим более подробно соответствия и бинарные отношения.

Любое соответствие— это множество упорядоченных пар. Например, если A = R1 (множество действительных чисел), то бинарное отношение на R1 — это некоторое множество точек плоскостиR2 .Определение 3.2. Область определения соответствия из множества A1 вмножество A2 ρ ⊆ A1 × A2 — есть множествоdom ρ = {x |(∃y ∈ A2 )(x, y) ∈ ρ}.Область значения соответствия ρ — это множествоrng ρ = {y |(∃x ∈ A1 )(x, y) ∈ ρ}.Из определения вытекает, что dom ρ ⊆ A1 , rng ρ ⊆ A2 . Соответствие называютвсюду определенным, если dom ρ = A1 .Определение 3.3.

Сечением соответствия ρ для фиксированного x ∈ A1 называютмножествоρ(x) = {y | (x, y) ∈ ρ}.Пример 3.1.Пусть ρ = {(x, y) | x > y + 1} ⊆ {1, 2, 3, 4}2 . Имеем ρ = {(3, 1), (4, 1), (4, 2)} .Область определения отношения dom ρ = {3, 4} , область значений — rng ρ = {1, 2} .Построить график и граф отношения ρ.3.1. Построить графики и графы следующих бинарных отношений, заданных намножестве X = {1, 2, 3, 4, 5, 6} :(а) x1 ϕx2 , если x1 < x2 ;(б) x1 τ x2 , если x1 ≤ x2 ;(в) x1 ρx2 , если (x1 − x2 ) ≥ 2 ;(г) {(a, b)| a + b — четное} ;3.2.

Определить, по какому принципу построено отношение, заданное графиком Φ наM × M , где M = {л, о, с, т} ,а Φ = {(о, л), (с, л), (т, л), (с, о), (т, о), (с, т)} .1СЕМИНАР 3.23.2. Операции над соответствиямиПоскольку соответствия являются множествами, то все операции над множествами(пересечение, объединение, разность, дополнение и т.д.) применимы и к соответствиям.Однако для соответствий можно определить специальные операции: композицию соответствий и получение обратного соответствия.1) Композиция соответствий.Если ρ ⊆ A1 × A2 , σ ⊆ A2 × A3 , то композиция (произведение) соответствий ρ и σесть соответствие ρ ◦ σ , определяемое какρ ◦ σ = {(x, z) | (∃y)((x, y) ∈ ρ)∧∧ ((y, z) ∈ σ)}.Пример 3.2.

Соответствие ρ берем из предыдущего примера, а соответствиеσ ⊆ {1, 2, 3, 4}2 зададим непосредственно как множество пар σ = {(1, 2), (1, 3), (3, 4)} .Построить граф композиции ρ ◦ σ.Композицию отношения с самим собой называют квадратом отношения.Определение 3.4. Отношение idA = {(x, x) | ∈ A} называют диагональюмножества A .Свойства композиции:(1) ρ ◦ (σ ◦ τ ) = (ρ ◦ σ) ◦ τ ;(2) ρ ◦ ∅ = ∅ ◦ ρ = ∅;(3) ρ ◦ (σ ∪ τ ) = ρ ◦ σ ∪ ρ ◦ τ ;(4) ρ ◦ (σ ∩ τ ) ⊆ ρ ◦ σ ∩ ρ ◦ τ ; (равенство в общем случае не имеет места!).(5) ρ ◦ idA = idA ◦ρ = ρ , где ρ ⊆ A2 — бинарное отношение на A .Рассмотрим доказательство свойства (1). Используем метод двух включений:(x, z) ∈ ρ ◦ (σ ◦ τ ) ⇒⇒ (∃y)(((x, y) ∈ ρ)∧∧ ((y, z) ∈ σ ◦ τ )) ⇒⇒ (∃y)(∃t)(((x, y) ∈ ρ) ∧ (((y, t) ∈ σ)∧∧ ((t, z) ∈ τ ))) ⇒⇒ (∃y)(∃t)((((x, y) ∈ ρ) ∧ ((y, t) ∈ σ))∧∧ ((t, z) ∈ τ )) ⇒⇒ (∃t)(((x, t) ∈ ρ ◦ σ) ∧ ((t, z) ∈ τ )) ⇒⇒ (x, z) ∈ (ρ ◦ σ) ◦ τ.СЕМИНАР 3.3Обратно:(x, z) ∈ (ρ ◦ σ) ◦ τ ⇒⇒ (∃t)(((x, t) ∈ ρ ◦ σ)∧∧ ((t, z) ∈ τ )) ⇒⇒ (∃y)(∃t)((((x, y) ∈ ρ)∧∧ ((y, t) ∈ σ))∧∧ ((t, z) ∈ τ )) ⇒⇒ (∃y)(∃t)(((x, y) ∈ ρ)∧∧ (((y, t) ∈ σ)∧∧ ((t, z) ∈ τ ))) ⇒⇒ (∃y)(((x, y) ∈ ρ) ∧ ((y, z) ∈ σ ◦ τ )) ⇒⇒ (x, z) ∈ ρ ◦ (σ ◦ τ ).2) Обратное соответствие.Соответствие, обратное соответствию ρ ⊆ A1 × A2 , есть соответствие из A2 в A1 ,обозначаемое ρ−1 и равное по определениюρ−1 = {(y, x) | (x, y) ∈ ρ}.Для соответствия ρ из примера ??ρ−1 = {(1, 3), (1, 4), (2, 4)}.Обратное соответствие обладает следующими свойствами:(6) (ρ−1 )−1 = ρ(7) (ρ ◦ σ)−1 = σ −1 ◦ ρ−1Для фиксированного y ∈ A2 положим ρ−1 (y) = {x | y ∈ ρ(x)} .СЕМИНАР 3.Задачи3.1.

Найти domρ , rngρ , ρ−1 , ρ ◦ ρ , ρ−1 ◦ ρ , ρ ◦ ρ−1 для отношений:(а) ρ = {(x, y) | x, y ∈ N, x = 0 (mod y)};(б) ρ = {(x, y) | x, y ∈ [0, 1], x + y ≤ 1}(в) ρ = {(x, y) | x, y ∈ [0, 1], 2x ≥ 3y}.3.2. Доказать, что для любого бинарного отношения ρ ⊆ A × A :(а) domρ−1 = rngρ ;(б) rngρ−1 = domρ ;(в) domρ1 ◦ρ2 = ρ−11 (rngρ1 ∩ domρ2 ) ;(г) rngρ1 ◦ρ2 = ρ2 (rngρ1 ∩ domρ2 ) .3.3. Доказать, что для любых бинарных отношений ρ1 , ρ2 , ρ3 ∈ A × A :(а) ρ1 ∩ ρ1 = ρ1 ∪ ρ1 = ρ1 ;(б) ρ1 ◦ (ρ2 ◦ ρ3 ) = (ρ1 ◦ ρ2 ) ◦ ρ3 ;(в) ρ1 ◦ idA = idA ◦ ρ1 = ρ1 ;−1(г) (ρ1 ∩ ρ2 )−1 = ρ−11 ∩ ρ2 ;−1(д) (ρ1 ∪ ρ2 )−1 = ρ−11 ∪ ρ2 ;(е) (ρ)−1 = (ρ−1 ) ;−1(ж) (ρ1 ◦ ρ2 )−1 = ρ−12 ◦ ρ1 .4.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов семинаров