Ім'я файлу: Сєрий.docx
Розширення: docx
Розмір: 67кб.
Дата: 25.11.2021
скачати
Пов'язані файли:
5.docx
Лаба 4_РТП_СЗІ_Кліщ Богдан.docx
Лаба 5_РТП_СЗІ_Кліщ.docx
Тести, статистика праці.docx
Реферат Лесько П.В. Авторське право ЕЛЕП-11.docx.doc
Індивідуальна нормативне.docx
lab2.docx
ЦЕРКВА РІЗДВА ПРЕСВЯТОЇ БОГОРОДИЦІ У САМБОРІ.docx
ШАБЕЛЬКО КУРСОВА.docx
Розраха.docx
Сучасні методики здорового харчування.docx
Звіт до БД 2.docx
звіт_від_ред.docx
lab_8_Kravets.docx
Сенсорне виховання.doc
СПЗ_ЛАБ_1.docx
lab5_бд.docx
Фізика5 Моя лаба.doc
Вебинар англ.docx
5.docx
ЛР 3 ФДП.docx
Методичка до ПЗ №5-6.doc
зразок РГР 2021 (1).docx
курсова 1.docx


§2. Відношення та їх властивості 41

2) Нехай відношення R зображено графом на рис. 20.

Відношення R:

а) не є рефлексивним, не є антирефлексивним;

б) є симетричним;

в) не є транзитивним.



Рис. 20

3) Нехай Р – множина усіх людей. Визначимо відношення Rтак: “ є братом ”. Окре-

мо зауважимо, що не є братом самому собі. У сім’ї з двох братів і та сестри , маємо ситу- ацію, зображену на рис. 21.



Рис. 21

Зауважимо, що вказане відношення відображає наступна булева матриця:
p q r

p

q

r
0 1 1

1 0 1

0 0 0




42 Розділ 1. МНОЖИНИ ТА ВІДНОШЕННЯ
Легко бачити, що відношення R– антирефлек-сивне, несиметричне ( , але ), не є анти-симетричним ( , але ), не є тран-зитивним.

Надалі вважаємо, що - антирефлексивне відношення.

Доведемо необхідні умови рефлективності та симетричності відношень.

Теорема 1.

Відношення R - рефлексивне тоді та лише тоді, коли відношення , де , є антирефлексив- ним.

Доведення.

▼ Якщо то і, отже, є антирефлексивним відношенням.

Нехай тепер тоді Якщо (а;а) то (а;а) . Але це суперечить рефлексивності відношення R. Тому (а;а) для всіх , а це й означає, що – антиреф- лексивне відношення.

Навпаки, нехай - антирефлексивне відношення. Припус- тимо, (а;а) Тоді (а;а) а це суперечить тому, що відношення R – рефлексивне відношення. ▲

Теорема 2.

R – симетричне відношення тоді та лише тоді, коли – симетричне відношення.

Доведення.

Необхідність ( ).

▼Нехай відношення R симетричне і (а;b) тоді (а;b) Оскільки R– симетричне, то (b;а) тобто (b;а) Отже, відношення є симетричним. Необхідність доведена.

Достатність ( ).

Якщо відношення – симетричне, то за доведеним відно- шення є також симетричним. Але ж (див. властивості операцій над відношеннями), тому Rє відношенням. Достат- ність доведена. ▲
§2. Відношення та їх властивості 43
2.6. Відношення еквівалентності

Означення. Відношення Rна множині А називається відношенням еквівалентності, якщо воно рефлексивне, си- метричне та транзитивне.

Приклади. 1) (), (), ( ), ( ), І, U– відношення еквіва- лентності;

2) Нехай де – фіксоване число. Маємо:

а) тобто R – рефлексивне відношення;

б)

, тобто R – симетричне відношення; в) Оскільки то тобто R– транзитивне відношення.

Розглянуте в останнььому прикладі відношення еквівалент- ності називають відношенням конгруентності чисел за модулем m і замість aRb записують:

Означення. Нехай – відношення еквіва- лентності, Переріз відношення R за елементом а називається класом еквівалентності за відношенням R і позначається [a].

Отже, Якщо то bназивається представником класу еквівалентності [a], зокрема

Приклади. 1) Нехай A = Z, R – відношення екві- валентності, що задається наступним чином: (перевірити самостій- но). Які класи еквівалентності породжує таке відношення еквівалентності?

Легко бачити, що такими класами еквіва- лентності є якщо і

44 Розділ 1. МНОЖИНИ ТА ВІДНОШЕННЯ

2) Які класи еквівалентності породжуються в множині Z відношенням конгруентності за мо- дулем 4?

Клас еквівалентності елемента 0 містить всі числа bтакі, що тоб- то всі цілі числа, що діляться націло на 4: Клас еквівалентнос- ті, породжений елементом 1, містить всі цілі числа bтакі, що тобто такі цілі числа, остача від ділення яких на 4 дорівнює 1. Отже, Аналогічно

Очевидно, що [4] = [0], [5] = [1] і т. д. Не- важко помітити, що довільні два класи екві- валентності або не мають спільних елементів ( і т. д.), або збіга- ються ( і т. д.).

Отже, відношення конгруентності за модулем 4 розбиває множину Z на 4 класи еквівалент- ності:



3) Розглянемо множину Парі (a;b) з ці- єї множини співставимо дріб . Оскільки серед дробів існують скоротні дроби, то різні пари з можуть визначати рівні дроби. Визначи- мо відношення еквівалентності на насту- пним чином: Множи- ну всіх класів еквівалентності, що визначають- ся цим відношенням на називають ра- ціональними числами і позначають такими представниками класів еквівалентності, у яких найменші знаменники b.

§2. Відношення та їх властивості 45

Теорема 3.

Довільні класи еквівалентності за відношенням R або не мають спільних елементів, або збігаються.

Доведення.

▼Нехай [a], [b] – два довільні фіксовані класи еквівалентнос- ті за відношенням R. Припустимо, [a] [b] Покажемо, що в цьому випадку [a] = [b].

Оскільки Якщо x – довільний елемент з [a], то . Але відношення R– транзитивне та симетричне, тому з того, що (R - симетричне), випливає, що тобто . Отже, Аналогічно, можна довести, що Тому ▲

Означення. Розбиттям множини А називається така система множин що:







Теорема 4.

Довільне відношення еквівалентності, задане на мно- жині А, породжує розбиття цієї множини на класи еквівалентності.

Доведення.

▼ Нехай {[a]|a } – сукупність різних класів еквівалент- ності. Враховуючи теорему 3, треба показати, що



Дійсно, якщо то при деякому маємо (наприклад, ). Тому xналежить до одного з класів екві- валентності за відношенням R. Далі тобто Включення випливає з того, що ▲
скачати

© Усі права захищені
написати до нас