Презентация Теорія відношень онлайн

Содержание слайда: Розділ 2. Теорія відношень

Содержание слайда: 2.3. Властивості бінарних відношень рефлексивність антирефлексивність симетричність асиметричність антисиметричність транзитивність антитранзитивність замикання відношень

Содержание слайда: Рефлексивність Відношення R на множині X називається рефлексивним, якщо для будь-якого хX має місце xRx.

Содержание слайда: Антирефлексивність Відношення R на множині X називається антирефлексивним, якщо з x1R x2 виходить, що x1 x2.

Содержание слайда: Симетричність Відношення R на множині X називається симетричним, якщо для пари (x1, х2)X2 з x1 R x2 виходить x2 R x1.

Содержание слайда: Асиметричність Відношення R на множині X називається асиметричним, якщо для пари (x1, х2)X2 із x1 R x2 виходить, що не виконується x2 R x1 .

Содержание слайда: Антисиметричність Відношення R на множині X називається антисиметричним, якщо з x1 R x2 і x2 R x1 виходить, що x1= x2.

Содержание слайда: Транзитивність Відношення R на множині X називається транзитивним, якщо з x1 R x2 і x2 R x3 виходить x1 R x3 .

Содержание слайда: Антитранзитивність Відношення R на множині X називається антитранзитивним, якщо з x1 R x2 і x2 R x3 виходить, що не виконується x1 R x3.

Содержание слайда: Приклад перевірки на транзитивність та антитранзитивність a3 R a1 і a1 R a4  a3 R a4 відсутня

Содержание слайда: Замикання Рефлексивним замиканням RE відношення R називається відношення RE=RE, де E – відношення тотожності на X (діагональ).

Содержание слайда: Симетричним замиканням RS відношення R називається відношення RS=RR-1, тобто якщо (x1, х2)R, то (x1, х2)RS i (x2, х1)RS. Симетричним замиканням RS відношення R називається відношення RS=RR-1, тобто якщо (x1, х2)R, то (x1, х2)RS i (x2, х1)RS.

Содержание слайда: Транзитивним замиканням Rt відношення R називається відношення Rt=RR1…Rn… Транзитивним замиканням Rt відношення R називається відношення Rt=RR1…Rn…

Содержание слайда: Алгоритм Уоршалла Алгоритм Уоршалла побудови транзитивного замикання для відношення R. Нехай відношення задано у вигляді матриці. Присвоювання початкових значень W = R, k = 0. Виконати k = k + 1. Для всіх i  k таких, що wk = 1, і для всіх j виконати операцію wij = wij  wkj. Якщо k = n, то отримано розв’язок.

Содержание слайда: Приклад. Використаня алгоритму Уоршалла для побудови транзитивного замикання. Приклад. Використаня алгоритму Уоршалла для побудови транзитивного замикання. Нехай A={1, 2, 3, 4}, R  AА

Содержание слайда: W(2)=W(1) бо другий стовпчик нульовий W(2)=W(1) бо другий стовпчик нульовий

Содержание слайда: 2.4. Відношення еквівалентності, толерантності, порядку відношення еквівалентності класи еквівалентності відношення толерантності строгий порядок частковий (нестрогий) порядок лінійний порядок порівнянні і непорівнянні елементи структура впорядкованих множин

Содержание слайда: Відношення еквівалентності Бінарне відношення, що має властивості рефлексивності, симетричності і транзитивності, називається відношенням еквівалентності (позначається ~). Нехай задана множина А і відношення еквівалентності, що визначене на цій множині: RАА. Елементи a, b  А, для яких виконується aRb, називаються еквівалентними. Будь-яке відношення еквівалентності R, визначене на множині А, розбиває множину А на неперетинні підмножини, які називаються класами еквівалентності.

Содержание слайда: Розбиття скінченної множини А на класи еквівалентності за відношенням R. Розбиття скінченної множини А на класи еквівалентності за відношенням R. Виберемо елемент а1А і утворимо клас С1 що складається з усіх елементів уА, для яких виконується відношення a1R y. (Клас С1 може складатися тільки з одного елемента а1, якщо не існує інших елементів у, таких, що a1Ry - через рефлексивність відношення еквівалентності завжди виконується a1R a1.) Якщо С1А, то виберемо з А елемент а2, що не входить до класу С1, і утворимо клас С2, який складається з елементів уА: a2R y. Якщо (С1C2)А, то виберемо з А елемент а3, що не входить до класів С1 і С2, і утворимо клас С3. Будемо продовжувати побудову класів доти, доки в А не залишиться жодного елемента, що не входить до одного з класів Сi.

Содержание слайда: Система класів С1, С2, … ,Сn називається системою класів еквівалентності і має такі властивості: Система класів С1, С2, … ,Сn називається системою класів еквівалентності і має такі властивості: 1. класи попарно не перетинаються  i, j: СiСj=  2. будь-які два елементи з одного класу еквівалентні  a, bСi : (a, b)  R 3. будь-які два елементи з різних класів не еквівалентні  a Сi, bСj : (a, b)  R

Содержание слайда: Приклад. Приклад. Нехай A={2, 4, 6, 8, 12, 15}, R1  AА R1 – мати однакову кількість цифр Розбиття на класи еквівалентності за R1: {{2, 4, 6, 8}, {12, 15}}

Содержание слайда: Приклад. Приклад. Нехай A={2, 4, 6, 8, 12, 15}, R2  AА R2 = {(2,2),(2,6),(4,4),(4,8),(4,12),(6,2),(6,6), (8,4),(8,8),(8,12),(12,4),(12,12), (15,15)} Розбиття на класи еквівалентності за R2: {{2, 6},{4, 8, 12},{15}}

Содержание слайда: Бінарне відношення, що має властивості рефлексивності, симетричності і антитранзитивності, називається відношенням толерантності. Бінарне відношення, що має властивості рефлексивності, симетричності і антитранзитивності, називається відношенням толерантності. Толерантність зображує собою формальне уявлення інтуїтивного поняття схожості. Приклад. Муха-мура-тура-тара-кара-каре-кафе-кафр-каюр-каюк-крюк-крок-срок-сток-стон-слон

Содержание слайда: Відношення порядку Бінарне відношення, що має властивості антирефлексивності (якщо а<b, то аb), асиметричності (якщо а<b, то не правильне b<а) і транзитивності (якщо а<b і b<с, то а<с) , називається відношенням строгого порядку (позначається <). Приклад. A – множина студентів групи, R  AА, R – бути старшим.

Содержание слайда: Бінарне відношення, що має властивості рефлексивності, антисиметричності і транзитивності, називається відношенням нестрогого (часткового) порядку (позначається ). Бінарне відношення, що має властивості рефлексивності, антисиметричності і транзитивності, називається відношенням нестрогого (часткового) порядку (позначається ). Якщо на множині задане відношення часткового порядку, то ця множина називається частково упорядкованою. Приклад. Нехай A ={a, b, c}, R – відношення включення, задане на булеані 2A.

Содержание слайда: Зображення відношення часткового порядку

Содержание слайда: діаграма Хассе

Содержание слайда: Шлях у графі відношення з вершини а до вершини b — це послідовність дуг (а, х1), (х1, х2), (х2, х3),..., (хn-1, b), n1. Число дуг n називається довжиною шляху. Шлях у графі відношення з вершини а до вершини b — це послідовність дуг (а, х1), (х1, х2), (х2, х3),..., (хn-1, b), n1. Число дуг n називається довжиною шляху. Елементи а і b називаються порівнянними у відношенні часткового порядку R, якщо виконується хоча б одне із співвідношень aRb або bRa. Множина А, на якій задане відношення часткового порядку R і для якої всілякі два елементи цієї множини порівнянні, називається лінійно упорядкованою або повністю упорядкованою.

Содержание слайда: Структура впорядкованих множин A={2, 4, 6, 8, 12, 24}, В={ 4, 8, 12}, В  A R  AА, R – бути дільником R = (2,2),(2,4),(2,6),(2,8), (2,12), (2,24),(4,4),(4,8),(4,12), (4,24),(6,6),(6,12),(6,24),(8,8), (8,24),(12,12),(12,24),(24,24)}

Содержание слайда: Мажорантою (найбільшим елементом, верхньою гранню) підмножини В називають такий елемент mА, що для будь-якого елемента bB справджується відношення bRm. Мажорантою (найбільшим елементом, верхньою гранню) підмножини В називають такий елемент mА, що для будь-якого елемента bB справджується відношення bRm. Підмножина В  А може мати кілька мажорант. Сукупність мажорант називають верхнім конусом підмножини В і позначають В.

Содержание слайда: Якщо верхній конус підмножини В має мінімальний елемент, то він називається точною верхньою гранню В і позначається sup В. Якщо верхній конус підмножини В має мінімальний елемент, то він називається точною верхньою гранню В і позначається sup В. Якщо точна верхня грань sup В  В, то її називають максимальним елементом В (позначають max(В)). Якщо максимальний елемент існує, то він єдиний.

