PR_SEM4 (1076837)

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

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

Семинар 4.Специальные свойства бинарных отношенийОпределение 4.1. Бинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если idA ⊆ ρ , т.е.(∀x ∈ A)((x, x) ∈ ρ);2) иррефлексивным, если idA ∩ρ = ∅ , т.е.(∀x ∈ A)((x, x) ∈/ ρ);3) симметричным, если ρ−1 = ρ , т.е.(∀x∀y)((x, y) ∈ ρ ⇒ (y, x) ∈ ρ);4) антисимметричным, еслиρ ∩ ρ−1 ⊆ idA , т.е.(∀x∀y)(((x, y) ∈ ρ ∧ (y, x) ∈ ρ) ⇒⇒ (x = y))(в частности, м. б., что ρ ∩ ρ−1 = ∅ !);Эквивалентное определение:(∀x∀y)(((x, y) ∈ ρ ∧ x 6= y) ⇒⇒ ((y, x)) ∈/ ρ).5) транзитивным, если ρ ◦ ρ ⊆ ρ , т.е.(∀x∀y∀z)(((x, y) ∈ ρ ∧ (y, z) ∈ ρ) ⇒⇒ ((x, z) ∈ ρ));6) плотным, если(∀x∀y)(((x, y) ∈ ρ ⇒ (∃z)((z 6= x)∧∧ (z 6= y) ∧ ((x, z) ∈ ρ) ∧ ((z, y) ∈ ρ)).Определение 4.2. Бинарное отношение называется:1) эквивалентностью, если оно рефлексивно, симметрично и транзитивно;2) толерантностью, если оно рефлексивно и симметрично,3) порядком (или частичным порядком), если оно рефлексивно, антисимметричнои транзитивно;4) предпорядком (или квазипорядком), если оно рефлексивно и транзитивно;5) строгим порядком, если оно иррефлексивно, антисимметрично и транзитивно;6) строгим предпорядком, если оно иррефлексивно и транзитивно;Можно говорить: отношение эквивалентности, толерантности, порядка, предпорядка”.

. . “ и т.п.1СЕМИНАР 4.2Пример 4.1.а) Рассмотрим отношение ρ на множестве всех подмножеств некоторого множестваU : A ρ B ⇔ A ∩ B 6= ∅ и ∅ ρ ∅. Покажем, что это отношение толерантности:Поскольку для любого множества A ∈ U, A 6= ∅, A∩A = A 6= ∅ и ∅ ρ ∅, отношениеρ является рефлексивным.Поскольку из A ∩ B 6= ∅ следует, что B ∩ A 6= ∅, отношение ρ являетсясимметричным.Вывод: это отношение толерантности.Покажем, что ρ — не эквивалентность.Поскольку из A ∩ B 6= ∅ и B ∩ C 6= ∅ , никак не следует, что A ∩ C 6= ∅, что легковидеть из диаграммы, отношение ρ не транзитивно.б) Зададим на множестве натуральных чисел N следующее отношение: a | b = a”делит (является делителем) b “.Это отношение рефлексивно, поскольку любое число является делителем самого себя.Покажем антисимметричнсть.Пусть a делит b и, с другой стороны, b делит a .

Тогда найдется натуральное числоt1 , такое, что b = at1 , и найдется t2 , такое, что a = bt2 . Отсюда b = bt2 t1 , что намножестве натуральных чисел возможно только при t1 = t2 = 1 . Следовательно, a = b .Покажем транзитивность.Если a делит b , а b делит c , то найдутся такие натуральные числа t1 , t2 , такие,что b = at1 и c = bt2 . Отсюда имеем c = at1 t2 , т.е. a — делитель c .Таким образом, отношение делимости на множестве N является отношением порядка.Если распространить это отношение на множество целых чисел, то оно будет ужетолько предпорядком, поскольку не будет антисимметричным.

Например, 2 делится на−2 , и −2 делится на 2 , однако 2 6= −2 .в) Рассмотрим множество всех подмножеств множества A — B(A) . Покажем, чтоотношение включения ⊆ на множестве B(A) есть порядок.Это отношение рефлексивно, т.к. для любого множества X справедливо X ⊆ X .Поскольку для любых двух множеств X и Y из (X ⊆ Y ) и (Y ⊆ X) следует, чтоX = Y , рассматриваемое отношение антисимметрично.Из определения включения вытекает, что если (X ⊆ Y ) и (Y ⊆ Z) , то X ⊆ Z .Следовательно, отношение транзитивно.4.1. Исследовать свойства (рефлексивность, иррефлексивность, симметричность, антисимметричность, транзитивность) следующих отношений:(а) M = {a, b, c, d} ,Φ = {(a, a), (a, b), (c, a),(b, d), (a, d), (b, c)};(б) m ρ k , если m − k делится на n , где m ∈ Z , k ∈ Z , n ∈ Z ;(в) x ϕ y, если (x − y) ≤ 2 , x ∈ R , y ∈ R .4.2.

Пусть X = {x | x ∈ [0, 1]} , ρ = {(x, y) | x, y ∈ X, x < y и |x − y| < 0.5} . Построитьграфики отношений ρ и ρ−1 . Исследовать свойства отношения ρ . Что можно сказать освойствах обратного отношения?4.3. Отношение σ связывает клетки шахматной доски: две клетки связаны, если содной на другую можно перейти ходом коня.

Записать отношение с помощью логическихвысказываний, исследовать его свойства.4.4. Пусть τ и π — отношения на N × N : (a, b) τ (c, d) , если a ≤ c и b ≤ d ;(a, b) π (c, d) , если a ≤ c и b ≥ d . Являются ли τ и π отношениями порядка и почему?4.5. Пусть υ определено на множестве положительных рациональных чисел:(a/b)υ(с/d) , если ad ≤ bc . Показать, что υ является отношением линейного порядка.4.6. Пусть A — произвольное множество и ρ , σ — отношения на множестве 2A × 2A( прямом произведении множества всех подмножеств A на себя).(а) (P, Q)σ(X, Y ) , если (P ⊆ X) и (Q ⊆ Y ) ;(б) (P, Q)ρ(X, Y ) , если (P 4Q) ⊆ (X4Y ) ;СЕМИНАР 4.3Являются ли ρ и σ отношениями порядка?4.7.

Рассмотрим множество квадратных матриц размером 2 × 2 , элементами которыхявляются целые числа. Является ли заданное ниже отношение τ отношением порядка?Линейного порядка?(а) Aτ B , если aij ≤ bij , i, j = 1, 2 ;(б) Aτ B , если aij ≤ bij , i, j = 1, 2 и хотя бы для одной пары элементов неравенствострогое.4.8. Пусть F — множество функций, непрерывных на [a, b] . Исследовать свойстваотношения τ :Z bZ b(а) f (x)τ g(x) , еслиf (x) dx =g(x) dx .

Является ли τ отношением эквивалентности?aZaZb(б) f (x)τ g(x) , еслиbf (x) dx ≤ag(x) dx .Является ли τ отношением порядка?a4.9. Пусть M —некоторое множество, а 2M \{∅} — множество всех его подмножествбез пустого множества. Два множества из 2M связаны отношением τ , если они имеютхотя бы одно непустое общее подмножество. Является ли в общем случае τ отношениемпорядка. Какими свойствами будет обладать отношение τ , если M = {a, b}.

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

Тип файла PDF

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

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

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