Множини, відношення та функції: задачі з покроковими розв’язками

Q: Множини, відношення та функції: що це?

На діаграмі Вена два кола ділять U на чотири області: лише A, обидві, лише B і жодна. Кожен множинний вираз — це об’єднання деяких із цих областей, тож його завжди можна порахувати область за областю. Тут |A| = 12 + 5 = 17, |A ∩ B| = 5, |A ∪ B| = 12 + 5 + 8 = 25 і |(A ∪ B)′| = 15.

Q: Множини, відношення та функції: що ви тренуєте?

Легка: діаграми Вена та підмножини Середня: включення–виключення та відношення Складна: функції та підрахунок Кожна задача має нові значення, тож ви вивчаєте метод, а не відповідь. Застрягли? Спершу відкрийте невелику підказку, а повне пояснення — лише коли воно знадобиться.

Безкоштовні задачі з теми Множини, відношення та функції з рисунками, підказками й повними розв’язками. Щоразу нові значення, трьох рівнів: діаграми Вена та підмножини, включення–виключення та відношення, функції та підрахунок.

Безкоштовна задачаЛегка

Нехай A = {b, e} і B = {1, 2}. Знайдіть |A × B|.

A = {b, e}B = {1, 2}

Точна відповідь: ціле число, без округлення.

Наступна задача →

Тренуйтеся безкоштовно: Множини, відношення та функції Тренуйтеся зараз: Множини, відношення та функціїБезкоштовних задач щодня: 5. Без картки.

Що ви тренуєте

Легкадіаграми Вена та підмножини
Середнявключення–виключення та відношення
Складнафункції та підрахунок

Як розв’язувати задачі на тему «Множини, відношення та функції»

Намалюйте діаграму Вена й вирішіть область за областю, що належить множинному виразу.
У задачах на підрахунок заповнюйте області від центру назовні: спочатку всі множини, потім пари, потім окремі множини, потім зовнішню частину.
Використовуйте принцип включення–виключення для перевірки: |A ∪ B| = |A| + |B| − |A ∩ B|.
Для відношення перевіряйте кожну властивість на кожній парі й наводьте один контрприклад, коли вона не виконується.
Для функції порахуйте стрілки, що приходять до кожного елемента B: не більше однієї означає ін’єктивність, щонайменше одна — сюр’єктивність.

Типові помилки

Додавати |A| і |B|, не віднімаючи перетин.
Забути додати назад центр для трьох множин.
Переставити показник у кількості функцій: nᵐ для m елементів у n.
Застосовувати g ∘ f у неправильному порядку: першою діє f.
Забути пари (x, x) під час підрахунку пар відношення еквівалентності.

Основні формули

Дві множини: |A ∪ B| = |A| + |B| − |A ∩ B|
Три множини: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Різниця та доповнення: A − B = A ∩ B′, |A′| = |U| − |A|
Булеан і декартів добуток: |𝒫(A)| = 2^|A|, |A × B| = |A|·|B|
Підмножини розміру k: C(n, k) = n!/(k!(n − k)!)
Функції A → B: nᵐ; injective n!/(n − m)!; surjective Σ (−1)ᵏ C(n, k)(n − k)ᵐ
Відношення на n елементах: 2^n²; reflexive 2^{n² − n}; symmetric 2^n(n+1)/2
Композиція: (g ∘ f)(x) = g(f(x))

Вивчайте тему «Множини, відношення та функції» з нуля

Перед цим: Логіка висловлювань і доведення

1Множини та операції над множинами

Множина — це набір різних елементів: A = {1, 2, 3}. Порядок і повторення не мають значення. |A| — кількість елементів, а U — універсальна множина, що містить усе, про що йдеться.

A ∪ B (об’єднання): елементи з A, або з B, або з обох.
A ∩ B (перетин): елементи, що належать обом.
A − B (різниця): елементи A, яких немає в B.
A′ (доповнення): елементи U, яких немає в A.

На діаграмі Вена два кола ділять U на чотири області: лише A, обидві, лише B і жодна. Кожен множинний вираз — це об’єднання деяких із цих областей, тож його завжди можна порахувати область за областю.

Тут |A| = 12 + 5 = 17, |A ∩ B| = 5, |A ∪ B| = 12 + 5 + 8 = 25 і |(A ∪ B)′| = 15.

