5 Релацијске структуре

Релацијске структуре или релације, представљају основни концепт у математици који се користи за описивање односа између елемената неког скупа. Оне су кључне у разумевању структуре математичких објеката и имају широку примену у различитим областима, као што су логика, теорија скупова, алгебра и рачунарство. На пример, у математици, релација “мање” успоставља однос између бројева, где за било која два броја \(a\) и \(b\), релација \(a < b\) означава да је \(a\) мање од \(b\). Са друге стране, можемо разматрати релацију “пријатељства” међу људима, где је скуп људи повезан кроз друштвене односе. Дакле, релације нам омогућавају да моделирамо и анализирамо комплексне системе интеракција, било да су у питању нумерички подаци, социјалне мреже, или транспортни системи. У наставку изучавамо бинарне релације, које повезује елементе из једног скупа са елементима из другог скупа по одређеном правилу или својству.

Бинарна релација \(R\) на скупу \(A\) је подскуп Декартовог производа \(A \times A\).

Пример

Нека је \(A = \{1, 2, 3\}\), и нека је дата релација \(R\) на \(A\) као \(R = \{ (1, 2), \ (1, 3), \ (2, 3) \}\). Ако пажљиво погледамо који елементи су у релацији тј. шта су елементи скупа \(R\) можемо рећи да је на овај начин дефинисана релација мање (\(<\)) на скупу \(A\). Дакле \(a\) је у релацији са \(b\) ако је \(a\) мање од \(b\).

Уместо записа \((a,b) \in R\) који говори да су елементи \(a\) и \(b\) у релацији \(R\) често користимо ознаку \(a R b\) док за елементе који нису у релацији на пример \(c\) i \(d\) уместо ознаке \((c,d) \notin R\) користимо ознаку \(a \cancel{R} b\).

Представљање релација

Бинарна релација \(R\) на коначном скупу \(A\) можем се представити на неколико начина:

Набрајањем елемената

Као подскуп скупа \(A^2\), односно набрајањем елемената који су у релацији. У случају да је велики број елемената у релацији а мали број елемената који нису у релацији могуће је навести скуп елемената који нису у релацији \(R'\) и у том случају релацију \(R\) добијамо као комплемент датог скупа тј. \(R=A^2/R'\).
Таблицом

Формирањем таблице чије су колоне и врсте нумерисане елементима скупа \(A\), док се у пресеку \(i\)-врсте и \(j\)-колоне наводи 1 ако је \(i R j\), а у супротном 0.
Графом

Елементи скупа \(А\) се представљају као кружићи (чворови) у равни а уколико је \(a R b\), чворови \(a\) и \(b\) се повезују усмереном линијом (усмереном граном) од \(a\) ка \(b\).

Пример

Дата је релација \(R_1\) на скупу \(\{1,2,3,4,5,6\}\) дефинисана на следећи начин:

\[ x R_1 y\ \Leftrightarrow\ x<y\ \land\ x\mid y. \]

Ову релацију можемо да представимо на више начина:

Набрајањем елемената који су у релацији

\[ R_1=\{(1,2),(1,3),(1,4),(1,5),(1,6),(2,4),(2,6),(3,6)\}. \]

или

\[1\,R_1\,2,\,\, 1\,R_1\,3,\,\, 1\,R_1\,4,\,\, 1\,R_1\,5,\,\, 1\,R_1\,6,\,\, 2\,R_1\,4,\,\, 2\,R_1\,6,\,\, 3\,R_1\,6.\]
Таблицом:

\(R_1\)	2	3	4	5	6
1	1	1	1	1	1
2	0	0	1	0	1
3	0	0	0	0	1
4	0	0	0	0	0
5	0	0	0	0	0
6	0	0	0	0	0

Графом

Основна својства бинарних релација

Као што бинарне операције имају одређена својства (асоцијативност, комутативност), тако и бинарне релације могу имати одређена својства. За релацију кажемо да је рефлексивна ако је сваки елемент скупа у релацији са самим собом. Релација је симетрична ако за сваки пар елемената важи да кад је први елемент у релацији с другим, онда је и други у релацији с првим. Са друге стране кажемо да је релације антисиметрична ако за сваки пар различитих елемената важи да кад је први у релацији с другим, други није у релацији с првим. За релацију кажемо да је транзитивна ако за било која три елемента, када је први у релацији са другим и други са трећим, онда је и први у релацији с трећим. Све наведене особине можемо формално записати коришћењем предикатских формула.

Релација \(R\) на скупу \(A\) је:

Рефлексивна (Р) ако \((\forall a \in A) \ a \, R \, a\)
Симетрична (С) ако \((\forall a, b \in A) \ a \, R \, b \Rightarrow b \, R \, a\)
Антисиметрична (АС) ако \((\forall a, b \in A) \ a \, R \, b \, \land\, b \, R \, a \,\,\Rightarrow\,\, a = b\)
Транзитивна (Т) ако \((\forall a, b, c \in A) \ a \, R \, b \,\land \,b \, R \, c \,\,\Rightarrow\,\, a \, R \, c\)

