рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Замикання відношень

Реферат Курсовая Конспект

Выберите учебное заведение

Замикання відношень

Замикання відношень - раздел Математика, Основи Дискретної математики Рефлексивним Замиканням Бінарного Відношення R,...

Рефлексивним замиканням бінарного відношення R, заданого на множині А (позначається R_r), називається відношення R_r=i_AÈR.

Симетричним замиканням бінарного відношення R, заданого на множині А (позначається R_s), називається відношення R_s=RÈR^-1.

Нехай, наприклад, на множині А={1,2,3,4} задано відношення R={<2,3>,<3,3>, <2,1>,<1,3>}. Рефлексивним замиканням R є відношення R_r={<1,1>,<2,2>,<3,3>, <4,4>,<2,3>,<2,1>,<1,3>}, симетричним замиканням R є відношення R_s={<2,3>, <3,3>,<2,1>,<1,3>,<3,2>,<1,2>, <3,1>}.

Транзитивним замиканням бінарного відношення R, заданого на множині А (позначається R_t або TC(R)), називається відношення R_t=RÈR²È…ÈRⁿÈ…, де Rⁿ=R, якщо n=1, Rⁿ=R^n-1*R, якщо n>1.

Для обчислення транзитивного замикання деякого відношення зручно використовувати таку властивість. Нехай R – бінарне відношення на множині А. Якщо для деякого n (n³1) RÈ…ÈRⁿ = RÈ…ÈRⁿÈRⁿ⁺¹, то R_t=RÈ…ÈRⁿ. Для обгрунтування цього твердження достатньо показати, що для усіх k>n+1 RÈ…ÈRⁿ = RÈ…ÈR^k за умови RÈ…ÈRⁿ = RÈ…ÈRⁿÈRⁿ⁺¹. Очевидно, що RÈ…ÈRⁿ Í RÈ…ÈR^k. Покажемо, що RÈ…ÈR^k Í RÈ…ÈRⁿ. Дійсно, <x,y>ÎRÈ…ÈR^k Þ існує число і (1£і£k) таке, що <x,y>ÎRⁱ. Якщо і£n+1, то <x,y>ÎRÈ…ÈRⁿ. Нехай і>n+1, тоді маємо: <x,y>ÎRⁱ Þ <x,y>ÎRⁿ*Rⁱ^-ⁿ Þ <x,y>ÎRⁿ⁺¹*Rⁱ^-ⁿ^-1 Þ існує zÎА такий, що <x,z>ÎRⁿ⁺¹ та <z,y>ÎRⁱ^-ⁿ^-1 Þ <x,z>ÎRÈ…ÈRⁿ, <z,y>ÎRⁱ^-ⁿ^-1 Þ існує число j<n+1 таке, що <x,z>ÎR^j Þ <x,y>ÎR^j+i-n^-1. Якщо j+i-n-1£n+1, то включення доведено, інакше покладемо і₁=j+i-n-1. Очевидно, що і₁<і. Таким чином, можна побудувати скінченну послідовність чисел і, і₁,…, і_l, де і_l – перше з чисел у послідовності, для якого i_l<n+1, <x,y>ÎR^m, mÎ{і, і₁,…, і_l}. Отже, <x,y>ÎRÈ…ÈRⁿ.

Обчислимо транзитивне замикання R_t відношення R={<2,3>,<3,3>, <2,1>,<1,3>,<3,4>}, заданого на множині А={1,2,3,4}. Маємо: R²={<2,3>,<2,4>, <3,3>,<3,4>,<1,3>,<1,4>}. RÈR²={<2,3>,<3,3>,<2,1>,<1,3>,<3,4>,<2,4>, <1,4>} ¹R, отже, обчислюємо R³=R²*R. Маємо: R³={<2,3>,<2,4>,<3,3>,<3,4>,<1,3>, <1,4>}. Оскільки

RÈR²ÈR³={<2,3>,<3,3>,<2,1>,<1,3>,<3,4>,<2,4>,<1,4>}=RÈR²,

то R_t=RÈR².

З визначення транзитивного замикання відношення випливає, що для будь-якого бінарного відношення R на А xR_ty Û існує така скінченна послідовність x₁,…,x_n елементів множини А, що x₁=x, x_n=y, x_iRx_i+1, iÎ{1,…,n-1}.

Рефлексивно-симетрично-транзитивним замиканням відношення R, заданого на множині А, назвемо відношення R_rst=ТС(і_АÈRÈR^-1).

Теорема 8. Нехай R – деяке бінарне відношення на множині А, R_е – будь-яке відношення еквівалентності на А таке, що RÍR_е, R_rst – рефлексивно-симетрично-транзитивне замикання відношення R. Тоді R_rstÍR_е.