Самоперевірка Скільки елементів має A − B на діаграмі вище?

Відповідь: 12. A − B залишає частину A поза B: лише область із 12. П’ять елементів у перетині належать і B, а 17 — це вся A.

2Підрахунок за принципом включення–виключення

Додавання |A| і |B| рахує перетин двічі, тож відніміть його один раз:

|A ∪ B| = |A| + |B| − |A ∩ B|

Для трьох множин віднімають попарні перетини, але тоді центр було вилучено тричі, тож його додають назад:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

У текстових задачах зазвичай надійніше заповнювати діаграму Вена від центру назовні: спочатку елементи в усіх трьох множинах, потім кожна пара мінус центр, потім кожна окрема множина мінус те, що вже розміщено.

Ще два підрахунки трапляються часто: множина з n елементів має 2ⁿ підмножин (її булеан 𝒫(A)), а |A × B| = |A|·|B| впорядкованих пар.

Самоперевірка З 40 студентів 25 вивчають французьку, 18 — німецьку, а 9 — обидві. Скільки не вивчають жодної?

Відповідь: 6. |F ∪ G| = 25 + 18 − 9 = 34, тож 40 − 34 = 6 не вивчають жодної. Якщо забути відняти 9, вийде 43, що більше за всю групу.

3Розв’язаний приклад

Простежте кожен крок. Спробуйте передбачити наступний, перш ніж його відкрити.

Розв’язаний приклад

З 60 студентів 30 склали математику (M), 25 — фізику (P) і 20 — хімію (C). 10 склали M і P, 8 склали M і C, 6 склали P і C, а 3 склали всі три. Скільки не склали жодного?

Центр

3 склали всі три.

Лише пари

Лише M і P: 10 − 3 = 7. Лише M і C: 8 − 3 = 5. Лише P і C: 6 − 3 = 3.

Лише окремі

Лише M: 30 − 7 − 5 − 3 = 15. Лише P: 25 − 7 − 3 − 3 = 12. Лише C: 20 − 5 − 3 − 3 = 9.

Об’єднання і доповнення

|M ∪ P ∪ C| = 15 + 12 + 9 + 7 + 5 + 3 + 3 = 54

Формула дає те саме: 30 + 25 + 20 − 10 − 8 − 6 + 3 = 54.

Відповідь

60 − 54 = 6 студентів не склали жодного з трьох.

4Відношення

Відношення R на множині X — це множина впорядкованих пар (x, y), де x і y належать X. Якщо зобразити його орієнтованим графом, кожна пара — це стрілка, а (x, x) — петля.

Рефлексивне: (x, x) ∈ R для кожного x: петля в кожній вершині.
Симетричне: (x, y) ∈ R завжди супроводжується (y, x) ∈ R.
Антисиметричне: (x, y) і (y, x) одночасно належать R лише тоді, коли x = y.
Транзитивне: (x, y) і (y, z) в R тягнуть за собою (x, z) ∈ R.

Відношення, яке рефлексивне, симетричне й транзитивне, — це відношення еквівалентності. Воно розбиває X на неперетинні класи, наприклад на залишки 0, 1 і 2 для «x ≡ y (mod 3)». Клас із s елементів дає s² впорядкованих пар.

Щоб спростувати властивість, достатньо одного контрприкладу; щоб довести її, перевірте кожну пару.

Самоперевірка R = {(1, 2), (2, 3)} на {1, 2, 3}. Яку пару треба додати, щоб R стало транзитивним?

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

Відповідь: (1, 3). (1, 2) і (2, 3) належать R, тож транзитивність вимагає (1, 3). Пара (2, 1) потрібна була б для симетричності, а (1, 1) — для рефлексивності.

5Функції

Функція f: A → B дає кожному елементу A рівно один образ у B.

Ін’єктивна (один до одного): різні елементи мають різні образи; жоден елемент B не отримує двох стрілок.
Сюр’єктивна (на): кожен елемент B отримує принаймні одну стрілку.
Бієктивна: обидва. Лише тоді f має обернену f⁻¹.

Функція на рисунку ін’єктивна, але не сюр’єктивна: d не отримує жодної стрілки. Для ін’єкції потрібно |A| ≤ |B|, а для сюр’єкції — |A| ≥ |B|.

