PP_s3 (Семинары)

ОТНОШЕНИЯ И СООТВЕТСТВИЯ• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit1. Основные определенияОпределение 3.1. n -арным (или n -местным ) отношениемна множествах A1, . . . , An называется произвольное подмножество ρдекартова произведения A1 × . . . × An :ρ ⊆ A 1 × . . . × An .В частности, при ρ = ∅ получаем пустое отношение, а приρ , совпадающем со всем указанным декартовым произведением —универсальное отношение.Важный частный случай получаем при n = 2 : тогда говорят осоответствии из множества A1 в множество A2 .Если A1 = A2 = .

. . = An = A , то ρ называют n -арнымотношением на множестве A ; при n = 2 получаем бинарноеотношение на множестве A .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitРассмотрим более подробно соответствия и бинарные отношения.Любое соответствие — это множество упорядоченных пар. Например,если A = R1 (множество действительных чисел), то бинарное отношение на R1 — это некоторое множество точек плоскости R2 .Определение 3.2.

Область определения соответствия измножества A1 в множество A2 ρ ⊆ A1 × A2 — есть множествоD(ρ) = {x |(∃y ∈ A2)(x, y) ∈ ρ}.Область значения соответствия ρ — это множествоR(ρ) = {y |(∃x ∈ A1)(x, y) ∈ ρ}.Из определения вытекает, что D(ρ) ⊆ A1 , R(rho) ⊆ A2 .Соответствие называют всюду определенным, если D(ρ) = A1 .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОпределение 3.3. Сечением соответствия ρ для фиксированногоx ∈ A1 называют множествоρ(x) = {y | (x, y) ∈ ρ}.Пример 1.Пусть ρ = {(x, y) | x > y + 1} ⊆ {1, 2, 3, 4}2 .Имеем ρ = {(3, 1), (4, 1), (4, 2)} .Область определения отношения D(ρ) = {3, 4} ,область значений — R(ρ) = {1, 2} .Задание.

Построить график и граф отношения ρ.• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit3.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 = {л, о, с, т} ,а Φ = {(о, л), (с, л), (т, л), (с, о), (т, о), (с, т)} .• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit2.

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

Соответствие ρ берем из предыдущего примера, асоответствие σ ⊆ {1, 2, 3, 4}2 зададим непосредственно как множествопар σ = {(1, 2), (1, 3), (3, 4)} .Задание. Построить граф композиции ρ ◦ σ.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitКомпозицию отношения с самим собой называют квадратом отношения.Определение 3.4.

Отношение idA = {(x, x) | ∈ A} называютдиагональю множества A .Свойства композиции:(1) ρ ◦ (σ ◦ τ ) = (ρ ◦ σ) ◦ τ ;(2) ρ ◦ ∅ = ∅ ◦ ρ = ∅;(3) ρ ◦ (σ ∪ τ ) = ρ ◦ σ ∪ ρ ◦ τ ;(4) ρ ◦ (σ ∩ τ ) ⊆ ρ ◦ σ ∩ ρ ◦ τ ;(равенство в общем случае не имеет места!).(5) ρ ◦ idA = idA ◦ρ = ρ , где ρ ⊆ A2 — бинарное отношение на A .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitРассмотрим доказательство свойства (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) ∈ (ρ ◦ σ) ◦ τ.Второе включение.(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) ∈ ρ ◦ (σ ◦ τ ).• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit2) Обратное соответствие.Соответствие, обратное соответствию ρ ⊆ A1 × A2 , есть соответствиеиз A2 в A1 , обозначаемое ρ−1 и равное по определениюρ−1 = {(y, x) | (x, y) ∈ ρ}.Для соответствия ρ = {(3, 1), (4, 1), (4, 2)}ρ−1 = {(1, 3), (1, 4), (2, 4)}.Обратное соответствие обладает следующими свойствами:(6) (ρ−1)−1 = ρ(7) (ρ ◦ σ)−1 = σ −1 ◦ ρ−1Для фиксированного y ∈ A2 положим ρ−1(y) = {x | y ∈ ρ(x)} .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадачи3.1.

Найти D(ρ) , R(ρ) , ρ−1 , ρ ◦ ρ , ρ−1 ◦ ρ , ρ ◦ ρ−1 для отношения:ρ = {(x, y) | x, y ∈ [0, 1], 2x ≥ 3y}.3.2. Доказать, что для любых бинарных отношений ρ1 , ρ2 , ρ3 ∈ A×A :(а) ρ1 ∩ ρ1 = ρ1 ∪ ρ1 = ρ1 ;(б) ρ1 ◦ (ρ2 ◦ ρ3) = (ρ1 ◦ ρ2) ◦ ρ3 ;(в) ρ1 ◦ idA = idA ◦ ρ1 = ρ1 .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitДомашнее задание3.1. Найти D(ρ) , R(ρ) , ρ−1 , ρ ◦ ρ , ρ−1 ◦ ρ , ρ ◦ ρ−1 для отношений:(а) ρ = {(x, y) | x, y ∈ N, x = 0 (mod y)};(б) ρ = {(x, y) | x, y ∈ [0, 1], x + y ≤ 1}.3.2.

Доказать, что для любого бинарного отношения ρ ⊆ A × A :(а) D(ρ−1) = R(ρ) ;(б) R(ρ−1) = D(ρ) ;(в) D(ρ1 ◦ ρ2) = ρ−11 (R(ρ1 ) ∩ D (ρ2 )) ;(г) R(ρ1 ◦ ρ2) = ρ2(R(ρ1) ∩ D(ρ2))(д) (ρ)−1 = (ρ−1) .3.3. Доказать, что для любых бинарных отношений ρ1 , ρ2 ∈ A × A :−1(а) (ρ1 ∩ ρ2)−1 = ρ−11 ∩ ρ2 ;−1(б) (ρ1 ∪ ρ2)−1 = ρ−11 ∪ ρ2 ;−1(в) (ρ1 ◦ ρ2)−1 = ρ−12 ◦ ρ1 .• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit.