Теорія відношень - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Теорія відношень. Доклад-сообщение содержит 41 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Розділ 2. Теорія відношень

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

Симетричним замиканням 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.

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

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

Слайд 20

Описание слайда:

Система класів С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

Слайд 21

Описание слайда:

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

Слайд 22

Описание слайда:

Приклад. Приклад. Нехай 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}}

Слайд 23

Описание слайда:

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

Слайд 24

Описание слайда:

Відношення порядку Бінарне відношення, що має властивості антирефлексивності (якщо а

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

діаграма Хассе

Слайд 28

Описание слайда:

Шлях у графі відношення з вершини а до вершини 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 і для якої всілякі два елементи цієї множини порівнянні, називається лінійно упорядкованою або повністю упорядкованою.

Слайд 29

Описание слайда:

Структура впорядкованих множин 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)}

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

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

Слайд 33

Описание слайда:

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

Слайд 34

Описание слайда:

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

Слайд 35

Описание слайда:

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

Слайд 36

Описание слайда:

Нехай 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}.

Слайд 37

Описание слайда:

Відображення (функція) Функцією 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.

Слайд 38

Описание слайда:

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

Слайд 39

Описание слайда:

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

Слайд 40

Описание слайда:

Якщо 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.

Слайд 41

Описание слайда:

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

Теги Теор дношень

Похожие презентации