Пример

Нека је дата релација \(R_2 = \{ (1, 2),(2, 2), (2, 3), (3, 1), (3, 2), (4, 4), (5, 5) \}\) дефинисана на скупу \(\{1, 2, 3, 4, 5\}\).

Релација \(R_2\) није Р јер \(1\,\cancel{R_2}\,1\) (слично за елемент \(3\)).

Релација \(R_2\) није С јер је \(1\,R_2\,2\) а \(2\,\cancel{R_2}\,1\) (слично за \(3\) и \(1\)).

Релација \(R_2\) није АС јер за различите елементе \(2\) и \(3\) важи да је \(2\,R_2\,3\) и \(3\,R_2\,2\).

Релација \(R_2\) није Т јер имамо да је \(1\,R_2\,2\), \(2\,R_2\,3\) док \(1\,\cancel{R_2}\,3\) (слично за \(2, 3, 1\)).
Релација једнкости \(=\) на скупу \(\mathbb{N}\) јесте Р, С, АС и Т.,
Релација \(\le\) na skupu \(\mathbb{R}\) jeste Р, АС и Т, а није С.

Из табличне репрезентације релације лако можемо да проверимо особине Р, С и АС. Релација је:

Р ако и само ако су сви елементи главне дијагонале једнаки 1.
С ако и само ако је табела симетрична у односу на главну дијагоналу тј. свака два елемента која су симетрична у односу на главну дијагоналу су једнака.
АС ако и само ако у табели не постоје две 1-це које су симетричне у односу на главну дијагоналу тј. елементи који су симетрична у односу на главну дијагоналу нису оба једнака 1.

Пример

Посматрајмо релацију \(R_1\) из првог примера и њену табличну репрезентацију.

\(R_1\)	2	3	4	5	6
1	1	1	1	1	1
2	0	0	1	0	1
3	0	0	0	0	1
4	0	0	0	0	0
5	0	0	0	0	0
6	0	0	0	0	0

На главној дијагонали нису све 1 па релација није Р

Eлементи у односу на главну дијагоналу (обојени истом бојом) нису увек једнаки па није ни С.

Eлементи у односу на главну дијагоналу (обојени истом бојом) нису никад истовремено једнаки 1 одакле следи да је релација АС.

Слично из графовске репрезентације релације можемо проверити својства Р, С, АС али и особину Т.

Релација је

Р ако и само ако се у сваком чвору налази петља.
С ако и само ако свака два различита чвора или нису повезана или су повезана са две гране (супротних оријентација).
АС ако и само ако свака два различита чвора нису повезана са две гране (супротних оријентација).
- Т ако и само ако за сваке две гране које се надовезују постоји грана која води од почетног чвора прве до завршног чвора друге гране.

Релација еквиваленције

Релација \(R\) на скупу \(A\) је релација еквиваленције ако је рефлексивна, симетрична и транзитивна.

Пример

Код релације еквиваленције за сваки елемент можемо посматрати скуп њему еквивалентних елемената односно скуп свих елемената који су у релацији са њим. Ови скупови се називају класе еквиваленције. Формално, нека је \(R\) релација еквиваленције на скупу \(A\) и нека је \(x \in A\). Скуп

\[C_a = \{ b \in A : a \, R \, b \}\]

назива се класа еквиваленције елемента \(a\).

Пример

Посматрајући класе еквиваленције у претходном примеру можемо да приметимо да су класе за елементе који су у релацији једнаке, док су класе за елементе који нису у релацији дисјунктне. Такође класа сваког елемента је непразна а унија свих класа еквиваленције даје цео скуп \(A\). Ово запажање је формално записано кроз следеће тврђење.

Нека је \(R\) релација еквиваленције на скупу \(A\). Тада важи:

\(\forall a \in A\quad C_a \neq \emptyset\).
\(\forall a,b \in A\quad a\,R\,b \,\,\Rightarrow\,\, C_a = C_b\).
\(\forall a,b \in A\quad a\,\cancel{R}\,b \,\,\Rightarrow\,\, C_a \cap C_b = \emptyset\)
\(A = \bigcup_{a \in A} C_a\).

Дакле свака релација еквиваленције партиционише (разбија) полазни скуп на непразне дисјунктне подскупове. Поставља се питање да ли важи обратно тј. уколико имамо дато партиционисање неког скупа на \(k\) дисјунктних подскупова да ли постоји релација еквиваленције чије класе партиционишу полазни скуп на идентичан начин.

Пример

Посматрајмо скуп \(А=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\) и разбијање на подскупове \(A_1=\{1, 3, 5, 7, 9\}\) и \(A_2=\{2, 4, 6, 8, 10\}\).

Релација еквиваленције која даје ове класе еквиваленције је релација парности. Два елемента \(a\) и \(b\) су у релацији ако и само ако имају исту парност, односно оба су или непарна или парна. Једноставно се проверава да је овако дефинисана релација Р,С и Т што значи да је релација еквиваленције. Тада скуп \(\{1, 3, 5, 7, 9\}\) представља класу еквиваленције зa непарне бројеве, а скуп \(\{2, 4, 6, 8, 10\}\) представља класу еквиваленције за парне бројеве.

