2  Скупови

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

Појам скупа

Скуп је основни математички појам који представља колекцију добро дефинисаних и међусобно различитих објеката, који се називају елементима скупа. Елементи се не понављају у скупу тј. сваки елемент је јединствен. Објекти у скупу могу бити бројеви, матрице, функције, слова, људи, други скупови итд.

Скупови се најчешће задају на два начина:

1. Набрајањем елемената где се елементи директно наводе унутар витичастих заграда.
   • Пример: \(A = \{1, 2, 3, 4, 5\}\)
2. Описом својства које сви његови елементи задовољавају
   • Пример: \(B = \{ x \mid x \text{ је паран број између 1 и 10} \}\)

Редослед елемената у скупу није битан, па је скуп \(\{1, 2, 3\}\) исти као скуп \(\{3, 2, 1\}\).

Приликом задавања скупа помоћу неког својства треба бити пажљив. Размотримо, на пример, скуп \(X = \{ A \mid A \notin A \}\) свих скупова који не садрже сами себе као елемент. Да ли скуп \(X\) садржи самог себе?

• Ако је \(X \in X\), онда \(X\) не задовољава услов \(X \notin X\), па по дефиницији не припада скупу \(X\), тј. \(X \notin X\).
• Ако је \(X \notin X\), онда \(X\) задовољава услов, па по дефиницији припада скупу \(X\), тј. \(X \in X\).

У оба случаја долазимо до противречности. Овај парадокс, познат као Раселов парадокс, показује да наивна теорија скупова, која дозвољава формирање скупа на основу било ког својства, води до противречности. Због тога се користе аксиоматски системи теорије скупова који строго одређују како се скупови смеју формирати; њихово детаљније проучавање припада математичкој логици.

Британски математичар и филозоф Бертранд Расел (Bertrand Russell) открио је овај парадокс 1901. године. Да би га учинио приступачнијим, формулисао је причу о берберину: у једном селу постоји берберин који брије све оне, и само оне, који не брију сами себе. Ко брије берберина? Ако берберин брије самог себе, онда он спада међу оне које не сме да брије; ако не брије самог себе, онда спада међу оне које мора да брије.

Скупове често приказујемо и графички коришћењем Венових дијаграма који користе кругове или друге затворене криве за представљање скупова. Пресеци између кругова приказују заједничке елементе (пресеке) између скупова.

На пример, на слици 2.1 приказан је скуп \(A = \{1, 2, \dots, 10\}\) и његови подскупови: делиоци броја 10 (скуп \(B\)) и парни бројеви (скуп \(C\)).

Слика 2.1: Делиоци броја 10 (скуп \(B\)) и парни бројеви (скуп \(C\)) у скупу \(A\)

Основне релације међу скуповима су:

1. Једнакост скупова \(=\)
   • Два скупа \(A\) и \(B\) су једнаки ако садрже потпуно исте елементе.
   • Пример: Ако је \(A = \{1, 2, 3\}\) и \(B = \{3, 2, 1\}\), онда је \(A = B\).
2. Подскуп \(\subseteq\) и надскуп \(\supseteq\):
   • Скуп \(A\) је подскуп скупа \(B\) ако су сви елементи \(A\) такође и елементи \(B\).
   • Скуп \(B\) је надскуп скупа \(A\) ако је \(A \subseteq B\).
   • Пример: \(A = \{2, 3\}, B = \{1, 2, 3, 4\}\), тада је \(A \subseteq B\) и \(B \supseteq A\).
3. Прави подскуп \(\subset\) и прави надскуп \(\supset\):
   • Скуп \(A\) је прави подскуп скупа \(B\) ако је \(A \subseteq B\) и \(A \neq B\).
   • Скуп \(B\) је прави надскуп скупа \(A\) ако је \(B \supseteq A\) и \(A \neq B\).
   • Пример: \(A = \{2, 3\}, B = \{1, 2, 3, 4\}\), тада је \(A \subset B\) и \(B \supset A\).

Однос \(A \subseteq B\) на Веновом дијаграму приказан је на слици 2.2: круг скупа \(A\) налази се унутар круга скупа \(B\).

Слика 2.2: Скуп \(A\) је подскуп скупа \(B\)

Празан и универзални скуп

Празан скуп је скуп који нема ниједан елемент. Означава се са \(\emptyset\) или \(\{\}\).