За |A| = m і |B| = n існує nᵐ функцій і n!/(n − m)! ін’єктивних. Композиція (g ∘ f)(x) = g(f(x)) спершу застосовує f.

Самоперевірка Скільки існує функцій із множини з 3 елементів у множину з 4 елементів?

Відповідь: 64. Кожен із 3 елементів обирає один із 4 образів: 4³ = 64. Число 3⁴ = 81 міняє ролі місцями, 24 = 4·3·2 рахує лише ін’єктивні функції, а 12 = 3·4 — розмір A × B.

6Типові помилки

Додавати |A| + |B|, не віднімаючи перетин.
Забувати додати назад центр у принципі включення–виключення для трьох множин.
Писати mⁿ замість nᵐ для кількості функцій із m елементів у n елементів.
Думати, що відношення не може бути одночасно симетричним і антисиметричним: відношення {(1, 1)} є обома.
Застосовувати g ∘ f у неправильному порядку: першою діє f.

7Як виглядають екзаменаційні запитання

Легкий: діаграми Вена та підмножини. Ви рахуєте множинний вираз за діаграмою Вена, клікаєте область виразу або знаходите розмір булеана, декартового добутку чи сімейства підмножин.
Середній: включення–виключення та відношення. Ви розв’язуєте задачі на підрахунок для двох і трьох множин, рахуєте вирази за сумами областей, визначаєте, яку властивість має відношення, або рахуєте пари, потрібні для замикання.
Складний: функції та підрахунок. Ви класифікуєте функцію як ін’єктивну, сюр’єктивну чи бієктивну, рахуєте функції, ін’єкції та сюр’єкції, обчислюєте композиції й обернені та рахуєте пари у відношеннях еквівалентності.

Вивчайте крок за кроком у застосунку Вивчайте крок за кроком у застосунку

Розв’язані приклади

Приклад 1Легка

Нехай A = {a, b, c, x, y} і B = {1, 2, 3, 4}. Знайдіть |𝒫(A)|.

A = {a, b, c, x, y}B = {1, 2, 3, 4}

Знайти: |𝒫(A)|

Показати підказки

Множина з k елементів має 2ᵏ підмножин: кожен елемент або входить у підмножину, або ні.
|A| = 5, |B| = 4.
|𝒫(A)| = 2^|A|.

Показати відповідь і покроковий розв’язок

Функції та підрахунок: функція f: A → B дає кожному елементу A рівно один образ у B. f ін’єктивна (один до одного), коли різні елементи мають різні образи, сюр’єктивна (на), коли кожен елемент B є образом, і бієктивна, коли виконується і те, і те. За |A| = m і |B| = n існує nᵐ функцій, n!/(n − m)! ін’єктивних (m ≤ n), а за принципом включення–виключення Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ сюр’єктивних. |𝒫(A)| = 2ᵐ і |A × B| = m·n.

Розміри

|A| = 5

|B| = 4

Порахуйте

|𝒫(A)| = 2⁵ = 32

Відповідь

|𝒫(A)| = 32

Приклад 2Середня

З 53 студентів першого курсу 35 склали математику (M), 28 склали фізику (P) і 29 склали хімію (C). 20 склали M і P, 18 склали M і C, 10 склали P і C, а 6 склали всі три. Скільки не входять до жодної з трьох множин?

|U| = 53

Знайти: |(M ∪ P ∪ C)′|

Показати підказки

Заповнюйте діаграму Вена від центру назовні: спочатку всі три, потім пари, потім окремі множини.
Лише M і P (не C): 20 − 6 = 14. Лише M: 35 − 14 − 12 − 6 = 3.
Принаймні одна множина: 35 + 28 + 29 − 20 − 18 − 10 + 6 = 50.

Показати відповідь і покроковий розв’язок

Множини та діаграми Вена: A ∪ B містить елементи з A або B (або з обох), A ∩ B — елементи з обох, A − B — елементи A, яких немає в B, а доповнення A′ — усе в U, чого немає в A. На діаграмі Вена кожен множинний вираз — це об’єднання областей, тож рахуйте його область за областю. Включення–виключення: |A ∪ B| = |A| + |B| − |A ∩ B| і |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Центр і пари

