Презентация_сем4 (Семинары)

ОТНОШЕНИЯ И СООТВЕТСТВИЯСпециальные свойствабинарных отношений• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если (∀x ∈ A)((x, x) ∈ ρ) ,• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если (∀x ∈ A)((x, x) ∈ ρ) ,т.е. idA ⊆ ρ .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если (∀x ∈ A)((x, x) ∈ ρ) ,т.е.

idA ⊆ ρ .2) иррефлексивным, если (∀x ∈ A)((x, x) ∈/ ρ) ,• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если (∀x ∈ A)((x, x) ∈ ρ) ,т.е. idA ⊆ ρ .2) иррефлексивным, если (∀x ∈ A)((x, x) ∈/ ρ) ,т.е. idA ∩ρ = ∅ .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если (∀x ∈ A)((x, x) ∈ ρ) ,т.е. idA ⊆ ρ .2) иррефлексивным, если (∀x ∈ A)((x, x) ∈/ ρ) ,т.е.

idA ∩ρ = ∅ .3) симметричным, если (∀x∀y)((x, y) ∈ ρ ⇒ (y, x) ∈ ρ) ,• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если (∀x ∈ A)((x, x) ∈ ρ) ,т.е. idA ⊆ ρ .2) иррефлексивным, если (∀x ∈ A)((x, x) ∈/ ρ) ,т.е. idA ∩ρ = ∅ .3) симметричным, если (∀x∀y)((x, y) ∈ ρ ⇒ (y, x) ∈ ρ) ,т.е. ρ−1 = ρ .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если (∀x ∈ A)((x, x) ∈ ρ) ,т.е. idA ⊆ ρ .2) иррефлексивным, если (∀x ∈ A)((x, x) ∈/ ρ) ,т.е. idA ∩ρ = ∅ .3) симметричным, если (∀x∀y)((x, y) ∈ ρ ⇒ (y, x) ∈ ρ) ,т.е. ρ−1 = ρ .4) антисимметричным, если(∀x∀y)(((x, y) ∈ ρ ∧ (y, x) ∈ ρ) ⇒ (x = y))• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если (∀x ∈ A)((x, x) ∈ ρ) ,т.е.

idA ⊆ ρ .2) иррефлексивным, если (∀x ∈ A)((x, x) ∈/ ρ) ,т.е. idA ∩ρ = ∅ .3) симметричным, если (∀x∀y)((x, y) ∈ ρ ⇒ (y, x) ∈ ρ) ,т.е. ρ−1 = ρ .4) антисимметричным, если(∀x∀y)(((x, y) ∈ ρ ∧ (y, x) ∈ ρ) ⇒ (x = y))т.е. ρ ∩ ρ−1 ⊆ idA• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если (∀x ∈ A)((x, x) ∈ ρ) ,т.е.

idA ⊆ ρ .2) иррефлексивным, если (∀x ∈ A)((x, x) ∈/ ρ) ,т.е. idA ∩ρ = ∅ .3) симметричным, если (∀x∀y)((x, y) ∈ ρ ⇒ (y, x) ∈ ρ) ,т.е. ρ−1 = ρ .4) антисимметричным, если(∀x∀y)(((x, y) ∈ ρ ∧ (y, x) ∈ ρ) ⇒ (x = y))т.е. ρ ∩ ρ−1 ⊆ idA (в частности, м. б., что ρ ∩ ρ−1 = ∅ !).• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если (∀x ∈ A)((x, x) ∈ ρ) ,т.е. idA ⊆ ρ .2) иррефлексивным, если (∀x ∈ A)((x, x) ∈/ ρ) ,т.е. idA ∩ρ = ∅ .3) симметричным, если (∀x∀y)((x, y) ∈ ρ ⇒ (y, x) ∈ ρ) ,т.е.

ρ−1 = ρ .4) антисимметричным, если(∀x∀y)(((x, y) ∈ ρ ∧ (y, x) ∈ ρ) ⇒ (x = y))т.е. ρ ∩ ρ−1 ⊆ idA (в частности, м. б., что ρ ∩ ρ−1 = ∅ !).Эквивалентное определение:(∀x∀y)(((x, y) ∈ ρ ∧ x 6= y) ⇒ ((y, x)) ∈/ ρ).• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если (∀x ∈ A)((x, x) ∈ ρ) ,т.е. idA ⊆ ρ .2) иррефлексивным, если (∀x ∈ A)((x, x) ∈/ ρ) ,т.е. idA ∩ρ = ∅ .3) симметричным, если (∀x∀y)((x, y) ∈ ρ ⇒ (y, x) ∈ ρ) ,т.е. ρ−1 = ρ .4) антисимметричным, если(∀x∀y)(((x, y) ∈ ρ ∧ (y, x) ∈ ρ) ⇒ (x = y))т.е.

