Презентация семинар 3 (1076834), страница 2

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

Текст из файла (страница 2)

Операции над соответствиямиПоскольку соответствия являются множествами, то все операции надмножествами (пересечение, объединение, разность, дополнение и т.д.)применимы и к соответствиям. Однако для соответствий можно определить специальные операции: композицию соответствий и получениеобратного соответствия.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) ρ ◦ (σ ◦ τ ) = (ρ ◦ σ) ◦ τ ;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitКомпозицию отношения с самим собой называют квадратом отношения.Определение 3.4.

Отношение idA = {(x, x) | ∈ A} называютдиагональю множества A .Свойства композиции:(1) ρ ◦ (σ ◦ τ ) = (ρ ◦ σ) ◦ τ ;(2) ρ ◦ ∅ = ∅ ◦ ρ = ∅;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitКомпозицию отношения с самим собой называют квадратом отношения.Определение 3.4. Отношение idA = {(x, x) | ∈ A} называютдиагональю множества A .Свойства композиции:(1) ρ ◦ (σ ◦ τ ) = (ρ ◦ σ) ◦ τ ;(2) ρ ◦ ∅ = ∅ ◦ ρ = ∅;(3) ρ ◦ (σ ∪ τ ) = ρ ◦ σ ∪ ρ ◦ τ ;• 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Композицию отношения с самим собой называют квадратом отношения.Определение 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).включений.Используем метод двух• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitРассмотрим доказательство свойства (1).включений.Используем метод двухПервое включение.(x, z) ∈ρ ◦ (σ ◦ τ ) ⇒• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitРассмотрим доказательство свойства (1).включений.Используем метод двухПервое включение.(x, z) ∈ρ ◦ (σ ◦ τ ) ⇒ (∃y)(((x, y) ∈ ρ) ∧ ((y, z) ∈ σ ◦ τ )) ⇒• 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) ∈ τ ))) ⇒• 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) ∈ τ )) ⇒• 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) ∈ τ )) ⇒• 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) ∈(ρ ◦ σ) ◦ τ ⇒• 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) ∈ τ )) ⇒• 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) ∈ τ )) ⇒• 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) ∈ τ ))) ⇒• 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) ∈ σ ◦ τ )) ⇒• 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) Обратное соответствие• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit2) Обратное соответствие.Соответствие, обратное соответствию ρ ⊆ A1 × A2 , есть соответствиеиз A2 в A1 , обозначаемое ρ−1 и равное по определениюρ−1 = {(y, x) | (x, y) ∈ ρ}.• 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)}.• 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)}.Обратное соответствие обладает следующими свойствами:• 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 = ρ• 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• 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.

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

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