Нека је \(\{A_1, A_2, \ldots, A_k\}\) партиција скупа \(A\). Нека је \(R\) релација на скупу \(A\), дефинисана на следећи начин \(a \, R \, b\) ако и само ако елементи \(a\) и \(b\) припадају истом елементу партиције \(A_i\). Тада је \(R\) релација еквиваленције чије су класе еквиваленције управо подскупови \(A_1, A_2, \ldots, A_k\).

Пример

Посматрајмо скуп \(A=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\) и разбијање на подскупове \(A_1=\{1, 3, 5, 7, 9, 10\}\) и \(A_2=\{2, 4, 6, 8\}\). У овом случају можемо увести релацију \(a\,R\,b\) ако и само ако \(a\) и \(b\) припрадају истом скупу \(A_i\). Уведена релација је релација еквиваленције а класе еквиваленције су управо \(A_1\) и \(A_2\).

Релација поретка

Релација \(R\) на скупу \(A\) је релација поретка ако је рефлексивна, антисиметрична и транзитивна. Тада уређен пар \((A,R)\) називамо уређен скуп.

Пример

Ако је \(A \subseteq \mathbb{R}\), онда су \((A, \leq)\) и \((A, \geq)\) уређени скупови.
Ако је \(A \subseteq \mathbb{N}\), онда је \((A, \mid)\) уређен скуп.
Ако је \(A \subseteq \mathcal{P}(B)\), онда су \((A, \subseteq)\) и \((A, \supseteq)\) уређени скупови.

Нека је \((A, R)\) уређен скуп. Ако је \(a R b\) или \(b R a\) за елементе \(a\) и \(b\), кажемо да су упоредиви. Скуп чија су свака два елемента упоредива називамо тотално уређеним скупом, док се скуп који није тотално уређен назива парцијално уређеним скупом.

Пример

\((\mathbb{R}, \leq)\), \((\mathbb{Z}, \leq)\) су тотално уређени скупови.
\((\mathbb{N}, \mid)\), \((\mathcal{P}(A), \subseteq)\) су парцијално уређени скупови.

Најмањи, највећи, минимални и максимални елемент

За \(a \in A\) кажемо да је најмањи елемент уређеног скупа \((A,R)\) ако за свако \(b \in A\) важи \(a R b\). За \(a \in A\) кажемо да је минимални елемент уређеног скупа \((A,R)\) ако не постоји \(b \in A\) такав да важи \(b \neq a\) и \(b R a\).

За \(a \in A\) кажемо да је највећи елемент уређеног скупа \((A,R)\) ако за свако \(b \in A\) важи \(b R a\). За \(a \in A\) кажемо да је максимални елемент уређеног скупа \((A,R)\) ако не постоји \(b \in A\) такав да важи \(b \neq a\) и \(a R b\).

Пример

У уређеном скупу \(([0,1], \leq)\), најмањи елемент је 0, а највећи елемент је 1.
У уређеном скупу \(((0,1), \leq)\), не постоји ни најмањи ни највећи елемент.
У уређеном скупу \((\mathbb{N}, \leq)\), најмањи елемент је 1, док највећи елемент не постоји.
У уређеном скупу \((\mathcal{P}(\mathbb{N}), \subseteq)\), најмањи елемент је \(\emptyset\), а највећи елемент је \(\mathbb{N}\).
Нека је \(\mathcal{K}(\mathbb{N})\) скуп свих коначних подскупова скупа \(\mathbb{N}\). Најмањи елемент у \((\mathcal{K}(\mathbb{N}), \subseteq)\) је \(\emptyset\), док највећи елемент не постоји.

Најмањи (или највећи) елемент уређеног скупа \((S, R)\), ако постоји, јединствен је и уједно минимални (максимални) елемент, што значи да је једини такав елемент у скупу. У коначном уређеном скупу увек постоји бар један минимални и бар један максимални елемент, а ако постоји тачно један минимални (или максимални) елемент, тај елемент је најмањи (или највећи) у скупу. У тотално уређеном скупу, сваки минимални (максимални) елемент је истовремено и најмањи (највећи) елемент, и обрнуто.

Пример

Уређен скуп \(A = \{1, 2, 3\}\) са релацијом \(R = \{(1,1), (2,2), (3,1), (3,2), (3,3)\}\).
- \((A,R)\) је парцијално уређен скуп.
  
  Лако се проверава да је релација \(R\) релација поретка. Како \(1\cancel{R}2\) и \(2\cancel{R}1\) скуп \(S\) са релацијом \(R\) је парцијално уређен.
- Елемент 3 је најмањи и једини минимални елемент.
  
  Елемент 3 је у релацији са свим елементима (\((3,1)\) и \((3,2)\) су у \(R\)), што значи да је мањи или једнак сваком елементу у скупу. Пошто не постоји елемент који је мањи од 3, он је најмањи елемент и уједно једини минимални елемент.