Универзални скуп \(U\) је скуп свих елемената који се у датом разматрању посматрају; сви скупови са којима радимо његови су подскупови.

Празан скуп је подскуп сваког скупа: \(\emptyset \subseteq A\) за сваки скуп \(A\). Да то није тачно, у \(\emptyset\) би морао да постоји елемент који није у \(A\), а у \(\emptyset\) нема ниједног елемента. Празан скуп је зато и јединствен: ако би постојала два празна скупа, сваки би био подскуп другог, па би били једнаки.

Треба разликовати \(\emptyset\) и \(\{\emptyset\}\): први скуп нема елемената, а други има тачно један елемент — празан скуп. Слично као што је празна кутија различита од кутије у којој се налази празна кутија.

Универзални скуп није један исти за све ситуације, већ зависи од контекста. Ако посматрамо студенте једне генерације, \(U\) је скуп свих студената те генерације; ако решавамо једначину у целим бројевима, \(U = \mathbb{Z}\). На Веновим дијаграмима универзални скуп се приказује правоугаоником у коме се налазе кругови осталих скупова.

Операције са скуповима

Основне операције између скупова су:

1. Унија скупова \(\cup\):
   • Унија два скупа \(A\) и \(B\) је скуп свих елемената који припадају бар једном од скупова \(A\) или \(B\) односно \(A \cup B = \{ x \mid x \in A \ \text{или} \ x \in B \}\).
   • Пример: Ако је \(A = \{1, 2, 3\}\) и \(B = \{3, 4, 5\}\), онда је \(A \cup B = \{1, 2, 3, 4, 5\}\).
2. Пресек скупова \(\cap\):
   • Пресек два скупа \(A\) и \(B\) је скуп свих елемената који су заједнички за оба скупа односно \(A \cap B = \{ x \mid x \in A \ \text{и} \ x \in B \}\).
   • Пример: Ако је \(A = \{1, 2, 3\}\) и \(B = \{2, 3, 4\}\), онда је \(A \cap B = \{2, 3\}\).
3. Разлика скупова \(\setminus\):
   • Разлика скупова \(A\) и \(B\) је скуп елемената који припадају скупу \(A\), али не и скупу \(B\) односно \(A \setminus B = \{ x \mid x \in A \ \text{и} \ x \notin B \}\).
   • Пример: Ако је \(A = \{1, 2, 3, 4\}\) и \(B = \{3, 4, 5\}\), онда је \(A \setminus B = \{1, 2\}\).
4. Симетрична разлика \(\triangle\):
   • Симетрична разлика скупова \(A\) и \(B\) је скуп елемената који припадају тачно једном од скупова \(A\) или \(B\) односно \(A \triangle B = (A \setminus B) \cup (B \setminus A)\).
   • Пример: Ако је \(A = \{1, 2, 3\}\) и \(B = \{3, 4, 5\}\), онда је \(A \triangle B = \{1, 2, 4, 5\}\).
