Множества и отношения: основные формулы и определения
Основные понятия теории множеств
Множество — неупорядоченная совокупность уникальных элементов. Обычно обозначается заглавными буквами: \( A, B, C \).
Операции над множествами
| Операция | Обозначение | Формула |
|---|---|---|
| Объединение | \( A \cup B \) | \( \{x \mid x \in A \text{ или } x \in B\} \) |
| Пересечение | \( A \cap B \) | \( \{x \mid x \in A \text{ и } x \in B\} \) |
| Разность | \( A \setminus B \) | \( \{x \mid x \in A \text{ и } x \notin B\} \) |
| Дополнение | \( \overline{A} \) | \( \{x \mid x \notin A\} \) |
| Симметрическая разность | \( A \triangle B \) | \( (A \setminus B) \cup (B \setminus A) \) |
| Декартово произведение | \( A \times B \) | \( \{(a, b) \mid a \in A, b \in B\} \) |
Пример: Пусть \( A = \{1, 2, 3, 4\} \), \( B = \{3, 4, 5, 6\} \). \( U = \{1, 2, ..., 7\} \)). Тогда:
- Объединение: \( A \cup B = \{1, 2, 3, 4, 5, 6\} \)
- Пересечение: \( A \cap B = \{3, 4\} \)
- Разность: \( A \setminus B = \{1, 2\} \), \( B \setminus A = \{5, 6\} \)
- Симметрическая разность: \( A \triangle B = \{1, 2, 5, 6\} \)
- Декартово произведение: \( A \times B = \{(1,3), (1,4), ..., (4,6)\} \)
- Дополнение: \( \overline{A} = \{5, 6, 7\} \).
Формулы мощности
- Мощность объединения: \[ |A \cup B| = |A| + |B| - |A \cap B| \]
- Мощность декартова произведения: \[ |A \times B| = |A| \cdot |B| \]
Теорема (о включениях-исключениях для трёх множеств):
\[
|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|
\]
Пример:
В группе из 150 студентов:
- 80 изучают математику (\( |A| \)),
- 60 — физику (\( |B| \)),
- 50 — программирование (\( |C| \)),
- 30 изучают и математику, и физику (\( |A \cap B| \)),
- 20 — математику и программирование (\( |A \cap C| \)),
- 15 — физику и программирование (\( |B \cap C| \)),
- 5 изучают все три предмета (\( |A \cap B \cap C| \)).
Требуется найти, сколько студентов изучают хотя бы один из этих предметов (\( |A \cup B \cup C| \))?
Решение:
\[ \begin{align*} |A \cup B \cup C| &= |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \\ &= 80 + 60 + 50 - 30 - 20 - 15 + 5 \\ &= 130 \text{ студентов.} \end{align*} \]Ответ: 130 студентов изучают хотя бы один предмет. Остальные 20 студентов (из 150) не изучают ни один из перечисленных предметов.
Бинарные отношения
Бинарное отношение между множествами \( A \) и \( B \) — подмножество декартова произведения \( A \times B \).
Свойства отношений
| Свойство | Определение |
|---|---|
| Рефлексивность | \( \forall a \in A \colon (a, a) \in R \) |
| Антирефлексивность | \( \forall a \in A \colon (a, a) \not\in R \) |
| Симметричность | \( \forall a, b \in A \colon (a, b) \in R \Rightarrow (b, a) \in R \) |
| Транзитивность | \( \forall a, b, c \in A \colon (a, b) \in R \land (b, c) \in R \Rightarrow (a, c) \in R \) |
| Антисимметричность | \( \forall a, b \in A \colon (a, b) \in R \land (b, a) \in R \Rightarrow a = b \) |
Виды отношений
- Эквивалентность — рефлексивное, симметричное и транзитивное отношение.
- Частичный порядок — рефлексивное, антисимметричное и транзитивное отношение.
- Строгий порядок — антирефлексивное, антисимметричное и транзитивное отношение.
Пример: Отношение "делится нацело" на множестве натуральных чисел — частичный порядок.
Матрица отношения
Если \( A = \{a_1, a_2, \dots, a_n\} \), то отношение \( R \) можно задать матрицей \( M \) размером \( n \times n \), где:
\[ M_{ij} = \begin{cases} 1, & \text{если } (a_i, a_j) \in R, \\ 0, & \text{иначе}. \end{cases} \]
Пример: Пусть \( A = \{1, 2, 3\} \), отношение \( R = \{(1,1), (1,2), (2,3), (3,1)\} \). Тогда матрица \( M_R \):
\[
M_R = \begin{pmatrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0 \\
\end{pmatrix}
\]
Так как \( (1,1) \in R \Rightarrow M_{11} = 1 \), а \( (3,2) \notin R \Rightarrow M_{32} = 0 \).
Пример: Отношение "меньше или равно" на \( A = \{1, 2, 3\} \):
\[
R = \{(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)\}
\]
Матрица:
\[
M_R = \begin{pmatrix}
1 & 1 & 1 \\
0 & 1 & 1 \\
0 & 0 & 1 \\
\end{pmatrix}
\]
Обратное отношение
Определение: Для отношения \( R \subseteq A \times B \) обратное отношение \( R^{-1} \subseteq B \times A \) — это множество пар:
\[
R^{-1} = \{(b, a) \mid (a, b) \in R\}.
\]
Свойства обратного отношения:
- \( (R^{-1})^{-1} = R \),
- Если \( R \) — рефлексивно, то \( R^{-1} \) тоже рефлексивно,
- Если \( R \) — биекция, то \( R^{-1} \) — тоже биекция.
Пример: Пусть \( R = \{(1, x), (2, y), (3, x)\} \) (из \( A = \{1, 2, 3\} \) в \( B = \{x, y\} \)). Тогда:
\[
R^{-1} = \{(x, 1), (y, 2), (x, 3)\}.
\]
Композиция отношений
Если \( R \subseteq A \times B \) и \( S \subseteq B \times C \), то их композицией называется отношение \( Q \subseteq A \times C \):
\[ Q=S \circ R = \{(a, c) \mid \exists b \in B \colon (a, b) \in R \land (b, c) \in S\} \]Композиция отношений - некоммутативная операция: в общем случае \(S \circ R \ne R \circ S\)
Пример: Пусть \( R \) и \( S \) — отношения на \( A = \{1, 2, 3\} \):
- \( R = \{(1, 2), (2, 3)\} \),
- \( S = \{(2, 1), (3, 1)\} \).
Тогда \( S \circ R \):
\[
S \circ R = \{(1, 1), (2, 1)\}
\]
Проверка: - \( (1, 2) \in R \) и \( (2, 1) \in S \) даёт \( (1, 1) \), - \( (2, 3) \in R \) и \( (3, 1) \in S \) даёт \( (2, 1) \).
Пример: Пусть даны три множества и два отношения:
- \( A = \{a, b, c\} \), \( B = \{1, 2, 3\} \), \( C = \{x, y, z\} \),
- \( R \subseteq A \times B = \{(a, 1), (a, 2), (b, 3), (c, 1)\} \),
- \( S \subseteq B \times C = \{(1, y), (2, x), (3, y), (3, z)\} \).
Найдём композицию \( S \circ R \):
Для каждого элемента \( (a_i, b_j) \in R \) ищем пары \( (b_j, c_k) \in S \):
- Для \( (a, 1) \in R \):
Находим \( (1, y) \in S \) → добавляем \( (a, y) \) в результат. - Для \( (a, 2) \in R \):
Находим \( (2, x) \in S \) → добавляем \( (a, x) \). - Для \( (b, 3) \in R \):
Находим \( (3, y) \) и \( (3, z) \in S \) → добавляем \( (b, y) \) и \( (b, z) \). - Для \( (c, 1) \in R \):
Находим \( (1, y) \in S \) → добавляем \( (c, y) \).
Получаем
\[ S \circ R = \{(a, x), (a, y), (b, y), (b, z), (c, y)\} \]