- Елементи 1 и 2 су максимални елементи, па највећи елемент не постоји.
  
  Елементи 1 и 2 нису у релацији са ниједним елементом (осим са самим собом), што их чини максималним елементима. Пошто не постоји елемент са којим су сви елементи у релацији, највећи елемент не постоји.
Уређен скуп \((\mathbb{N} \setminus \{1\},\ \mid)\):
- Нема максималних елемената.
  
  У релацији дељивости, за сваки број \(n > 1\), постоји број \(n \cdot m\) који је дељив са \(n\) односно \(n\,|\,n \cdot m\) па не постоје максимални елементи у овом скупу.
- Минимални елементи су просте бројеви.
  
  Прост број \(p\) се не дели ни са једним бројем осим са 1 и самим собом. Пошто је 1 искључен из скупа, просте бројеви су елементи који немају ниједан други елемент који их дели, те су они минимални елементи.
- Нема најмањих ни највећих елемената.
  
  Не постоји број који је дељив са свим другим бројевима (осим 1, који је искључен), па најмањи елемент не постоји. Можемо рећи да не постоји најмањи елемент и зато што има више минималних елемената. Такође, како не постоји максимални елемент онда не постоји ни највећи елемент.
Уређен скуп \(S = \{1, 2, 3, 4, 5\}\) са релацијом \[R = \{(1,1), (2,2), (3,1), (3,2), (3,3), (4,2), (4,4), (5,1), (5,2), (5,3), (5,5)\}.\]
- Скуп је парцијално уређен.
  
  Лако се проверава да је релација \(R\) релација поретка. Како \(1\cancel{R}2\) и \(2\cancel{R}1\) скуп \(S\) са релацијом \(R\) је парцијално уређен.
- Елементи 4 и 5 су минимални, а 1 и 2 су максимални елементи.
  
  Ни један елемент није у релацији са 4 и 5 (осим сами са собом) што их чини минималним елементима. Елементи 1 и 2 нису у релацији ни са једним другим елементом (осим са самим собом), па су максимални.
- Нема најмањих ни највећих елемената.
  
  Због постојања више минималних и максималних елемената, не постоји најмањи и највећи елемент.
Уређен скуп \((\mathcal{P}(A) \setminus \emptyset,\ \subseteq)\):
- \(A\) је највећи и једини максимални елемент.
  
  Скуп \(A\) садржи све подскупове себе самог и тиме је највећи елемент у овом парцијалном поретку. Пошто не постоји ниједан други подскуп који га садржи (осим можда самог себе), он је једини максимални елемент.
- Минимални елементи су сви једночлани подскупови скупа \(A\).
  
  Једночлани подскупови немају подскупове у \(\mathcal{P}(A) \setminus \emptyset\) (осим празаног скупа, који је искључен), па су они минимални елементи.
- Најмањи елемент не постоји.
  
  Због постојања више минималних елемената, не постоји најмањи елемент.

Доње и горње ограничење

Нека је \((A,R)\) уређен скуп и \(B \subseteq A\).

За \(a \in A\) кажемо да је доње ограничење (доња међа или минорaнта) скупа \(B\) ако за свако \(x \in B\) важи \(a R x\).
За \(a \in A\) кажемо да је горње ограничење (горња међа или мајоранта) скупа \(B\) ако за свако \(x \in B\) важи \(xR a\).

Сваки елемент из парцијално уређеног скупа \(A\) представља и доње и горње ограничење празног скупа, јер празан скуп нема елемената са којима би се могли упоредити елементи из \(A\). Међутим, доње или горње ограничење неког подскупа не мора увек да постоји у \(A\); постоје случајеви када подскуп нема ни једно доње или горње ограничење унутар скупа \(A\). Чак и када доње или горње ограничење постоји, оно не мора бити јединствено — може постојати више елемената који задовољавају услове доњег или горњег ограничења без постојања највећег доњег ограничења (инфимума) или најмањег горњег ограничења (супремума).

Пример

У \((\mathbb{R}, \leq)\):
- Доња ограничења скупа \([1, 3]\) су бројеви \(a\) такви да је \(a \leq 1\).
- Горња ограничења скупа \([1, 3]\) су бројеви \(a\) такви да је \(a \geq 3\).
У \((\mathbb{N}, \mid)\):
- Доња ограничења скупа \(\{6, 9, 12\}\) су 1 и 3.
- Горња ограничења скупа \(36k\), где је \(k \in \mathbb{N}\).
У \((\mathcal{P}(\{1,2,3,4\}), \subseteq)\):
- Доња ограничења скупа \(\{\{1,2\}, \{2,3\}\}\) су \(\emptyset\) и \(\{2\}\).
- Горња ограничења скупа су \(\{1,2,3\}\) и \(\{1,2,3,4\}\).

Инфимум и супремум

Нека је \((A,R)\) уређен скуп и \(B \subseteq A\).

Инфимум скупа \(B\), означен са \(\inf B\), је највећи елемент скупа свих доњих међа скупа \(B\).
Супремум скупа \(B\), означен са \(\sup B\), је најмањи елемент скупа свих горњих међа скупа \(B\).