ρ ∩ ρ−1 ⊆ idA (в частности, м. б., что ρ ∩ ρ−1 = ∅ !).Эквивалентное определение:(∀x∀y)(((x, y) ∈ ρ ∧ x 6= y) ⇒ ((y, x)) ∈/ ρ).• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit5) транзитивным, если(∀x∀y∀z)(((x, y) ∈ ρ ∧ (y, z) ∈ ρ) ⇒ ((x, z) ∈ ρ)),• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit5) транзитивным, если(∀x∀y∀z)(((x, y) ∈ ρ ∧ (y, z) ∈ ρ) ⇒ ((x, z) ∈ ρ)),т.е. ρ ◦ ρ ⊆ ρ .• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit5) транзитивным, если(∀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) ∈ ρ)).• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение называется:1) эквивалентностью, если оно рефлексивно, симметрично итранзитивно;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение называется:1) эквивалентностью, если оно рефлексивно, симметрично итранзитивно;2) толерантностью, если оно рефлексивно и симметрично;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение называется:1) эквивалентностью, если оно рефлексивно, симметрично итранзитивно;2) толерантностью, если оно рефлексивно и симметрично;3) порядком (или частичным порядком), если оно рефлексивно,антисимметрично и транзитивно;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение называется:1) эквивалентностью, если оно рефлексивно, симметрично итранзитивно;2) толерантностью, если оно рефлексивно и симметрично;3) порядком (или частичным порядком), если оно рефлексивно,антисимметрично и транзитивно;4) предпорядком (или квазипорядком), если оно рефлексивно итранзитивно;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение называется:1) эквивалентностью, если оно рефлексивно, симметрично итранзитивно;2) толерантностью, если оно рефлексивно и симметрично;3) порядком (или частичным порядком), если оно рефлексивно,антисимметрично и транзитивно;4) предпорядком (или квазипорядком), если оно рефлексивно итранзитивно;5) строгим порядком, если оно иррефлексивно, антисимметрично итранзитивно;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение называется:1) эквивалентностью, если оно рефлексивно, симметрично итранзитивно;2) толерантностью, если оно рефлексивно и симметрично;3) порядком (или частичным порядком), если оно рефлексивно,антисимметрично и транзитивно;4) предпорядком (или квазипорядком), если оно рефлексивно итранзитивно;5) строгим порядком, если оно иррефлексивно, антисимметрично итранзитивно;6) строгим предпорядком, если оно иррефлексивно и транзитивно;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение называется:1) эквивалентностью, если оно рефлексивно, симметрично итранзитивно;2) толерантностью, если оно рефлексивно и симметрично;3) порядком (или частичным порядком), если оно рефлексивно,антисимметрично и транзитивно;4) предпорядком (или квазипорядком), если оно рефлексивно итранзитивно;5) строгим порядком, если оно иррефлексивно, антисимметрично итранзитивно;6) строгим предпорядком, если оно иррефлексивно и транзитивно;Говорят: отношение эквивалентности, толерантности, порядка, предпорядка .

.”. “ и т.п.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 1.Рассмотрим отношение ρ на множестве всех подмножеств некоторогомножества U : A ρ B ⇔ A ∩ B 6= ∅ и ∅ ρ ∅.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 1.Рассмотрим отношение ρ на множестве всех подмножеств некоторогомножества U : A ρ B ⇔ A ∩ B 6= ∅ и ∅ ρ ∅.Покажем, что это отношение толерантности, т.е. рефлексивно исимметрично.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 1.Рассмотрим отношение ρ на множестве всех подмножеств некоторогомножества U : A ρ B ⇔ A ∩ B 6= ∅ и ∅ ρ ∅.Покажем, что это отношение толерантности, т.е.

рефлексивно исимметрично.Поскольку для любого множества A ∈ U, A 6= ∅, A ∩ A = A 6= ∅ и∅ ρ ∅, отношение ρ является рефлексивным.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 1.Рассмотрим отношение ρ на множестве всех подмножеств некоторогомножества U : A ρ B ⇔ A ∩ B 6= ∅ и ∅ ρ ∅.Покажем, что это отношение толерантности, т.е.

рефлексивно исимметрично.Поскольку для любого множества A ∈ U, A 6= ∅, A ∩ A = A 6= ∅ и∅ ρ ∅, отношение ρ является рефлексивным.Поскольку из A ∩ B 6= ∅ следует, что B ∩ A 6= ∅, отношение ρявляется симметричным.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 1.Рассмотрим отношение ρ на множестве всех подмножеств некоторогомножества U : A ρ B ⇔ A ∩ B 6= ∅ и ∅ ρ ∅.Покажем, что это отношение толерантности, т.е. рефлексивно исимметрично.Поскольку для любого множества A ∈ U, A 6= ∅, A ∩ A = A 6= ∅ и∅ ρ ∅, отношение ρ является рефлексивным.Поскольку из A ∩ B 6= ∅ следует, что B ∩ A 6= ∅, отношение ρявляется симметричным.Вывод: это отношение толерантности.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 1.Рассмотрим отношение ρ на множестве всех подмножеств некоторогомножества U : A ρ B ⇔ A ∩ B 6= ∅ и ∅ ρ ∅.Покажем, что это отношение толерантности, т.е.

