Релации - основни понятия и дефиниции

📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆ 📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆

Математика › Дискретна математика › Релации

Релации
Определения, представяне и композиция

5 определения, 6 примера — конструктивно и дескриптивно задаване, домен, обратна релация, таблично представяне, операции с релации и композиция

Дискретна математика Релации Бинарна релация Домен Композиция Д-р Атанас Илчев

От понятието за \(n\)-местна релация и методите за нейното задаване до операциите с релации и тяхната композиция

Определения и задаване на релации

Определение 1: Нека \(n\) е естествено число и \(M_1, M_2,\ldots, M_n\) е фамилия от множества. Всяко подмножество \(R\subseteq M_1\times M_2\times\ldots\times M_n\) се нарича \(n\)-местна релация, а множествата \(M_1, M_2,\ldots, M_n\) се наричат съответно 1-ви, 2-ри, …, \(n\)-ти домен на тази релация. При \(n=2\) получената релация се нарича двуместна или бинарна релация. Ако \((m,n)\in R\), за бинарна релация, ще използваме инфиксния запис \(mRn\).

Ако елементите на едно множество \(M\) са в релация с елементите на множество \(N\), естествено се поражда \(M\times N\), което определя дадената релация.

Съществуват два начина за задаване на релации — конструктивно (чрез явно изброяване на наредените двойки) и дескриптивно (чрез описание на свойство).