Супремум (инфимум) неког скупа не мора увек да постоји; међутим, ако постоји, онда је јединствен. Ако скуп има највећи (најмањи) елемент, тај елемент је уједно и његов супремум (инфимум). Штавише, највећи (најмањи) елемент постоји ако и само ако супремум (инфимум) припада самом скупу.

Пример

У \((\mathbb{R}, \leq)\):
- \(\inf[1,3] = \inf(1,3) = 1\)
- \(\sup[1,3] = \sup(1,3) = 3\)
У \((\mathbb{N}, \mid)\):
- \(\inf\{6,9,12\} = \operatorname{NZD}(6,9,12) = 3\)
- \(\sup\{6,9,12\} = \operatorname{NZS}(6,9,12) = 36\)
У \((\mathcal{P}(\{1,2,3,4\}), \subseteq)\):
- \(\inf\{\{1,2\}, \{2,3\}\} = \{2\}\)
- \(\sup\{\{1,2\}, \{2,3\}\} = \{1,2,3\}\)

За уређен скуп у коме свака два елемента имају супремум и инфимум кажемо да је решетка (или мрежа).

У тотално уређеном скупу сваки пар елемената је упоредив и за сваки пар постоје супремум (већи од та два елемента) и инфимум (мањи од та два елемента) што значи да је такав скуп решетка. Решетка има највише један минимални и највише један максимални елемент. Ако постоји, минимални (максимални) елемент решетке, он је уједно и њен најмањи (највећи) елемент.

Пример

Уређени скупови \((\mathbb{R}, \leq)\), \((\mathbb{Q}, \leq)\), \((\mathbb{Z}, \leq)\) и \((\mathbb{N}, \leq)\) су тотално уређени скупови, самим тим и решетке.
Уређен скуп \((\mathbb{N}, \mid)\) је решетка јер је за свако \(m, n \in \mathbb{N}\):
- \(\inf\{m, n\} = \operatorname{NZD}(m, n)\)
- \(\sup\{m, n\} = \operatorname{NZS}(m, n)\)
Уређен скуп \((\{6, 9, 12\}, \mid)\) није решетка јер:
- \(\operatorname{NZD}(6, 9) = 3 \notin \{6, 9, 12\}\)
- \(\operatorname{NZS}(6, 9) = 18 \notin \{6, 9, 12\}\)
Уређен скуп \((\mathcal{P}(A), \subseteq)\) је решетка јер за сваки \(X, Y \in \mathcal{P}(A)\):
- \(\inf\{X, Y\} = X \cap Y\)
- \(\sup\{X, Y\} = X \cup Y\)
Уређен скуп \((\{\{1,2\}, \{2,3\}, \{1,2,3\}\}, \subseteq)\) није решетка јер

\(\{1,2\} \cap \{2,3\} = \{2\} \notin \{\{1,2\}, \{2,3\}, \{1,2,3\}\}\)

Хасеови дијаграми

Хасеов дијаграм је графички приказ парцијално уређеног скупа који омогућава визуелну репрезентацију односа између елемената тог скупа и помаже у идентификацији својстава као што су минимални и максимални елементи, инфимум, супремум итд.

Хасеов дијаграм се може конструисати тако што се сваком елементу из скупа \(A\) придружи један чвор. Сваки чвор се повезује (не)оријентисаним гранама са својим непосредним претходницима. Елемент \(a \in A\) је непосредни претходник елемента \(b \in A\) ако је \(a \neq b\), \(a R b\) и не постоји \(c \in A\), различит од \(a\) и \(b\), такав да је \(a R c\) и \(c R b\). Чворови се ређају одоздо навише по нивоима, почевши од нивоа 0 који се налази на дну дијаграма и у коме су смештени чворови који немају непосредне претходнике. Чвор се смешта у ниво \(n\) ако су сви његови непосредни претходници на нижим нивоима и бар један од њих на нивоу \(n-1\).

Пример

Оријентисан Хасеов дијаграм за уређен скуп \((\{1,2,\dots,9\}, \mid)\).
Оријентисан Хасеов дијаграм за уређен скуп \((\{1,2,3,4\}, \leq)\).

Хасеов дијаграм се може конструисати коришћењем транзитивне редукције уместо одређивања непосредних претходника за сваки чвор.

Транзитивно затворење релације је проширење дате релације тако да постане транзитивна. То значи да се оригиналној релацији додају сви потребни парови \((a, c)\) за које важи да постоје \((a, b)\) и \((b, c)\) у тој релацији. На тај начин, транзитивно затворење је најмања транзитивна релација која садржи почетну релацију.

Транзитивна редукција релације је, насупрот томе, сужавање релације тако да се из ње уклоне сви парови који се могу добити транзитивношћу из других парова. Другим речима, из релације се уклањају све везе које нису неопходне за одржавање истог транзитивног затворења. Транзитивна редукција је најмања могућа релација чије је транзитивно затворење једнако оригиналној релацији.

