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

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

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

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

Поняття відношення

Поняття відношення - раздел Математика, Основи Дискретної математики Термін «Відношення» Застосовується У Математиці Для Позначенн...

Термін «відношення» застосовується у математиці для позначення певного зв’язку між об’єктами. Відношенням R, заданим на множинах А та В, називається довільна підмножина декартова добутка А та В, тобто RÍА´В. Запис xRy означає <x,y>ÎR. Іноді будемо задавати відношення на множинах А та В у вигляді xRy Û Р(х,у), де Р(х,у) – твердження, яке є необхідною й достатньою умовою того, що <x,y>ÎR.

Наприклад, множина R={<1,2>,<1,3>,<3,1>,<3,5>} є відношенням, заданим на множинах А={1,2,3} та В={1,2,3,4,5}, оскільки RÍА´В, а множина С={<1,3>,<4,3>,<1,2>,<2,6>,<3,3>,<1,1>,<1,4>} не є відношенням, заданим на множинах А та В, тому що СËА´В. Прикладом відношення, заданого на множинах N та Z, є множина М={<n,z>| nÎN, zÎZ, n=|z|}, що складається з упорядкованих пар чисел виду <n,n> або <n,-n>, де nÎN. Легко переконатися, що MÍN´Z.

У випадку рівних множин А та В відношення, задане на А та В, називають бінарним відношенням, заданим на множині А (або бінарним відношенням на множині А). Таким чином, бінарне відношення, задане на деякій множині А, – це довільна підмножина множини А².

Прикладом бінарного відношення, заданого на множині N, є множина {<n₁,n₂>| n₁ÎN, n₂ÎN, n₁<n₂}, яка складається з упорядкованих пар невід’ємних цілих чисел таких, що перше число пари менше за друге, тобто дане відношення описує той зв’язок між числами, який ми звикли називати «…менш, ніж…». Іншим прикладом бінарного відношення на множині N є множина {<n,m>| nÎN, mÎN, n та m – парні числа}. Прикладом бінарного відношення, заданого на множині людей, є множина {<l₁,l₂>| l₁,l₂ – люди, l₁ – брат l₂}, яка описує такий тип родинного зв’язку, як «бути братом». Наступний приклад бінарного відношення – відношення включення, задане на булеані деякої множини А. Позначимо це відношення символом Í, тоді Í ={<S,T>| S,TÎP(A), SÍT}. Якщо, наприклад, А={1,2,3,4}, то упорядкована пара множин <{2,4},{1,2,4}> належить відношенню включення, оскільки {2,4}Í{1,2,4}, а упорядкована пара <{1,2},{2,3,4}> – ні, тому що {1,2}Ë{2,3,4}.

Бінарне відношення на множині А виду {<x,x>| xÎA} називається відношенням тотожності на А, або діагоналлю множини А, й позначається i_A. Елементи відношення i_A назвемо діагональними елементами, або діагональними парами.

Прикладом відношення тотожності є відношення {<a,a>,<b,b>, <c,c>,<d,d>}, задане на множині А={a,b,c,d}. Відношення R={<a,a>, <c,c>,<d,d>} не є діагоналлю множини А, оскільки містить не усі пари виду <x,x>, побудовані з елементів множини А (<b,b>ÏR).

Розглянемо узагальнення поняття відношення, заданого на двох множинах. Відношенням R, заданим на множинах А₁,…,А_n, називається довільна підмножина декартова добутка множин А₁,…,А_n, тобто RÍА₁´…´А_n.

Наприклад, множина R={<a,2,f,>,<c,4,t>,<b,2,n>,<c,2,f>} є відношенням, заданим на множинах A={a,b,c}, B={1,2,3,4}, C={f,g,n,m,t}, оскільки, як неважко переконатися, RÍА´В´С. Множина Х={<1,2,3>, <a,b,c>} не є відношенням, заданим на множинах А, В, С, тому що Х не є підмножиною множини А´В´С.

У випадку, коли А₁=…=А_n=А, відношення, задане на множинах А₁,…,А_n, називають n-арним відношенням, заданим на множині А. Зрозуміло, що n-арне відношення, задане на множині А, – це довільна підмножина множини Аⁿ. Для значень n=1 та n=3 (як й для n=2) існують спеціальні назви відповідних відношень. Так, при n=1 відношення називається унарним, або властивістю на множині А; при n=3 відношення називається тернарним

Наприклад, множина S={<n,m,k>| n,m,kÎN, k=n+m} є тернарним відношенням на множині N, оскільки SÍN´N´N (вираз n,m,kÎN використано для скорочення запису й означає nÎN, mÎN, kÎN). Дане відношення складається з тих упорядкованих трійок невід’ємних цілих чисел, у яких число, що є третім компонентом, – це сума чисел, що стоять на першому й другому місцях трійки. Таким чином, трійка <2,5,7> належить S, а трійка <3,4,5> – ні. Множина Р={x| х – людина, x – студент} є унарним відношенням, заданим на множині людей, й задає властивість «бути студентом».

Развернуть

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

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

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

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

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

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

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

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

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

КИЇВ КНУТД 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>) будемо називати сукупність двох об’єктів (не обов’язково різних), які розташовані у

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

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

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

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

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

Задачі та вправи
І. Чи існують на множині {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 – м