# 2. Методичні вказівки

Цей розділ **самодостатній**: у ньому зібрано всю теорію, потрібну для теми —
скінченні множини, їхні операції, діаграми Венна, закони алгебри множин і
множина-ступінь, — разом із прийомами, якими розв'язують завдання з
[3task.md](3task.md). Наприкінці розібрано **демонстраційний** приклад доведення
тотожності діаграмами Венна на даних, **відмінних** від будь-якого варіанта, —
щоб показати метод, не розв'язуючи жодного варіанта. Зовнішні джерела не потрібні;
ширше й з доведеннями ту саму теорію викладено в
[Лекції 1](../../Lectures/ODM-L01.md).

## 2.1 Множини та способи задання

**Множина** — це невпорядкована сукупність **різних** об'єктів, які називають її
**елементами**. Пишуть $x \in A$, якщо $x$ — елемент $A$, і $x \notin A$ інакше.
Множину визначає лише те, *які* елементи вона містить, тож справджуються дві
властивості:

- **несуттєвість повторень** — $\{1,2,2,3\} = \{1,2,3\}$;
- **несуттєвість порядку** — $\{1,2,3\} = \{3,1,2\}$.

Є два стандартні способи задати множину:

- **переліком (списком)** — елементи виписують у фігурних дужках:
  $A = \{1, 3, 5\}$;
- **характеристичною властивістю (предикатом)** — вказують умову $P(x)$, якій
  мають задовольняти елементи, майже завжди з областю $U$, з якої беруть $x$:
  $$ A = \{\, x \in U \mid P(x) \,\} \qquad (\text{«усі } x \text{ з } U \text{, для яких } P(x)\text{»}). $$

Щоб перейти від **властивості** до **переліку**, перебирають кандидатів з області
й лишають ті, що проходять перевірку умовою. Наприклад,
$\{\, x \mid x \in \mathbb{N},\ x < 6,\ x \bmod 2 = 0 \,\}$: кандидати
$1,2,3,4,5$; парними серед менших за $6$ є $2$ і $4$, тож множина дорівнює
$\{2, 4\}$.

Корисні позначення: **натуральні числа** $\mathbb{N} = \{1, 2, 3, \dots\}$ (у
цьому курсі без нуля), **порожня множина** $\varnothing = \{\,\}$, яка не має
жодного елемента, і **потужність** $|A|$ — кількість різних елементів $A$
(зокрема $|\varnothing| = 0$).

**Підмножина й рівність.** Запис $A \subseteq B$ означає, що кожен елемент $A$ є
й елементом $B$. Дві множини **рівні**, $A = B$, саме тоді, коли мають однакові
елементи, тобто коли одночасно $A \subseteq B$ **і** $B \subseteq A$. Цей принцип
«двох включень» — один зі способів довести тотожність (§2.6).

**Універсальна множина.** У багатьох задачах наперед фіксують множину $U$ **всіх**
розглядуваних об'єктів — **універсум**. Саме відносно нього беруть **доповнення**
(§2.2); на діаграмі універсум — це обмежувальний прямокутник.

## 2.2 Операції над множинами

Нехай $A$ і $B$ — множини всередині універсуму $U$.

| Операція | Позначення | Означення | Приклад |
|---|:--:|---|---|
| **Об'єднання** | $A \cup B$ | $\{\, x : x \in A \text{ або } x \in B \,\}$ | $\{1,2,3\}\cup\{3,4\}=\{1,2,3,4\}$ |
| **Перетин** | $A \cap B$ | $\{\, x : x \in A \text{ і } x \in B \,\}$ | $\{1,2,3\}\cap\{3,4\}=\{3\}$ |
| **Різниця** | $A \setminus B$ | $\{\, x : x \in A \text{ і } x \notin B \,\}$ | $\{1,2,3\}\setminus\{3,4\}=\{1,2\}$ |
| **Доповнення** | $\overline{A}$ | $U \setminus A = \{\, x \in U : x \notin A \,\}$ | $\overline{\{1,2\}}=\{3,4,5\}$, якщо $U=\{1,\dots,5\}$ |

