Ім'я файлу: Сєрий.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 Міністерство_освіти_та_науки_України_PI.docx Контрольна робота Павло Коцаба.docx Метод Баркера.docx Grej_R._S.docx знайомий реферат.docx ОКРО.docx Zvit№1ПСМ.doc §2. Відношення та їх властивості 41 2) Нехай відношення R зображено графом на рис. 20. Відношення R: а) не є рефлексивним, не є антирефлексивним; б) є симетричним; в) не є транзитивним. Рис. 20 3) Нехай Р – множина усіх людей. Визначимо відношення Rтак: “ є братом ”. Окре- мо зауважимо, що не є братом самому собі. У сім’ї з двох братів і та сестри , маємо ситу- ацію, зображену на рис. 21. Рис. 21 Зауважимо, що вказане відношення відображає наступна булева матриця:
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. Далі тобто Включення випливає з того, що ▲ |