M ∩ P ∩ C: 6

M ∩ P лише: 20 − 6 = 14

M ∩ C лише: 18 − 6 = 12

P ∩ C лише: 10 − 6 = 4

Окремі множини

M лише: 35 − 14 − 12 − 6 = 3

P лише: 28 − 14 − 4 − 6 = 4

C лише: 29 − 12 − 4 − 6 = 7

Відповідь

|M ∪ P ∪ C| = 50

|(M ∪ P ∪ C)′| = 53 − 50 = 3

Відповідь

|(M ∪ P ∪ C)′| = 3

Приклад 3Складна

Функції f і g на {1, 2, 3, 4, 5} задано таблицями. Знайдіть (f ∘ g)(5).

f: 1 ↦ 1, 2 ↦ 3, 3 ↦ 2, 4 ↦ 3, 5 ↦ 4g: 1 ↦ 5, 2 ↦ 1, 3 ↦ 5, 4 ↦ 4, 5 ↦ 1

Знайти: (f ∘ g)(5)

Показати підказки

(f ∘ g)(x) означає f(g(x)): спершу g, потім f.
Внутрішнє значення — g(5) = 1.
Тепер застосуйте зовнішню функцію до 1.

Показати відповідь і покроковий розв’язок

Внутрішня функція

g(5) = 1

Зовнішня функція

f(1) = 1

(f ∘ g)(5) = 1

Відповідь

(f ∘ g)(5) = 1

Запитання й відповіді

Множини, відношення та функції: що це?

Тут |A| = 12 + 5 = 17, |A ∩ B| = 5, |A ∪ B| = 12 + 5 + 8 = 25 і |(A ∪ B)′| = 15.

Множини, відношення та функції: як розв’язувати задачі крок за кроком?

Намалюйте діаграму Вена й вирішіть область за областю, що належить множинному виразу.
У задачах на підрахунок заповнюйте області від центру назовні: спочатку всі множини, потім пари, потім окремі множини, потім зовнішню частину.
Використовуйте принцип включення–виключення для перевірки: |A ∪ B| = |A| + |B| − |A ∩ B|.
Для відношення перевіряйте кожну властивість на кожній парі й наводьте один контрприклад, коли вона не виконується.
Для функції порахуйте стрілки, що приходять до кожного елемента B: не більше однієї означає ін’єктивність, щонайменше одна — сюр’єктивність.

Множини, відношення та функції: які помилки найпоширеніші?

Додавати |A| і |B|, не віднімаючи перетин.
Забути додати назад центр для трьох множин.
Переставити показник у кількості функцій: nᵐ для m елементів у n.
Застосовувати g ∘ f у неправильному порядку: першою діє f.
Забути пари (x, x) під час підрахунку пар відношення еквівалентності.

Множини, відношення та функції: що ви тренуєте?

Легка: діаграми Вена та підмножини
Середня: включення–виключення та відношення
Складна: функції та підрахунок

Кожна задача має нові значення, тож ви вивчаєте метод, а не відповідь. Застрягли? Спершу відкрийте невелику підказку, а повне пояснення — лише коли воно знадобиться.

Як проходить тренування

Кожна задача має нові значення, тож ви вивчаєте метод, а не відповідь.
Застрягли? Спершу відкрийте невелику підказку, а повне пояснення — лише коли воно знадобиться.
Ваш прогрес, помилки та збережені задачі зберігаються, тож перед іспитом ви зможете все повторити.

Теми до і після цієї

Спочатку вивчіть

Логіка висловлювань і доведення

Далі

Теорія графів

Курси з цією темою

Дискретна математика

Інші теми: Математика і статистика

Границі Похідні Оптимізація Інтеграли Послідовності та ряди Диференціальне числення функцій багатьох змінних Диференціальні рівняння Комплексні числа Чисельні методи Матриці та визначники Вектори: скалярний і векторний добутки Логіка висловлювань і доведення Теорія графів Теорія чисел і арифметика за модулем Імовірність Описова статистика Нормальний розподіл Довірчі інтервали Перевірка гіпотез і довірчі інтервали Лінійна регресія та кореляція Критерії хі-квадрат

Робочий аркуш для друку

Робочий аркуш «Множини, відношення та функції» з відповідями