Хасеов дијаграм се конструише уклањањем петљи из оригиналног графа релације и применом транзитивне редукције. У овом графу остаће само непосредних односи између елемената јер су елиминисани они који су последица транзитивности.

Релације у Пајтону

Релацију у програмском језику можемо дефинисати веома једноставно коришћењем скупова и comprehension синтаксе. На почетку дефинисаћемо скуп \(А\). Како смо у претходним примерима често користили предикате за дефинисање релације можемо увести функцију predikat_relacije_R(a , b) да опишемо предикат који описује да су два елемента у релацији. Саму релацију R креирамо као скуп свих парова \((a, b)\) из \(A\) који испуњавају дефинисан предикат.

A = {1, 2, 3, 4, 5, 6}

def predikat_relacije_R(a, b):
    return a < b and b % a == 0

R = {(a, b) for a in A for b in A if predikat_relacije_R(a, b)}

Дефинисану релацију можемо приказати скуповно тако што штампамо скуп \(R\). За приказ таблице дефинисаћемо функцију tablica(R, A) која креира табелу за релацију \(R\) на скупу \(A\). На почетку уводимо променљиву linija за креирање хоризонталних линија раздвајања у табели, у складу са бројем елемената у \(A\). Затим креирамо заглавље табеле тј. у првом реду табеле исписујемо ознаку „R“ у првој колони и све елементе из скупа \(A\) као заглавља колона. Након тога за сваки елемент \(a\) из \(A\), креирамо ред у табели. У првој колони тог реда налази се елемент \(a\), а у осталим колонама су вредности \(1\) или \(0\), у зависности од тога да ли је пар \((a, b)\) у релацији \(R\). Ако је \((a, b)\) у \(R\), исписујемо \(1\), иначе \(0\). На крају враћамо формирану табелу као стринг, који можемо исписати у конзолие.

def tablica(R, A):
    linija = "\n" + ("+-----" * (len(A) + 1)) + "+\n"
    tablica = linija

    tablica += '|{:^5}|'.format("R")
    for a in A:
        tablica += '{:^5}|'.format(a)
    tablica += linija

    for a in A:
        tablica += '|{:^5}|'.format(a)
        for b in A:
            tablica += '{:^5}|'.format(int((a, b) in R))
        tablica += linija
    return tablica

За приказ графа релације користићемо библиотеку NetworkX. Дефинишемо функцију graf_relacije(R, A), која ће да приказује усмерени граф за релацију на датом скупу. На почетку увозимо библиотеке networkx и matplotlib.pyplot, где networkx служи за рад са графовима, а matplotlib.pyplot за визуелизацију. Функција graf_relacije прихвата релацију R, која је скуп уређених парова (и представља везе између елемената скупа), и скуп A, који садржи елементе. Унутар функције креирамо усмерени граф DiGraph() у који се додају чворови из скупа A и гране из релације R. На крају, граф исцртавамо помоћу кружног распореда чворова (circular_layout), уз приказ ознака чворова (with_labels=True), а резултат се приказује помоћу matplotlib.pyplot.show().

import networkx
import matplotlib.pyplot

def graf_relacije(R, A):
    graf = networkx.DiGraph()
    graf.add_nodes_from(A)
    graf.add_edges_from(R)
    networkx.draw(graf, networkx.circular_layout(graf), with_labels=True)
    matplotlib.pyplot.show()
    return graf

Функције all и any у Python-у проверавају да ли су сви или бар неки елементи у итерабилноj колекцији True.

all(kolekcija): Враћа True ако су сви елементи у итерабилној колекцији (нпр. листи) True. Ако постоји бар један False елемент, враћа False. На пример, all([True, True, False]) враћа False јер је последњи елемент False.
any(kolekcija): Враћа True ако бар један елемент у итерабилној колекцији има вредност True. Ако су сви елементи False, враћа False. На пример, any([False, False, True]) враћа True јер постоји један True елемент.

Ове функције су корисне за записивање предикатских формула са универзалним и егзистенцијалним квантификаторима где је домен неки коначан скуп.

За проверу рефлексивности имплементираћемо функцију je_refleksivna(R, A). Као што смо рекли користимо функцију all, која враћа True само ако су сви елементи у листи истинити. Унутар all, користимо comprehension израз [ (a, a) in R for a in A ], који генерише листу свих логичких вредности (True или False) за сваки \(a \in A\), у зависности од тога да ли је \((a, a)\) у \(R\). Ако је сваки \((a, a)\) у \(R\), функција враћа True, што значи да је релација рефлексивна; ако макар један пар недостаје, враћа False, чиме означавамо да релација није рефлексивна.

На сличан начин имплементирамо и остале функције за проверу симетричности, антисиметричности и транзитивности стим што из формула уклањамо импликацију за коју немамо уграђен оператор па формулу \(L \Rightarrow D\) записујемо као not L or D. Поступак записивања формуле којом је дефинисана особина транзитивности у Пајтон код приказана је на слици.

def je_refleksivna(R, A):
    return all([(a, a) in R for a in A])


def je_simetricna(R, A):
    return all([not ((a, b) in R) or ((b, a) in R) for a in A for b in A])


