Презентация семинар 3 (Семинары)
Описание файла
Файл "Презентация семинар 3" внутри архива находится в следующих папках: Семинары, Семинар 3. PDF-файл из архива "Семинары", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 3 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "дискретная математика" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
ОТНОШЕНИЯ И СООТВЕТСТВИЯ• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit1. Основные определенияОпределение 3.1. n -арным (или n -местным ) отношениемна множествах A1, . . . , An называется произвольное подмножество ρдекартова произведения A1 × . .
. × An :ρ ⊆ A 1 × . . . × An .• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit1. Основные определенияОпределение 3.1. n -арным (или n -местным ) отношениемна множествах A1, . . . , An называется произвольное подмножество ρдекартова произведения A1 × . . . × An :ρ ⊆ A 1 × . . . × An .В частности, при ρ = ∅ получаем пустое отношение, а приρ , совпадающем со всем указанным декартовым произведением —универсальное отношение.• 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 .• 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Рассмотрим более подробно соответствия и бинарные отношения.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitРассмотрим более подробно соответствия и бинарные отношения.Любое соответствие — это множество упорядоченных пар.
Например,если A = R1 (множество действительных чисел), то бинарное отношение на R1 — это некоторое множество точек плоскости R2 .• 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) ∈ ρ}.• 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) ∈ ρ}.• 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 .• 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 .• 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)} .• 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} ,• 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 • 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} :• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit3.1. Построить графики и графы следующих бинарных отношений,заданных на множестве X = {1, 2, 3, 4, 5, 6} :(а) x1 ϕ x2, если x1 < x2 ;• 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 ;• 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 ;• 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 — четное} ;• 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. Операции над соответствиямиПоскольку соответствия являются множествами, то все операции надмножествами (пересечение, объединение, разность, дополнение и т.д.)применимы и к соответствиям. Однако для соответствий можно определить специальные операции: композицию соответствий и получениеобратного соответствия.• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit2.
Операции над соответствиямиПоскольку соответствия являются множествами, то все операции надмножествами (пересечение, объединение, разность, дополнение и т.д.)применимы и к соответствиям. Однако для соответствий можно определить специальные операции: композицию соответствий и получениеобратного соответствия.1) Композиция соответствий.• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit2. Операции над соответствиямиПоскольку соответствия являются множествами, то все операции надмножествами (пересечение, объединение, разность, дополнение и т.д.)применимы и к соответствиям. Однако для соответствий можно определить специальные операции: композицию соответствий и получениеобратного соответствия.1) Композиция соответствий.Если ρ ⊆ A1 × A2 , σ ⊆ A2 × A3 , то композиция (произведение)соответствий ρ и σ есть соответствие ρ ◦ σ , определяемое какρ ◦ σ = {(x, z) | (∃y)((x, y) ∈ ρ) ∧ ((y, z) ∈ σ)}.• 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 • Quit2.