Печать семинар 3 (Семинары)
Описание файла
Файл "Печать семинар 3" внутри архива находится в следующих папках: Семинары, Семинар 3. PDF-файл из архива "Семинары", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 3 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "дискретная математика" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Семинар 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.