def je_antisimetricna(R, A):
    return all([not ((a, b) in R and (b, a) in R) or (a == b) for a in A for b in A])


def je_tranzitivna(R, A):
    return all([not ((a, b) in R and (b, c) in R) or ((a, c) in R) for a in A for b in A for c in A])

За потребе провере да ли је релација \(R\) на скупу \(A\) релација еквиваленције дефинисаћемо функцију je_relacija_ekvivalencije(R, A) која враћа True само ако су испуњене особине Р, С, Т.

def je_relacija_ekvivalencije(R, A):
    return je_refleksivna(R, A) and je_simetricna(R, A) and je_tranzitivna(R, A)

За потребе провере да ли је релација \(R\) на скупу \(A\) релација поретка дефинисаћемо функцију je_relacija_poretka(R, A) која враћа True само ако су испуњене особине Р, АС, Т.

def je_relacija_poretka(R, A):
    return je_refleksivna(R, A) and je_antisimetricna(R, A) and je_tranzitivna(R, A)

Дефинисаћемо функцију klase_ekvivalencije(R, A) која одређује све класе еквиваленције релације \(R\) на скупу \(A\), ако је \(R\) релација еквиваленције. Прво, проверавамо функцијом je_relacija_ekvivalencije(R, A) да ли је \(R\) релација еквиваленције. Ако јесте, креирамо празан скуп klase који ће садржати класе еквиваленције. За сваки елемент \(a\) из \(A\) дефинишемо класу \(C_a\) као frozenset (непроменљив скуп) свих елемената \(b\) из \(A\) који су у релацији са \(a\). Сваку добијену класу \(C_a\) додајемо у скуп klase, и након обраде свих елемената функција враћамо скуп класа еквиваленције. Ако \(R\) није релација еквиваленције, враћамо празан скуп. Користимо frozenset за \(C_a\) уместо set јер је frozenset непроменљив и као такав можемо да га додамо у скуп klase. Генерално, елементи било ког скупа у Пајтону могу да буду само непроменљиви објекти (бројеви, стрингови, уређене \(n\)-торке…) а разлог лежи у имплементацији скупова преко речника односно хеш табеле.

def klase_ekvivalencije(R, A):
    if je_relacija_ekvivalencije(R,A):
        klase = set()
        for a in A:
            C_a = frozenset(b for b in A if (a, b) in R)
            klase.add(C_a)
        return klase
    else:
        return set()

У функцији haseov_dijagram(R, A), желимо да конструишемо Хасеов дијаграм за релацију \(R\) на скупу \(A\). Прво проверавамо да ли је релација \(R\) парцијални поредак користећи функцију je_relacija_poretka(R, A). Ако јесте, креирамо граф релације помоћу функције graf_relacije(R, A). Затим уклањамо све петље користећи graf.remove_edges_from(networkx.selfloop_edges(graf)). Примењујемо транзитивну редукцију на граф са networkx.transitive_reduction(graf) да бисмо добили Хасеов дијаграм који садржи само непосредне односе. За распоред чворова, користимо graphviz_layout са параметром да се граф приказује одоздо навише ( -Grankdir="BT"). Уколико Graphviz није доступан, можемо користити planar_layout као алтернативу за распоред чворова. На крају, цртамо и приказујемо дијаграм користећи библиотеке networkx и matplotlib.

def haseov_dijagram(R, A):
    if je_relacija_poretka(R, A):
        graf = graf_relacije(R, A)
        graf.remove_edges_from(networkx.selfloop_edges(graf))
        haseov_dijagram = networkx.transitive_reduction(graf)

        raspored_cvorova = networkx.drawing.nx_agraph.graphviz_layout(haseov_dijagram, prog="dot", args='-Grankdir="BT"')
        # raspored_cvorova=networkx.planar_layout(haseov_dijagram)

        networkx.draw(haseov_dijagram, raspored_cvorova, with_labels=True)
        matplotlib.pyplot.show()
        
        return haseov_dijagram
    else:
        return None

def informacije_o_relaciji(predikat_relacije_R,A):

    R = {(a, b) for a in A for b in A if predikat_relacije_R(a, b)}
    print("R = ", R)
    print(tablica(R, A))
    print("Refleksivna:", je_refleksivna(R, A))
    print("Simetricna:", je_simetricna(R, A))
    print("Antisimetricna:", je_antisimetricna(R, A))
    print("Tranzitivna:", je_tranzitivna(R, A))
    print("Relacija ekvivalencije:", je_relacija_ekvivalencije(R, A))
    print("Relacija poretka:", je_relacija_poretka(R, A))
    print("Klase ekvivalencije:", klase_ekvivalencije(R, A))
    graf_relacije(R, A)
    haseov_dijagram(R, A)

Тестирање на различитим примерима:

A = {1, 2, 3, 4, 5, 6}

def predikat_relacije_R(a, b):
    return a < b and b % a == 0
    
informacije_o_relaciji(predikat_relacije_R,A)