Пример 1: Нека \(M=\{10,20,30,40\}\) и \(N=\{4,5\}\). Разглеждаме:
\(R_1=\{(m,n)\mid m\in M,\; n\in N,\; m\text{ се дели на }n\}\) и \(R_2=\{(m,n)\mid m\in M,\; n\in M,\; m
Конструктивно: \[R_1=\{(10;5),(20;4),(20;5),(30;5),(40;4),(40;5)\},\quad R_1\subseteq M\times N.\] \[R_2=\{(10;20),(10;30),(10;40),(20;30),(20;40),(30;40)\},\quad R_2\subseteq M\times M.\]

Определение 2: Дефиниционна област (домен) на релация е множеството \(D_R=\{x\mid \exists\, y:\; xRy\}\), а областта от стойности е \(J_R=\{y\mid \exists\, x:\; xRy\}\).

Пример 2: Нека \(M=\{a,b,c,d\}\), \(N=\{1,2,3,4\}\) и \(R=\{(a;1),(b;3),(b;4),(c;1)\}\subseteq M\times N\). Тогава \(D_R=\{a,b,c\}\) и \(J_R=\{1,3,4\}\).

---

Представяне на релации

За изобразяването на релации се използват таблици (матрици), диаграми и графи. Табличното и диаграмното представяне важат за произволни две множества; представянето с граф е само за релации върху едно и също множество.

Пример 3: Нека \(K=\{a,b,c\}\) и \(R=\{(a;a),(a;c),(b;b),(c;a),(c;b)\}\). Таблично представяне — в клетката се записва \(1\), ако наредената двойка е в \(R\), и \(0\) в противен случай:

Тъй като \((a;a)\in R\), в клетката на пресичане на ред \(a\) и колона \(a\) записваме \(1\). Тъй като \((a;b)\notin R\), там записваме \(0\). По същия принцип попълваме цялата таблица.

---

Обратна релация, равенство и операции

Определение 3: Обратна релация на \(R\) е множеството \(R^{-1}=\{(n;m)\mid (m;n)\in R\}\). Дефиниционната област на \(R^{-1}\) е областта от стойности на \(R\) и обратно. Освен това \((R^{-1})^{-1}=R\).

Определение 4: Две релации са равни, ако се състоят от едни и същи наредени двойки.

Тъй като релациите са множества, за тях важат операциите обединение, сечение, разлика и допълнение.

Пример 4: Нека \(R_1=\{(a;a),(b;b),(c;c),(a;c)\}\) и \(R_2=\{(a;a),(a;b),(b;b),(a;c),(b;c)\}\). Тогава: \[R_1\cup R_2=\{(a;a),(b;b),(c;c),(a;c),(a;b),(b;c)\};\] \[R_1\cap R_2=\{(a;a),(b;b),(a;c)\};\] \[R_1\setminus R_2=\{(c;c)\};\] \[R_2\setminus R_1=\{(a;b),(b;c)\}.\]

---

Композиция на релации

Определение 5: Композиция на релациите \(R_1\subseteq M\times N\) и \(R_2\subseteq N\times K\) е релацията \(R_1\circ R_2\subseteq M\times K\), такава, че: \[R_1\circ R_2=\{(m;k)\mid \exists\, n\in N:\; (m;n)\in R_1\text{ и }(n;k)\in R_2\}.\] Доказва се, че композицията е асоциативна, но не е комутативна: \[R_1\circ(R_2\circ R_3)=(R_1\circ R_2)\circ R_3,\quad R_1\circ R_2\neq R_2\circ R_1.\]

Пример 5: Нека \(M=\{a,b,c\}\), \(N=\{1,2\}\), \(K=\{d,e,f,g,h\}\) и \[R_1=\{(a;1),(a;2),(b;1),(c;2)\},\quad R_2=\{(1;d),(1;e),(2;f),(2;g),(2;h)\}.\] Тъй като \((a;1)\in R_1\) и \((1;d)\in R_2\), следва \((a;d)\in R_1\circ R_2\); от \((a;2)\in R_1\) и \((2;f)\in R_2\), следва \((a;f)\in R_1\circ R_2\) и т.н.

Пример 6: Нека \(A=\{\text{котка, куче, хамстер}\}\), \(B=\{\text{храна, вода}\}\), \(C=\{\text{пакост, наводнение, счупен прозорец, топка}\}\) и \[R_1=\{(\text{котка;храна}),(\text{котка;вода}),(\text{куче;храна}),(\text{хамстер;вода})\},\] \[R_2=\{(\text{храна;пакост}),(\text{храна;топка}),(\text{вода;наводнение})\}.\] От \((\text{котка;храна})\in R_1\) и \((\text{храна;пакост})\in R_2\) следва \((\text{котка;пакост})\in R_1\circ R_2\); от \((\text{котка;вода})\in R_1\) и \((\text{вода;наводнение})\in R_2\) следва \((\text{котка;наводнение})\in R_1\circ R_2\) и т.н.

---

Задачи за самостоятелна работа

Задача 1Дадена е бинарната релация \(R\) от \(A=\{a,b,c,d\}\) в \(B=\{1,2,3,4,5\}\) и \(R=\{(a;1),(a;2),(b;3),(c;4),(d;5)\}\). Задайте релацията с таблица.

Задача 2Дадени са релациите \(R_1=\{(1;4),(1;5),(3;4)\}\subseteq A\times B\) и \(R_2=\{(4;6),(4;7),(5;8),(5;9)\}\subseteq B\times C\) над \(A=\{1,2,3\}\), \(B=\{4,5\}\) и \(C=\{6,7,8,9\}\). Намерете броя на елементите на композицията \(R_1\circ R_2\).

---

Онлайн тест

10 въпроса • 6 точки за верен отговор • максимум 60 точки

Тест: Релации

Изберете верния отговор за всеки въпрос, след което натиснете КРАЙ.

1Бинарна релация е релация с \(n=\):

\(1\) \(2\) \(3\)

2Дефиниционната област \(D_R\) на релация \(R\) е:

Множеството на втория домен Множеството \(\{x\mid \exists\,y:\; xRy\}\) Множеството на всички наредени двойки

3В Пример 2: \(J_R\) е равно на:

\(\{a,b,c,d\}\) \(\{1,3,4\}\) \(\{1,2,3,4\}\)

4В Пример 4: \(R_1\cap R_2\) е:

\(\{(a;a),(b;b),(c;c),(a;c)\}\) \(\{(a;a),(b;b),(a;c)\}\) \(\{(a;b),(b;c)\}\)

5В Пример 4: \(R_2\setminus R_1\) е:

\(\{(c;c)\}\) \(\{(a;b),(b;c)\}\) \(\{(a;b),(a;c)\}\)

6Обратната релация \(R^{-1}\) се получава чрез:

Изтриване на всяка втора наредена двойка Разменяне на местата в двойките: \((m;n)\to(n;m)\) Добавяне на нови двойки

7Вярно е, че \((R^{-1})^{-1}\) е равно на:

\(R^{-1}\) \(R\) Празното множество

8Композицията \(R_1\circ R_2\) е дефинирана, когато:

\(R_1\) и \(R_2\) са върху едно множество Вторият домен на \(R_1\) съвпада с първия домен на \(R_2\) \(R_1\) и \(R_2\) имат еднакъв брой елементи

9Композицията на релации е:

Комутативна и асоциативна Асоциативна, но не комутативна Комутативна, но не асоциативна

10В таблично представяне на релация, в клетка се записва \(1\), когато:

Двата елемента са равни Съответната наредена двойка принадлежи на релацията Двата елемента не са в релация

Използвана литература

1. Дискретна математика, Светла Бойчева, Стефка Толева-Стоименова, изд. Сиела 2018 г.
2. Увод в дискретната математика, Красимир Манев, изд. КЛМН 2012 г.
3. Въведение в дискретната математика, Христо Кискинов, Пловдивско университетско издателство
4. Ръководство за решаване на задачи по дискретна математика

Запишете урок

Индивидуални и групови онлайн уроци по математика за цялата страна

🎓 Подготовка за изпити

• ›НВО по математика след 7 клас
• ›НВО по математика след 10 клас
• ›Кандидатстудентски изпити по математика
• ›Прием в университети в чужбина (ISEE, SAT, A-Level)

📚 Текущо обучение и студенти

• ›Усвояване на текущия учебен материал (всички класове)
• ›Студенти: Мат. анализ, Линейна алгебра, Аналитична геометрия, Диф. уравнения, Теория на вероятностите, Статистика и др.

✆ 0883 375 433 ☎ Viber

Харесва ли ви съдържанието?

Ако този урок ви е бил полезен, можете да подкрепите създаването на нови безплатни материали.

📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆ 📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