рефлексивно исимметрично.Поскольку для любого множества A ∈ U, A 6= ∅, A ∩ A = A 6= ∅ и∅ ρ ∅, отношение ρ является рефлексивным.Поскольку из A ∩ B 6= ∅ следует, что B ∩ A 6= ∅, отношение ρявляется симметричным.Вывод: это отношение толерантности.Покажем, что ρ — не эквивалентность.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 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= ∅, что легко видеть что, отношение ρ не транзитивно.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 2.Зададим на множестве натуральных чисел N следующее отношение:a | b в том и только том случае, когда a является делителем b “.”• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 2.Зададим на множестве натуральных чисел N следующее отношение:a | b в том и только том случае, когда a является делителем b “.”Это отношение рефлексивно, поскольку любое число является делителемсамого себя.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 2.Зададим на множестве натуральных чисел N следующее отношение:a | b в том и только том случае, когда a является делителем b “.”Это отношение рефлексивно, поскольку любое число является делителемсамого себя.Покажем антисимметричнсть.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 2.Зададим на множестве натуральных чисел N следующее отношение:a | b в том и только том случае, когда a является делителем b “.”Это отношение рефлексивно, поскольку любое число является делителемсамого себя.Покажем антисимметричнсть.Пусть a делит b и, с другой стороны, bделит a .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 2.Зададим на множестве натуральных чисел N следующее отношение:a | b в том и только том случае, когда a является делителем b “.”Это отношение рефлексивно, поскольку любое число является делителемсамого себя.Покажем антисимметричнсть.Пусть a делит b и, с другой стороны, bделит a .Тогда найдется натуральное число t1 , такое, что b = at1 ,• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 2.Зададим на множестве натуральных чисел N следующее отношение:a | b в том и только том случае, когда a является делителем b “.”Это отношение рефлексивно, поскольку любое число является делителемсамого себя.Покажем антисимметричнсть.Пусть a делит b и, с другой стороны, bделит a .Тогда найдется натуральное число t1 , такое, что b = at1 ,инайдется t2 , такое, что a = bt2 .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 2.Зададим на множестве натуральных чисел N следующее отношение:a | b в том и только том случае, когда a является делителем b “.”Это отношение рефлексивно, поскольку любое число является делителемсамого себя.Покажем антисимметричнсть.Пусть a делит b и, с другой стороны, bделит a .Тогда найдется натуральное число t1 , такое, что b = at1 ,инайдется t2 , такое, что a = bt2 .Отсюда b = bt2t1 , что на множественатуральных чисел возможно только при t1 = t2 = 1 .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 2.Зададим на множестве натуральных чисел N следующее отношение:a | b в том и только том случае, когда a является делителем b “.”Это отношение рефлексивно, поскольку любое число является делителемсамого себя.Покажем антисимметричнсть.Пусть a делит b и, с другой стороны, bделит a .Тогда найдется натуральное число t1 , такое, что b = at1 ,инайдется t2 , такое, что a = bt2 .Отсюда b = bt2t1 , что на множественатуральных чисел возможно только при t1 = t2 = 1 .Следовательно,a = b.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 2.Зададим на множестве натуральных чисел N следующее отношение:a | b в том и только том случае, когда a является делителем b “.”Это отношение рефлексивно, поскольку любое число является делителемсамого себя.Покажем антисимметричнсть.Пусть a делит b и, с другой стороны, bделит a .Тогда найдется натуральное число t1 , такое, что b = at1 ,инайдется t2 , такое, что a = bt2 .Отсюда b = bt2t1 , что на множественатуральных чисел возможно только при t1 = t2 = 1 .Следовательно,a = b.Покажем транзитивность.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 2.Зададим на множестве натуральных чисел N следующее отношение:a | b в том и только том случае, когда a является делителем b “.”Это отношение рефлексивно, поскольку любое число является делителемсамого себя.Покажем антисимметричнсть.Пусть a делит b и, с другой стороны, bделит a .Тогда найдется натуральное число t1 , такое, что b = at1 ,инайдется t2 , такое, что a = bt2 .Отсюда b = bt2t1 , что на множественатуральных чисел возможно только при t1 = t2 = 1 .Следовательно,a = b.Покажем транзитивность.Если a делит b , а b делит c , то найдутсятакие натуральные числа t1 , t2 , такие, что b = at1 и c = bt2 .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 2.Зададим на множестве натуральных чисел N следующее отношение:a | b в том и только том случае, когда a является делителем b “.”Это отношение рефлексивно, поскольку любое число является делителемсамого себя.Покажем антисимметричнсть.Пусть a делит b и, с другой стороны, bделит a .Тогда найдется натуральное число t1 , такое, что b = at1 ,инайдется t2 , такое, что a = bt2 .Отсюда b = bt2t1 , что на множественатуральных чисел возможно только при t1 = t2 = 1 .Следовательно,a = b.Покажем транзитивность.Если a делит b , а b делит c , то найдутсятакие натуральные числа t1 , t2 , такие, что b = at1 и c = bt2 .