5. Комплемент скупа:
   • Комплемент скупа \(A\) у односу на универзални скуп \(U\) је скуп свих елемената који припадају \(U\), али не припадају \(A\) односно \(A' = U \setminus A\).
   • Пример: Ако је \(U = \{1, 2, 3, 4, 5\}\) и \(A = \{2, 3\}\), онда је \(A' = \{1, 4, 5\}\).

Резултат сваке операције можемо приказати Веновим дијаграмом, бојењем области која одговара добијеном скупу (слика 2.3):

Слика 2.3: Операције над скуповима (обојена је област добијеног скупа)

Важније особине операција са скуповима

За све скупове \(A, B, C \subseteq U\) важе следеће једнакости. Закони долазе у паровима: у левој колони је закон за унију, а у десној одговарајући закон за пресек.

Табела 2.1: Важније особине уније и пресека

Назив	За унију (\(\cup\))	За пресек (\(\cap\))
Комутативност	\(A \cup B = B \cup A\)	\(A \cap B = B \cap A\)
Асоцијативност	\((A \cup B) \cup C = A \cup (B \cup C)\)	\((A \cap B) \cap C = A \cap (B \cap C)\)
Дистрибутивност	\(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)	\(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
Идемпотентност	\(A \cup A = A\)	\(A \cap A = A\)
Апсорпција	\(A \cup (A \cap B) = A\)	\(A \cap (A \cup B) = A\)
Празан и универзални скуп	\(A \cup \emptyset = A\), \(\ A \cup U = U\)	\(A \cap U = A\), \(\ A \cap \emptyset = \emptyset\)
Комплемент	\(A \cup A' = U\)	\(A \cap A' = \emptyset\)
Де Морганови закони	\((A \cup B)' = A' \cap B'\)	\((A \cap B)' = A' \cup B'\)

Поред тога, за комплемент, разлику и инклузију важи:

• комплемент: \(\ \emptyset' = U\), \(\ U' = \emptyset\), \(\ (A')' = A\);
• разлика: \(\ A \setminus B = A \cap B'\), \(\ A \setminus A = \emptyset\), \(\ A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)\);
• инклузија и операције: \(\ A \cap B \subseteq A \subseteq A \cup B\), као и \(\ A \subseteq B \Leftrightarrow A \cup B = B \Leftrightarrow A \cap B = A\).

Принцип дуалности: ако у тачној једнакости истовремено заменимо \(\cup \leftrightarrow \cap\) и \(\emptyset \leftrightarrow U\) (а у инклузији \(\subseteq \leftrightarrow \supseteq\)), поново добијамо тачну једнакост. Зато у табели 2.1 сваки закон у левој колони има свој пар у десној.

Приметимо сличност са законима исказне логике: унија одговара дисјункцији (\(x \in A \cup B\) ако и само ако \(x \in A \lor x \in B\)), пресек конјункцији, а комплемент негацији. Зато свака таутологија исказног рачуна даје по један закон за скупове. На крају поглавља о исказном рачуну видећемо да су и скупови и искази само два примера исте алгебарске структуре — Булове алгебре.

Венов дијаграм на слици 2.4 добро показује зашто важи први Де Морганов закон: област изван оба круга је истовремено изван круга \(A\) и изван круга \(B\).

Слика 2.4: Де Морганов закон \((A \cup B)' = A' \cap B'\)

Кардиналност и принцип укључења–искључења

Кардиналност коначног скупа \(A\) је број његових елемената и означава се са \(|A|\). На пример, \(|\{a, b, c\}| = 3\) и \(|\emptyset| = 0\).

Ако су скупови \(A\) и \(B\) дисјунктни, тј. \(A \cap B = \emptyset\), онда је \(|A \cup B| = |A| + |B|\). Ако нису, сабирањем \(|A| + |B|\) елементе пресека бројимо двапут, па их једном морамо одузети.

Теорема 2.1 (Принцип укључења–искључења) За коначне скупове \(A\), \(B\) и \(C\) важи \[ |A \cup B| = |A| + |B| - |A \cap B|, \] \[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|. \]

Код три скупа елементи који су у тачно два скупа пребројани су двапут и одузети једном, а елементи у сва три скупа пребројани су три пута, одузети три пута и зато још једном додати. Отуда назив: наизменично укључујемо и искључујемо пресеке. Као последица важи и \(|A \setminus B| = |A| - |A \cap B|\).

Кликом на члан формуле укључујете га: сваки члан шрафира свој скуп у својој боји и под својим углом, а одузети чланови су шрафирани испрекиданом линијом. Ознака у свакој области показује колико пута су до сада бројани њени елементи — тиркизна значи тачно једном, магента више пута. Формула је тачна када су све ознаке тиркизне. Изнад ознаке је број елемената у области; за три скупа то су на почетку бројеви из примера који следи (\(A = A_2\), \(B = A_3\), \(C = A_5\)).

Пример 2.1 Колико бројева од 1 до 100 је дељиво са 2, 3 или 5?

Нека је \(A_k\) скуп бројева од 1 до 100 дељивих са \(k\). Тада је \(|A_2| = 50\), \(|A_3| = 33\) и \(|A_5| = 20\). Број је дељив и са 2 и са 3 ако је дељив са 6, па је \(|A_2 \cap A_3| = |A_6| = 16\); слично је \(|A_2 \cap A_5| = |A_{10}| = 10\), \(|A_3 \cap A_5| = |A_{15}| = 6\) и \(|A_2 \cap A_3 \cap A_5| = |A_{30}| = 3\). По принципу укључења–искључења \[ |A_2 \cup A_3 \cup A_5| = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74. \] Број елемената у свакој области Веновог дијаграма приказан је на слици 2.5. Преосталих \(100 - 74 = 26\) бројева није дељиво ни са једним од бројева 2, 3 и 5.

Слика 2.5: Бројеви од 1 до 100 дељиви са 2, 3 и 5: број елемената у свакој области

Партитивни скуп

Партитивни скуп неког скупа \(A\) је скуп свих могућих подскупова скупа \(A\). Означава се са \(\mathcal{P}(A)\). Формално: \[ \mathcal{P}(A) = \{ B \mid B \subseteq A \} \]

Пример: Ако је \(A = \{a, b, c\}\), онда је:

\[ \mathcal{P}(A) = \{ \emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\} \} \]

Ако скуп \(A\) има \(n\) елемената, онда партитивни скуп \(\mathcal{P}(A)\) има \(2^n\) елемената. Сваки подскуп је јединствено одређен комбинацијом избора елемената. За сваки од \(n\) елемената постоје две могућности (узети или не узети), што резултира укупним бројем комбинација \(2^n\). Ово је аналогно бројању у бинарном систему од \(0\) до \(2^n - 1\), где сваки број представља један подскуп.

За претходни пример:

Бинарни низ	Избор елемената (a, b, c)	Подскуп
000	(0, 0, 0)	\(\emptyset\) (празан скуп)
001	(0, 0, 1)	\(\{c\}\)
010	(0, 1, 0)	\(\{b\}\)
011	(0, 1, 1)	\(\{b, c\}\)
100	(1, 0, 0)	\(\{a\}\)
101	(1, 0, 1)	\(\{a, c\}\)
110	(1, 1, 0)	\(\{a, b\}\)
111	(1, 1, 1)	\(\{a, b, c\}\)

Укупно: \(2^3 = 8\) подскупова.

Подскупове можемо сложити по нивоима према броју елемената и повезати сваки подскуп са подскуповима који имају један елемент више. Добија се дијаграм приказан на слици 2.6, у коме се види како се из празног скупа, додавањем по једног елемента, стиже до целог скупа \(A\) (оваквим дијаграмима — Хасеовим дијаграмима — бавићемо се у поглављу о релацијама).

Слика 2.6: Подскупови скупа \(\{a, b, c\}\) уређени инклузијом

Декартов производ

Декартов производ \(n\) скупова \(A_1, A_2, A_3, \dotsc, A_n\) је скуп свих уређених \(n\)-торки где је први елемент из скупа \(A_1\), други из скупа \(A_2\), трећи из \(A_3\), и тако даље, до \(n\)-тог елемента из скупа \(A_n\) тј. \[ A_1 \times A_2 \times A_3 \times \dotsb \times A_n = \{ (a_1, a_2, a_3, \dotsc, a_n) \mid a_1 \in A_1, \ a_2 \in A_2, \ \dotsc, \ a_n \in A_n \} \]

За разлику од скупа, код \(n\)-торке редослед је битан: \((a, b) = (c, d)\) ако и само ако је \(a = c\) и \(b = d\). Зато је \((1, 2) \neq (2, 1)\), иако је \(\{1, 2\} = \{2, 1\}\), а у општем случају је и \(A \times B \neq B \times A\).

Пример 2.2 За скупове \(A_1 = \{1, 2\}\), \(A_2 = \{a, b\}\) и \(A_3 = \{\alpha, \beta\}\) је \[ A_1 \times A_2 \times A_3 = \{ (1, a, \alpha), \ (1, a, \beta), \ (1, b, \alpha), \ (1, b, \beta), \ (2, a, \alpha), \ (2, a, \beta), \ (2, b, \alpha), \ (2, b, \beta) \}. \]

Све уређене тројке можемо систематски набројати помоћу стабла избора (слика 2.7): на првом нивоу бирамо елемент из \(A_1\), на другом из \(A_2\), на трећем из \(A_3\), а сваки пут од корена до листа даје једну тројку.

Слика 2.7: Стабло избора за \(A_1 \times A_2 \times A_3\)

У овом примеру укупно има \(2 \cdot 2 \cdot 2 = 8\) уређених тројки, а у општем случају важи \[ \left| A_1 \times A_2 \times \dotsb \times A_n \right| = |A_1| \cdot |A_2| \cdot \dotsb \cdot |A_n| \]

Релације, функције, операције

Бинарна релација повезује елементе једног скупа са елементима другог скупа по одређеном правилу или својству. Формално, релација \(R\) од скупа \(A\) до скупа \(B\) је подскуп Декартовог производа \(A \times B\). Када је \(A = B\), говоримо о релацији на скупу \(A\).

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

Функција \(f\) из скупа \(A\) у скуп \(B\) је релација која сваком елементу \(a \in A\) придружује тачно један елемент \(b \in B\). У том случају користимо запис \(f: A \to B\). Код релације, један елемент \(a \in A\) може бити повезан са више елемената у \(B\), или ни са једним. У функцији, сваки \(a \in A\) је повезан са тачно једним \(b \in B\).

Скуп \(A\) називамо домен, а скуп \(B\) кодомен функције \(f\). Функције ћемо посматрати из дискретног угла: \(A\) и \(B\) су најчешће коначни скупови, а функцију задајемо таблицом или стрелицама од елемената скупа \(A\) ка елементима скупа \(B\) (слика 2.8).

Функција \(f: A \to B\) је:

• инјекција (или „1–1“) ако различите елементе слика у различите: \(f(a_1) = f(a_2) \Rightarrow a_1 = a_2\);
• сурјекција (или „на“) ако је сваки елемент скупа \(B\) слика неког елемента: за свако \(b \in B\) постоји \(a \in A\) тако да је \(f(a) = b\);
• бијекција ако је истовремено инјекција и сурјекција (обострано једнозначно пресликавање).

Слика 2.8: Инјекција (у сваки елемент скупа \(B\) стиже највише једна стрелица), сурјекција (у сваки стиже бар једна) и бијекција (у сваки стиже тачно једна)

На дијаграму стрелица својства се лако проверавају гледањем у скуп \(B\): код инјекције ни у један елемент не стижу две стрелице, код сурјекције нема елемента у који не стиже ниједна, а код бијекције у сваки елемент стиже тачно једна стрелица.

Пример 2.3  

• Функција \(f: \{0, 1, \dots, 5\} \to \{0, 1, 2\}\), \(f(n) = n \bmod 3\) (остатак при дељењу са 3) јесте сурјекција, јер се сваки остатак 0, 1, 2 појављује, али није инјекција, јер је нпр. \(f(1) = f(4) = 1\).
• Хафманов код из уводног поглавља је инјекција из скупа знакова у скуп низова битова: различити знакови морају имати различите кодове, иначе декодирање не би било могуће. Није сурјекција, јер већина низова битова није код ниједног знака.
• Функција која сваком студенту придружује његов број индекса је бијекција између скупа студената и скупа додељених бројева индекса.

За коначне скупове ова својства су тесно повезана са кардиналношћу:

• ако постоји инјекција \(A \to B\), онда је \(|A| \le |B|\);
• ако постоји сурјекција \(A \to B\), онда је \(|A| \ge |B|\);
• ако постоји бијекција \(A \to B\), онда је \(|A| = |B|\);
• ако је \(|A| = |B|\), онда је функција \(f: A \to B\) инјекција ако и само ако је сурјекција, ако и само ако је бијекција.

Прво својство, изречено обрнуто, познато је као Дирихлеов принцип: ако је \(|A| > |B|\), ниједна функција \(f: A \to B\) није инјекција, тј. бар два елемента скупа \(A\) имају исту слику. Ако у 5 фиока ставимо 6 чарапа, бар у једној фиоци су две чарапе; међу 367 људи бар двоје има рођендан истог дана. Исто важи и за рачунаре: ниједан поступак компресије не може да скрати сваку датотеку, јер низова дужине \(n\) има више него свих краћих низова.

Бијекција омогућава да упоредимо величине скупова и без бројања: два скупа имају исту кардиналност ако између њих постоји бијекција. Тако се појам кардиналности проширује и на бесконачне скупове — на пример, функција \(f(n) = 2n\) је бијекција између природних и парних природних бројева, па ови скупови имају „подједнако много“ елемената.

Број свих функција \(f: A \to B\) коначних скупова је \(|B|^{|A|}\), јер за сваки од \(|A|\) елемената домена бирамо слику на \(|B|\) начина. Отуда и број Булових функција \(n\) промењивих из поглавља о исказном рачуну: то су функције \(\{0,1\}^n \to \{0,1\}\), а њих има \(2^{2^n}\).

Операција дужине \(n\) (\(n\)-арна операција) на скупу \(A\) је било која функција \(f: A^n \to A\), дакле функција која узима \(n\) елемената скупа \(A\) и враћа један елемент истог скупа. Најчешће су бинарне операције (\(n = 2\)), као што су сабирање и множење целих бројева или највећи заједнички делилац, и унарне операције (\(n = 1\)), као што је промена знака броја. И операције са скуповима су операције у овом смислу: унија и пресек су бинарне, а комплемент унарна операција на партитивном скупу \(\mathcal{P}(U)\).

Скупови у програмском језику Python

У програмском језику Python скупови су уграђена структура података која представља неуређену колекцију јединствених елемената: редослед елемената се не чува, па им не можемо приступати индексом. Скупови су променљиви (енгл. mutable): када је скуп једном направљен, у њега можемо додавати нове елементе и из њега уклањати постојеће.

Дефинисање скупа

• Витичасте заграде и набрајање:

A = {1, 2, 3, 4}

• Функција set(), која прави скуп од било које колекције (листе, стринга, торке); понављања се притом губе:

A = set([1, 2, 2, 3, 4])
slova = set("математика")
prazan_skup = set()
print(A, len(slova))

{1, 2, 3, 4} 6

• Set comprehension конструкција, која одговара задавању скупа описом својства, \(\{x \mid x \in \{1, \dots, 10\},\ x \text{ паран}\}\):

A = {x for x in range(1, 11) if x % 2 == 0}
print(A)

{2, 4, 6, 8, 10}

Празан скуп се мора направити функцијом set(), јер {} у Python-у означава празан речник.

Додавање и уклањање елемената

Током извршавања алгоритма често је потребно додавати елементе у скуп и уклањати их из њега. Додавање се врши методом add (ако елемент већ постоји, скуп се не мења), а уклањање методом remove или discard. Обе методе уклањају елемент, али remove пријављује грешку ако елемента нема у скупу, док discard у том случају не ради ништа.

A = {1, 2, 3}
A.add(4)
print(A)
A.remove(2)
print(A)
A.discard(5)      # нема грешке, иако 5 није у скупу
print(A)
# A.remove(5)  ---> KeyError: 5

{1, 2, 3, 4}
{1, 3, 4}
{1, 3, 4}

Провера да ли елемент припада скупу (\(x \in A\)) пише се оператором in и веома је брза: не зависи од величине скупа, јер Python не претражује елементе један по један, већ из самог елемента израчунава где би требало да се налази (хеширање). Зато се скупови користе увек када често проверавамо припадност.

print(3 in A, 2 in A, 2 not in A)

True False True

Из истог разлога елементи скупа морају бити непроменљиви (бројеви, стрингови, торке), па скуп не може садржати листу или други скуп. Ако нам треба скуп скупова, користимо frozenset — непроменљиву верзију скупа:

# {{1, 2}, {3}}  ---> TypeError: unhashable type: 'set'
S = {frozenset({1, 2}), frozenset({3})}
print(frozenset({2, 1}) in S)

True

Релације између скупова

Провера подскупа (метода issubset или оператор <=) и надскупа (метода issuperset или оператор >=):

A = {1, 2}
B = {1, 2, 3}
print(A.issubset(B), A <= B)
print(A.issuperset(B), A >= B)

True True
False False

Прави подскуп и прави надскуп проверавају се операторима < и >, једнакост оператором ==, а дисјунктност методом isdisjoint:

print(A < B, {1, 2, 3} == {3, 2, 1}, A.isdisjoint({3, 4}))

True True True

Операције над скуповима

Свака операција има свој оператор и одговарајућу методу:

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print(A | B, A.union(B))                     # унија
print(A & B, A.intersection(B))              # пресек
print(A - B, A.difference(B))                # разлика
print(A ^ B, A.symmetric_difference(B))      # симетрична разлика

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

Комплемент не постоји као посебна операција, јер Python не зна шта је универзални скуп. Њега задајемо сами, па је \(A' = U \setminus A\):

U = set(range(1, 11))
print(U - A)

{5, 6, 7, 8, 9, 10}

Оператори A | B, A & B, … праве нови скуп, а A и B остају непромењени. Скраћени оператори |=, &=, -= и ^= (као и методе update, intersection_update, …) мењају сам скуп A — то је могуће управо зато што су скупови променљиви:

A = {1, 2, 3, 4}
C = A | {9}      # нови скуп, A се не мења
A |= {9}         # A се мења на месту
print(C, A)

{1, 2, 3, 4, 9} {1, 2, 3, 4, 9}

Примери

Пример 2.4 Ана, Борис и Владимир похађају предмет Дискретне математичке структуре, док Борис, Горан и Дејан похађају предмет Математика 1. Одредити:

1. који студенти похађају оба предмета,
2. који студенти похађају само Математику 1,
3. скуп свих студената који похађају бар један од ова два предмета.

dms = {"Ана", "Борис", "Владимир"}
m1 = {"Борис", "Горан", "Дејан"}

print(dms & m1)            # оба предмета
print(sorted(m1 - dms))    # само Математика 1
print(sorted(dms | m1))    # бар један предмет

{'Борис'}
['Горан', 'Дејан']
['Ана', 'Борис', 'Владимир', 'Горан', 'Дејан']

Пошто скуп не чува редослед, резултат је згодно приказати сортиран (функција sorted враћа листу).

Пример 2.5 Дата је листа бројева у којој се неки елементи понављају. Уклонити дупликате из листе.

brojevi = [5, 1, 2, 2, 3, 5, 4, 4]
print(sorted(set(brojevi)))           # сортирано
print(list(dict.fromkeys(brojevi)))   # редом првог појављивања

[1, 2, 3, 4, 5]
[5, 1, 2, 3, 4]

Претварањем у скуп губи се редослед, па резултат или сортирамо, или користимо речник (dict.fromkeys), који чува редослед уметања.

Пример 2.6 Направити партитивни скуп скупа \(\{a, b, c\}\).

Користимо исту идеју као у табели партитивног скупа: сваки подскуп одређен је низом од \(n\) нула и јединица, где јединица значи да елемент узимамо, а нула да га не узимамо. Све такве низове даје функција product из модула itertools: product([0, 1], repeat=n) бира 0 или 1 на свакој од \(n\) позиција.

from itertools import product

A = ["a", "b", "c"]
for izbor in product([0, 1], repeat=len(A)):
    podskup = {x for x, uzmi in zip(A, izbor) if uzmi == 1}
    print(izbor, sorted(podskup))

(0, 0, 0) []
(0, 0, 1) ['c']
(0, 1, 0) ['b']
(0, 1, 1) ['b', 'c']
(1, 0, 0) ['a']
(1, 0, 1) ['a', 'c']
(1, 1, 0) ['a', 'b']
(1, 1, 1) ['a', 'b', 'c']

Функција zip упарује елементе скупа са битовима низа, па за низ (1, 0, 1) добијамо парове ("a", 1), ("b", 0), ("c", 1) и у подскуп улазе a и c. Добијени редови тачно одговарају редовима табеле партитивног скупа, а има их \(2^3 = 8\).

Пример 2.7 Проверити резултат примера 2.1 директним пребројавањем бројева од 1 до 100 дељивих са 2, 3 или 5.

A2 = {n for n in range(1, 101) if n % 2 == 0}
A3 = {n for n in range(1, 101) if n % 3 == 0}
A5 = {n for n in range(1, 101) if n % 5 == 0}
print(len(A2 | A3 | A5))
print(len(A2) + len(A3) + len(A5) - len(A2 & A3) - len(A2 & A5) - len(A3 & A5) + len(A2 & A3 & A5))

74
74

Оба начина дају 74: први непосредно пребројава унију, а други рачуна по принципу укључења–искључења.

Пример 2.8 Функција \(f(n) = n \bmod 3\) на скупу \(\{0, 1, \dots, 5\}\) задата је речником. Проверити да ли је инјекција и да ли је сурјекција на скуп \(\{0, 1, 2\}\).

Функција је инјекција ако су све њене вредности различите, тј. ако скуп вредности има исто толико елемената колико и домен, а сурјекција ако скуп вредности покрива цео кодомен:

f = {n: n % 3 for n in range(6)}
kodomen = {0, 1, 2}
vrednosti = set(f.values())
print("инјекција:", len(vrednosti) == len(f))
print("сурјекција:", vrednosti == kodomen)

инјекција: False
сурјекција: True

Торке у програмском језику Python

Торка (енгл. tuple) у Python-у је уређени низ вредности — управо \(n\)-торка из Декартовог производа. За разлику од скупа, торка чува редослед и дозвољава понављање елемената, а за разлику од листе, торка је непроменљива (енгл. immutable).

Табела 2.2: Скуп, торка и листа у Python-у

	скуп {…}	торка (…)	листа […]
редослед је битан	не	да	да
понављање елемената	не	да	да
приступ индексом	не	да	да
може да се мења	да	не	да
може бити елемент скупа	не	да	не

Дефинисање торке

• Обичне заграде и набрајање (заграде се могу и изоставити):

tacka = (3, 4)
student = "Пера", "Перић", 2005
print(tacka, student)

(3, 4) ('Пера', 'Перић', 2005)

• Функција tuple(), која прави торку од било које колекције:

t = tuple(["a", "b", "c"])
prazna = tuple()
print(t, prazna)

('a', 'b', 'c') ()

За торку са само једним елементом неопходан је зарез иза елемента: (1,) је торка, а (1) је само број 1 у заградама.

print(type((1,)), type((1)))

<class 'tuple'> <class 'int'>

Приступ елементима

Пошто торка чува редослед, елементима се приступа индексом (бројање почиње од 0, а негативан индекс броји од краја). Као и код скупова, оператор in проверава припадност, а len даје дужину:

t = (10, 20, 30, 20)
print(t[0], t[-1], t[1:3])
print(20 in t, len(t), t.count(20), t.index(30))

10 20 (20, 30)
True 4 2 2

За разлику од скупова, торке се пореде елемент по елемент, па је редослед битан:

print((1, 2) == (2, 1), {1, 2} == {2, 1})

False True

Торке су непроменљиве

Када је торка једном направљена, њени елементи се не могу мењати, нити се могу додавати нови и уклањати постојећи. Зато су торке погодне за податке који треба да остану непромењени, као што су координате тачке или датум.

t = (1, 2, 3)
# t[0] = 5     ---> TypeError: 'tuple' object does not support item assignment
# t.append(4)  ---> AttributeError: 'tuple' object has no attribute 'append'
t2 = t + (4,)    # „измена“ заправо прави нову торку
print(t, t2)

(1, 2, 3) (1, 2, 3, 4)

Непроменљивост има и важну предност: торка може бити елемент скупа или кључ речника, што листа не може. Тако можемо направити скуп тачака или скуп уређених парова — дакле, релацију:

R = {(1, 2), (1, 3), (2, 3)}      # релација „мање“ на {1, 2, 3}
print((1, 3) in R, (3, 1) in R)

True False

Паковање и распакивање торки

Паковање је прављење торке од више вредности, а распакивање је обрнут поступак, у коме се вредности из торке додељују појединачним променљивима:

podaci = "Пера", "Перић", "23.05.1995"     # паковање
ime, prezime, datum_rodjenja = podaci      # распакивање
print(f"Име: {ime}, Презиме: {prezime}")

Име: Пера, Презиме: Перић

Тако се, на пример, вредности две променљиве размењују у једном реду, без помоћне променљиве:

x, y = 10, 20
x, y = y, x
print(x, y)

20 10

Примери

Пример 2.9 Набројати елементе Декартовог производа \(A_1 \times A_2 \times A_3\) из примера 2.2.

Функција product из модула itertools враћа све \(n\)-торке Декартовог производа, у истом редоследу као стабло избора на слици 2.7:

from itertools import product

A1, A2, A3 = [1, 2], ["a", "b"], ["α", "β"]
trojke = list(product(A1, A2, A3))
print(len(trojke))
print(trojke[:3])

8
[(1, 'a', 'α'), (1, 'a', 'β'), (1, 'b', 'α')]

Пример 2.10 Функција може да врати више вредности тако што их спакује у торку. Написати функцију која за скуп бројева враћа најмањи и највећи елемент.

def min_max(S):
    return min(S), max(S)

najmanji, najveci = min_max({7, 3, 9, 1})
print(najmanji, najveci)

1 9

Пример 2.11 Студенти су дати листом торки (име, број поена). Сортирати их по броју поена, од највећег.

studenti = [("Ана", 87), ("Борис", 92), ("Владимир", 78)]
for ime, poeni in sorted(studenti, key=lambda s: s[1], reverse=True):
    print(ime, poeni)

Борис 92
Ана 87
Владимир 78

Распакивање for ime, poeni in ... сваку торку одмах раставља на њене делове.

Задаци

Задаци за ово поглавље, са решењима, налазе се у збирци задатака: Скупови.