Содержание слайда: Мінорантою (найменшим елементом, нижньою гранню) підмножини В називають такий елемент nА, що для будь-якого елемента bB справджується відношення nRb. Мінорантою (найменшим елементом, нижньою гранню) підмножини В називають такий елемент nА, що для будь-якого елемента bB справджується відношення nRb. Підмножина В  А може мати кілька мінорант. Сукупність мінорант називають нижнім конусом підмножини В і позначають В.

Содержание слайда: Якщо нижній конус підмножини В має максимальний елемент, то він називається точною нижньою гранню В і позначається inf В. Якщо нижній конус підмножини В має максимальний елемент, то він називається точною нижньою гранню В і позначається inf В. Якщо точна нижня грань inf В  В, то її називають мінімальним елементом В (позначають min(В)). Якщо мінімальний елемент існує, то він єдиний.

Содержание слайда: 2.5. Функціональні відношення функціональне відношення області визначення і значень відображення (функція) сюр'єкція, ін'єкція, бієкція

Содержание слайда: Відношення R між множинами X і Y (RXY) є функціональним, якщо всі його елементи (упорядковані пари) різні за першим елементом: кожному хX або відповідає тільки один елемент уY, такий, що xRy, або такого елемента у взагалі не існує. Відношення R між множинами X і Y (RXY) є функціональним, якщо всі його елементи (упорядковані пари) різні за першим елементом: кожному хX або відповідає тільки один елемент уY, такий, що xRy, або такого елемента у взагалі не існує.

Содержание слайда: Нехай R — деяке відношення, RXY. Нехай R — деяке відношення, RXY. Областю визначення відношення R називається множина DR (DomR), що складається з усіх елементів множини X, які зв'язані відношенням R з елементами множини Y: DR  X, DR = {х: уY, (х, у)R}. Якщо DR = X, то відношення R називається повністю визначеним. Областю значень відношення R називається множина R(ImR), що складається з усіх елементів множини Y, які зв'язані відношенням R з елементами множини X: R  Y, R = {у: хX, (х, у)R}.

Содержание слайда: Відображення (функція) Функцією f або відображенням f множини X в Y (позначається f: X  Y) називається повністю визначене функціональне відношення F, FXY, DF = X (DFDf). Якщо множина АX, то через f(A) = {уY: у = f(х), xА) позначається образ множини А. Якщо множина ВY, то множина f-1(B) = {хX: f(x)В} називається прообразом множини В відносно відображення f.

Содержание слайда: Види відображень Функція f: XY називається сюр'єктивним відображенням, якщо f = Y. На графі, що зображує сюр'єктивне відображення XY, з будь-якої вершини хX виходить точно одна дуга, а до будь-якої вершини, що зображує елемент множини Y, заходить не менше однієї дуги. В матриці відображення у кожному рядку точно одна одиниця, а в кожному стовпчику – не менше однієї одиниці.

Содержание слайда: Функція f: XY називається ін'єктивним відображенням, якщо з x1x2 виходить f(x1)f(x2). Функція f: XY називається ін'єктивним відображенням, якщо з x1x2 виходить f(x1)f(x2). На графі, що зображує ін'єктивне відображення XY, з будь-якої вершини хX виходить точно одна дуга, а до будь-якої вершини, що зображує елемент множини Y, заходить не більше однієї дуги. В матриці відображення у кожному рядку точно одна одиниця, а в кожному стовпчику – не більше однієї одиниці.

Содержание слайда: Якщо f: XY — ін'єктивне відображення і F={(х,f(х)), хX} — відповідне функціональне відношення (FXY), то обернене відношення Якщо f: XY — ін'єктивне відображення і F={(х,f(х)), хX} — відповідне функціональне відношення (FXY), то обернене відношення F-1={(у,х), yf} також є функціональним. Функція х = f-1(y), f-1: f X, що задається відношенням F-1, має властивості: f-1(f(x)) = x, хX; f-1(f(y)) = y, yf і називається оберненою до функції f.

Содержание слайда: Функція f: XY називається бієктивним відображенням, якщо вона сюр'єктивна та ін'єктивна. Функція f: XY називається бієктивним відображенням, якщо вона сюр'єктивна та ін'єктивна. На графі, що зображує бієктивне відображення XY, з будь-якої вершини хX виходить точно одна дуга, а до будь-якої вершини, що зображує елемент множини Y, заходить точно одна дуга. В матриці відображення у кожному рядку точно одна одиниця, а в кожному стовпчику – теж точно одна одиниця.