R =  {(2, 4), (1, 2), (1, 5), (1, 4), (2, 6), (3, 6), (1, 6), (1, 3)}

+-----+-----+-----+-----+-----+-----+-----+
|  R  |  1  |  2  |  3  |  4  |  5  |  6  |
+-----+-----+-----+-----+-----+-----+-----+
|  1  |  0  |  1  |  1  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+-----+-----+
|  2  |  0  |  0  |  0  |  1  |  0  |  1  |
+-----+-----+-----+-----+-----+-----+-----+
|  3  |  0  |  0  |  0  |  0  |  0  |  1  |
+-----+-----+-----+-----+-----+-----+-----+
|  4  |  0  |  0  |  0  |  0  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+-----+
|  5  |  0  |  0  |  0  |  0  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+-----+
|  6  |  0  |  0  |  0  |  0  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+-----+

Refleksivna: False
Simetricna: False
Antisimetricna: True
Tranzitivna: True
Relacija ekvivalencije: False
Relacija poretka: False
Klase ekvivalencije: set()

A = {11, 22, 34, 36, 56}

def predikat_relacije_R(a, b):
    zbir_cifara_a = sum([int(cifra) for cifra in str(a)])
    zbir_cifara_b = sum([int(cifra) for cifra in str(b)])
    return (zbir_cifara_a - zbir_cifara_b) % 3 == 0
    
informacije_o_relaciji(predikat_relacije_R,A)

R =  {(56, 56), (22, 34), (36, 36), (56, 11), (11, 11), (34, 22), (34, 34), (22, 22), (11, 56)}

+-----+-----+-----+-----+-----+-----+
|  R  | 34  | 36  | 22  | 56  | 11  |
+-----+-----+-----+-----+-----+-----+
| 34  |  1  |  0  |  1  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+
| 36  |  0  |  1  |  0  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+
| 22  |  1  |  0  |  1  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+
| 56  |  0  |  0  |  0  |  1  |  1  |
+-----+-----+-----+-----+-----+-----+
| 11  |  0  |  0  |  0  |  1  |  1  |
+-----+-----+-----+-----+-----+-----+

Refleksivna: True
Simetricna: True
Antisimetricna: False
Tranzitivna: True
Relacija ekvivalencije: True
Relacija poretka: False
Klase ekvivalencije: {frozenset({36}), frozenset({56, 11}), frozenset({34, 22})}

A = {1, 2, 3, 4, 5, 6, 7, 8, 9}

def predikat_relacije_R(a, b):
    return b % a == 0 
    
informacije_o_relaciji(predikat_relacije_R,A)

R =  {(2, 2), (1, 6), (1, 3), (1, 9), (2, 8), (7, 7), (3, 3), (3, 9), (4, 8), (3, 6), (8, 8), (2, 4), (1, 2), (1, 5), (1, 8), (4, 4), (5, 5), (9, 9), (1, 1), (1, 4), (1, 7), (2, 6), (6, 6)}

+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  R  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  2  |  0  |  1  |  0  |  1  |  0  |  1  |  0  |  1  |  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  3  |  0  |  0  |  1  |  0  |  0  |  1  |  0  |  0  |  1  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  4  |  0  |  0  |  0  |  1  |  0  |  0  |  0  |  1  |  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  5  |  0  |  0  |  0  |  0  |  1  |  0  |  0  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  6  |  0  |  0  |  0  |  0  |  0  |  1  |  0  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  7  |  0  |  0  |  0  |  0  |  0  |  0  |  1  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  8  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |  1  |  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  9  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |  1  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+

Refleksivna: True
Simetricna: False
Antisimetricna: True
Tranzitivna: True
Relacija ekvivalencije: False
Relacija poretka: True
Klase ekvivalencije: set()

A = {2, 3, 4, 5, 6, 7, 8, 9, 10}

def predikat_relacije_R(a, b):
    return b % a == 0 
    
informacije_o_relaciji(predikat_relacije_R,A)

R =  {(4, 4), (8, 8), (2, 4), (5, 5), (7, 7), (9, 9), (2, 10), (6, 6), (10, 10), (5, 10), (3, 3), (2, 6), (3, 6), (3, 9), (2, 2), (4, 8), (2, 8)}

+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  R  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  | 10  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  2  |  1  |  0  |  1  |  0  |  1  |  0  |  1  |  0  |  1  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  3  |  0  |  1  |  0  |  0  |  1  |  0  |  0  |  1  |  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  4  |  0  |  0  |  1  |  0  |  0  |  0  |  1  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  5  |  0  |  0  |  0  |  1  |  0  |  0  |  0  |  0  |  1  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  6  |  0  |  0  |  0  |  0  |  1  |  0  |  0  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  7  |  0  |  0  |  0  |  0  |  0  |  1  |  0  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  8  |  0  |  0  |  0  |  0  |  0  |  0  |  1  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  9  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |  1  |  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 10  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |  1  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+

Refleksivna: True
Simetricna: False
Antisimetricna: True
Tranzitivna: True
Relacija ekvivalencije: False
Relacija poretka: True
Klase ekvivalencije: set()