![Чотири операції над двома множинами на діаграмах Венна: об'єднання, перетин та обидві різниці](img/p1_venn_ops.png)

Два факти, якими користуються постійно:

- **Доповнення відносне.** $\overline{A}$ не має сенсу без універсуму; завжди
  спершу вказуйте $U$.
- **Різниця напрямлена.** Загалом $A \setminus B \ne B \setminus A$ (див. рисунок:
  заштриховано різні «серпики»). Множини з $A \cap B = \varnothing$ називають
  **неперетинними**.

Найкорисніший місток між операціями:

$$ A \setminus B = A \cap \overline{B}, $$

тобто «усе в $A$, чого немає в $B$» дорівнює «$A$ у перетині з доповненням $B$».
Саме він переводить різницю в перетин і доповнення, на чому тримаються алгебраїчні
доведення.

## 2.3 Діаграми Венна: області та штрихування

**Діаграма Венна** зображує кожну множину колом усередині прямокутника $U$ так,
щоб було показано **всі можливі перетини**. Для двох множин — чотири області; для
трьох — вісім:

- **Дві множини** $A, B$: *лише $A$* ($A \setminus B$), *перетин* ($A \cap B$),
  *лише $B$* ($B \setminus A$) і *поза обома* ($\overline{A \cup B}$).
- **Три множини** $A, B, C$: три «пелюстки» лише-$A$, лише-$B$, лише-$C$; три
  попарні «лінзи» $A \cap B$, $A \cap C$, $B \cap C$; центральна область
  $A \cap B \cap C$ і зовнішня область.

**Як заштрихувати вираз (зсередини назовні).** Щоб зобразити область, яку задає
формула, обчислюють її, як арифметичний вираз, — спершу найглибшу операцію:

1. на чернетці заштриховують кожен підвираз у дужках;
2. комбінують: **об'єднання** зафарбовує *обидві* області; **перетин** лишає лише
   *спільну* частину; **різниця** $X \setminus Y$ лишає частину $X$ *поза* $Y$;
   **доповнення** зафарбовує все *поза* областю.

Наприклад, щоб заштрихувати $A \setminus (B \cup C)$: спершу штрихують $B \cup C$
(обидва відповідні кола), а потім лишають тільки ту частину $A$, що опинилася
**поза** заштрихованим.

**Як прочитати формулу з діаграми.** Заштриховану область називають найпростішою
комбінацією кіл, що її дає, — наприклад, «частини $A$ і $B$, але не $C$» читаються
як $(A \cup B) \setminus C$.

## 2.4 Закони алгебри множин

Операції підпорядковані алгебраїчним законам. Вони дають змогу спрощувати вирази
та перевіряти тотожності символьними перетвореннями, без рисунка.

| Закон | Формулювання |
|---|---|
| Комутативність | $A \cup B = B \cup A,\quad A \cap B = B \cap A$ |
| Асоціативність | $(A \cup B) \cup C = A \cup (B \cup C)$, і так само для $\cap$ |
| Дистрибутивність | $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$; двоїсто $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ |
| Одиниці / нулі | $A \cup \varnothing = A,\ A \cap U = A,\ A \cup U = U,\ A \cap \varnothing = \varnothing$ |
| Доповнення | $A \cup \overline{A} = U,\quad A \cap \overline{A} = \varnothing,\quad \overline{\overline{A}} = A$ |
| Поглинання | $A \cup (A \cap B) = A,\quad A \cap (A \cup B) = A$ |
| Закони де Моргана | $\overline{A \cup B} = \overline{A} \cap \overline{B},\quad \overline{A \cap B} = \overline{A} \cup \overline{B}$ |
| Різниця | $A \setminus B = A \cap \overline{B}$ |

Особливо важливі **закони де Моргана** (доповнення об'єднання/перетину змінює
операцію на протилежну й доповнює частини) та закон **різниці** — разом вони
роблять більшу частину роботи в доведеннях. З них випливають і корисні
тотожності для різниці, як-от $A \setminus (B \cup C) = (A \setminus B) \cap
(A \setminus C)$ та $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$.

## 2.5 Множина-ступінь

**Множина-ступінь** $\mathcal{P}(A)$ — це множина **всіх підмножин** $A$,
включно з порожньою множиною $\varnothing$ і самою $A$. Кожен елемент $A$
незалежно або **входить**, або **не входить** до конкретної підмножини, тож
$n$-елементна множина має

$$ |\mathcal{P}(A)| = 2^{|A|} $$

підмножин. Зокрема, для чотириелементної множини підмножин рівно
$2^{4} = 16$.

**Як виписати множину-ступінь без пропусків — за розміром.** Підмножини
перелічують **групами за кількістю елементів**: спершу $\varnothing$ (розмір $0$),
потім усі одноелементні, далі всі двоелементні й так до самої $A$. Кількість
підмножин розміру $k$ дорівнює числу сполучень $C_{n}^{k}$; для $n = 4$ це
$1, 4, 6, 4, 1$, а їхня сума

$$ C_4^0 + C_4^1 + C_4^2 + C_4^3 + C_4^4 = 1 + 4 + 6 + 4 + 1 = 16 = 2^{4} $$

слугує зручною **самоперевіркою**: якщо виписано не $16$ різних підмножин — десь
пропуск або повтор.

![Підмножини чотириелементної множини за розміром: кількості 1, 4, 6, 4, 1 у сумі дають 2⁴ = 16](img/p1_powerset_sizes.png)

> **Демонстраційний приклад (інші дані, ніж у варіантах).** Випишемо
> $\mathcal{P}(A)$ для **триелементної** множини $A = \{p, q, r\}$. За розміром:
>
> - розмір $0$: $\varnothing$ — $1$ підмножина;
> - розмір $1$: $\{p\},\ \{q\},\ \{r\}$ — $3$ підмножини;
> - розмір $2$: $\{p,q\},\ \{p,r\},\ \{q,r\}$ — $3$ підмножини;
> - розмір $3$: $\{p,q,r\}$ — $1$ підмножина.
>
> Разом $1 + 3 + 3 + 1 = 8 = 2^{3}$, як і має бути. Отже,
> $$ \mathcal{P}(\{p,q,r\}) = \big\{\, \varnothing,\ \{p\}, \{q\}, \{r\},\ \{p,q\}, \{p,r\}, \{q,r\},\ \{p,q,r\} \,\big\}. $$
> У завданні 2 множина містить **чотири** елементи, тож діяти треба так само, але
> з рядком розмірів $1, 4, 6, 4, 1$ і $16$ підмножинами.

## 2.6 Як довести тотожність діаграмами Венна

Щоб довести рівність двох теоретико-множинних виразів **діаграмами Венна**,
виконують три кроки:

1. на одній діаграмі заштриховують область **лівої** частини рівності (зсередини
   назовні, §2.3);
2. на другій, **такій самій**, діаграмі заштриховують область **правої** частини;
3. якщо заштриховані області **повністю збігаються**, вирази задають одну множину,
   тобто рівність доведено; якщо ж знайдеться область, зафарбована лише на одній
   діаграмі, — рівність **хибна** (і діаграма одразу дає контрприклад).

Для виразів із трьома множинами беруть діаграму з трьох кіл (вісім областей); з
двома — з двох кіл.

> **Демонстрація методу (на інших даних, ніж будь-який варіант).** Доведемо
> **дистрибутивний** закон
> $$ A \cup (B \cap C) = (A \cup B) \cap (A \cup C). $$
> Цієї рівності серед варіантів завдання 3 немає — вона слугує лише зразком
> оформлення.

**Ліва частина** $A \cup (B \cap C)$. Спершу штрихуємо $B \cap C$ — центральну
«лінзу» кіл $B$ і $C$ (обидві її частини: усередині $A$ й поза ним). Потім
об'єднуємо з усім колом $A$. Результат — усе коло $A$ разом із лінзою $B \cap C$:

![Побудова лівої частини: коло A, потім перетин B ∩ C, і нарешті їхнє об'єднання A ∪ (B ∩ C)](img/p1_proof_lhs.png)

**Права частина** $(A \cup B) \cap (A \cup C)$. Окремо штрихуємо $A \cup B$
(кола $A$ і $B$) та $A \cup C$ (кола $A$ і $C$), після чого лишаємо тільки
**спільну** для них частину:

![Побудова правої частини: A ∪ B, потім A ∪ C, і нарешті їхній перетин (A ∪ B) ∩ (A ∪ C)](img/p1_proof_rhs.png)

Порівнюємо крайні праві діаграми обох рядків: заштриховані області **збігаються** —
це коло $A$ разом із лінзою $B \cap C$. Отже,
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$, що й треба було довести.
$\blacksquare$

Так само оформлюють доведення свого варіанта: дві діаграми, підписані частини,
однозначний висновок про збіг (чи розбіг) заштрихованих областей.

## 2.7 Робочий контрольний список

- Множини записуйте в **сталому порядку** (наприклад, зростання), щоб рівні
  множини було легко порівнювати, хоча формально порядок і не має значення.
- Перед будь-яким **доповненням** випишіть універсум $U$.
- Для завдання-діаграми штрихуйте **зсередини назовні** й підписуйте кінцеву
  область.
- Для множини-ступеня перелічуйте підмножини **за розміром** і перевіряйте
  кількість числом $2^{|A|}$.
- Для переходу від властивості до переліку перетворіть умову на **перевірку**,
  застосовану до кожного кандидата з області, і зберіть ті, що її проходять.