Доведення. Нехай <x,y>ÎR_rst. Тоді <x,y>ÎR або <x,y>ÏR. Якщо <x,y>ÎR, то, оскільки RÍR_е, <x,y>ÎR_е. Якщо <x,y>ÏR, то для деякого і³1 <x,y>Î(і_АÈRÈR^-1)ⁱ. Нехай i=1. Тоді <x,y>Îі_А або <x,y>ÎR^-1. Якщо <x,y>Îі_А, то <x,y>ÎR_е, оскільки R_е рефлексивне. Якщо <x,y>ÎR^-1, то маємо: <x,y>ÎR^-1 Þ <y,x>ÎR Þ <y,x>ÎR_е Þ <x,y>ÎR_е. Нехай і>1 й <x,y>Î(і_АÈRÈR^-1)ⁱ. Це означає, що існують такі елементи х₁,…,х_і₊₁ множини А, що х₁=х, у=х_і₊₁, х₁(і_АÈRÈR^-1)х₂,…,х_і(і_АÈRÈR^-1)х_і₊₁, але тоді х₁R_eх₂,…,х_іR_eх_і₊₁. Оскільки R_e транзитивне, то х₁R_eх_і₊₁, отже, хR_eу.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Основи Дискретної математики

Київський національний університет технологій та дизайну... М К МОРОХОВЕЦЬ...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Замикання відношень

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

КИЇВ КНУТД 2005
УДК 51.681.3517 Конспект лекцій з курсу “Основи дискретної математики” для студентів спеціальності “Комп’ютерні науки” 6.0402 / Автор М.К.Мороховец

Лекція 1. Поняття множини. Операції над множинами
Теорія множин як математична дисципліна створена німецьким мате-матиком Г.Кантором. Згідно з його визначенням, множиною є довільне зі-брання певних об’єктів н

Способи подання множин
Множина може бути задана явно або неявно. Якщо об’єктів, що склада-ють множину, небагато, множина задається явно шляхом перерахування цих об’єктів (а точніше, їх імен). На письмі мн

Включення та рівність множин
Нехай А та В – множини. Будемо говорити, що А включається у В, або А є підмножиною В (й позначати АÍВ), якщо кожен елемент множини

Операції над множинами
Об’єднанням множин А та В (позначається АÈВ) називається множина усіх об’єктів, що є елементами множини А або В, тобто А

Властивості операцій над множинами
Теорема 1. Для будь-яких підмножин А, В, С універсальної множини U наведені нижче рівності є тотожностями (вираз А' слід розуміти як UА

Булеан множини
Кожна непорожня множина Х має принаймні дві різні підмножини: Æ та Х. Крім того, кожен елемент множини Х визначає деяку підмножину множини Х: якщо

Задачі та вправи
І. Описати словами множини: 1) {x| x=2y+1, yÎN}, 2) {x| x=2y-1, yÎN},

Декартів добуток множин
Упорядкованою парою об’єктів х та y (позначається <x,y>) будемо називати сукупність двох об’єктів (не обов’язково різних), які розташовані у

Поняття відношення
Термін «відношення» застосовується у математиці для позначення певного зв’язку між об’єктами. Відношенням R, заданим на множинах А та В, називається довільна підмножина декар

Операції над відношеннями
Нехай R1, R2 – відношення, задані на множинах A1,…,An. Об’єднанням відношень R1 та R2

Види бінарних відношень
Бінарне відношення R на множині А називається симетричним, якщо <x,y>ÎR Þ <y,x>ÎR. Пару

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

Фактор-множина
Нехай R – відношення еквівалентності на А. Тоді, як відомо, існує розбиття множини А, яке визначається відношенням R. Позначимо це розбиття через А

Задачі та вправи
І. Чи існують на множині {1,2,3,4} такі два різні відношення R та S, що: 1) Rr=Sr; 2) Rs=Ss; 3)

Відношення часткового порядку
Бінарне відношення R, задане на множині А, називається відношенням часткового порядку (частковим порядком на А), якщо R рефлексивне, антиси

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

Задачі та вправи
І. Які з відношень завдань XXVIІ-XXІX до попереднього розділу є відношен-нями: 1) часткового порядку, 2) строгого порядку, 3) передпорядку, 4) лінійного порядку, 5) повного порядку.

Поняття відображення
Відношення R, задане на множинах А та В, називається функціональним, якщо для кожного елемента xÎА існує не більше одного елемента

Види відображень
Відображення F множини А у множину В називається відображенням А на В (або сюр’єктивним відображенням, або сюр’єкцією), як

Задачі та вправи
І. Визначити, які з відображень є: а) частковими, б) сюр’єктивними, в) ін’єктивними, г) взаємно однозначними. А={a,b,c,d}, B={b

Рівнопотужні множини
Множини А та В називаються рівнопотужними (еквівалентними), якщо існує взаємно однозначне відображення А на В. Наприклад, множини

Потужність множини
Визначимо відношення ~ на множині усіх множин U: A~В Û А та В рівнопотужні. Дане відношення рефлексивне (А~А), симетричне (якщ

Трансфінітна індукція
Твердження, що стосуються елементів деякої повністю упорядкованої множини, можна доводити, використовуючи метод трансфінітної індукції, який є узагальненням методу математичної інду

Задачі та вправи
І. Навести приклад множини Y, еквівалентної множині X={1,2,3,4,5}. Скільки взаємно однозначних відображень існує між Х та Y? ІІ. Чи рівнопотужні

СПИСОК ВИКОРИСТАНОЇ ТА РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ
1. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976. – 400 с. 2. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программировани

СИМВОЛИ ТА ПОЗНАЧЕННЯ
N – множина усіх невід’ємних цілих чисел N+ – множина усіх додатних цілих чисел Z – м