Посібник “Математична скарбничка задач з комбінаторики”

Матеріал даного посібника можна використати для проведення уроків в 11 класі, а також для самоосвіти учнів, які бажають добре орієнтуватися в темі «Комбінаторика».

У посібнику міститься теоретичний матеріал, приклади з розв’язками, тести, завдання для домашніх робіт, інтегрована вікторина, різнорівнева самостійна робота, контрольна робота, завдання для майбутнього абітурієнта.

Хухрянська ЗОШ І-ІІІ ступенів
Матеріал даного посібника можна використати для проведення уроків в 11 класі, а також для самоосвіти учнів, які бажають добре орієнтуватися в темі «Комбінаторика».

У посібнику міститься теоретичний матеріал, приклади з розв’язками, тестові завдання, приклади для виконання домашньої роботи, інтегрована вікторина, різнорівнева самостійна робота, контрольна робота, завдання для майбутнього абітурієнта.

МАТЕМАТИЧНА СКАРБНИЧКА ЗАДАЧ З КОМБІНАТОРИКИ

Актуальність:

• Комбінаторні задачі розвивають нестандартне мислення, уяву, логигу, смекалку.
• Задачі з комбінаторики включені на всіх етапах математичних олімпіад та ЗНО

Комбінаторні задачі : навіщо вони потрібні?

Якщо ви знаєте, що таке комбінаторні задачі, то ніяких складнощів з їх рішенням ви відчувати не будете. Методика їх вирішення може стати в нагоді при необхідності складання розкладів, графіків роботи, а також складних математичних обчислень, для виконання яких не підійдуть електронні пристрої.

Комбінаторика – наука майбутнього? Багато фахівців в області математики і фізики вважають, що саме комбінаторна задача може стати поштовхом у розвитку всіх технічних наук. Достатньо лише нестандартно підійти до вирішення тих чи інших проблем, і тоді можна буде відповісти на питання, які вже кілька століть не дають спокою вченим. Деякі з них всерйоз стверджують, що комбінаторика є підмогою для всіх сучасних наук, особливо космонавтики. Набагато простіше буде вираховувати траєкторії польоту кораблів з допомогою комбінаторних задач, також вони дозволять визначити точне знаходження тих чи інших небесних світил.

Реалізація нестандартного підходу вже давно почалася в азіатських країнах, там учні навіть елементарні завдання по множенню, віднімання, складання і розподілу вирішують, використовуючи комбінаторні методи. На подив багатьох європейських вчених, методика дійсно працює. Школи Європи поки що тільки почали переймати досвід своїх колег. Коли саме комбінаторика стане одним з основних розділів математики, припустити складно. Зараз наука вивчається провідними вченими планети, які прагнуть популяризувати її.

З задачами, в яких приходиться вибирати ті чи інші предмети, розміщувати їх в певному порядку і відшуковувати серед різних розміщень найкращі, люди стикнулися ще в доісторичну епоху, обираючи найкращі розміщення мисливців під час полювання, воїнів під час битви, інструментів під час роботи.

Пізніше, поряд із спортивними змаганнями з’явились ігри з різними фігурами чи предметами, в яких вигравав той, хто краще знав переможні комбінації та вмів уникати програшних.(Давня єгипетська гра «сенет», в яку грав фараон Тутанхамон, нарди, китайські та японські шахмати, японські шашки «го» і т. д.) Що ж було поштовхом до виникнення комбінаторики, як науки? Для чого

ще потрібні знання з комбінаторики, крім відомого вже нам застосування в теорії ймовірності?

При вивченні розділу «Комбінаторика» в 11-му класі загальноосвітньої школи за програмою розглядають такі теми:

1. Поняття множини. Елементи множини. Дії над множинами.
2. Факторіал. Сполуки без повторень.
3. Розв’язування комбінаторних задач
4. Трикутник Паскаля. Біном Ньютона. Формула загального члена розкладу бінома.

Поняття множини

Поняття множини належить до первісних, воно не означається. Множина — це сукупність, зібрання деяких предметів будь-якої природи, наприклад: множина учнів класу, множина цифр десяткової нумерації, множина букв українського алфавіту, множина міст держави, множина будинків на вулиці тощо.

Для позначення множин використовуються прописні літери латинського алфавіту або фігурні дужки: множина А або .

Елементи множини

Означення . Предмети, з яких складається множина, називаються її елементами.

Наприклад , а = 5 — елемент множини цифр десяткової нумерації;

Львів — елемент множини міст України.

Якщо множину цифр десяткової нумерації позначити через А, то належність числа цій множині можна позначити так:

Число 12 не належить множині А, не є елементом цієї множини. Це твердження можна записати так: 12 А.

Множини бувають скінченні (множина будинків а певній вулиці) і нескінченні (множина точок прямої).

Означення . Множина, у якій немає жодного елемента, називається порожньою.

Наприклад , множина розв’язків рівняння х 2 = -1 на множині дійсних чисел є порожньою.

Множину можна задати: переліченням усіх її елементів, наприклад або характеристичною властивістю, наприклад , В — множина чисел, кратних 15, що менші від 90.

Означення . Дві множини називаються рівними, якщо вони складаються з однакових елементів.

Наприклад , X — множина коренів рівняння x 2 = 25, Х = ;

множина Y — множина коренів рівняння | х | = 5 , Y = .

Означення . Якщо множина В складається з деяких елементів даної множини А і лише з них, то множина В називається підмножиною множини А.

Наприклад , якщо В = , А = , то В А.

Над множинами можна виконувати певні операції. Розглянемо три з них.

Переріз множин

Означення 5. Перерізом множин А і В називається множина С, яка складається з усіх тих і лише тих елементів, які належать кожній із даних множин.

Приклад 1 . А — множина всіх дільників числа 32, В — множина всіх дільників числа 24.

Об’єднання множин

Означення 6. Об’єднанням або сумою двох множин А і В називається така множина R, яка складається з усіх елементів множин А і В і лише з них.

Кожний зі спільних елементів береться в множину лише один раз.

Приклад . Для множин А і В з прикладу 1 об’єднанням буде

Приклад . Множина дійсних чисел є об’єднанням множин раціональних та ірраціональних чисел: Q I = R.

Віднімання множин. Доповнення множини

Означення . Різницею двох множин А і В називається така множина D яка складається з усіх елементів множини А, які не належать множині В.

Приклад. А = , В = , DАВ = .

Впорядкована множина

Означення 8 . Скінченна множина, для якої істотний порядок елементів, називається впорядкованою.

Вказати порядок розміщення елементів у скінченній множині з n елементів — означає поставити у відповідність кожному елементу даної множини певне натуральне число від 1 до n .

Приклад 7 . Множини А = і В = є рівними, якщо вони не впорядковані, А = В.

Якщо ж вони є впорядкованими, то А ≠ В.

Приклад 8 . Із 30 учнів класу потрібно вибрати двох:

а) старосту і його заступника;

У випадку а) — це впорядкована множина.

Домашнє завдання.

Означення . Факторіал — це добуток послідовних натуральних чисел.

Термін «факторіал» походить від англійського слова «фактор» — множник.

Відповідь . х = 6.

На практиці часто доводиться відповідати на запитання: скількома способами можна виконати певне завдання? Наприклад, скласти розклад п’яти уроків на день із десяти різних навчальних предметів; позначити різні зв’язки між атомами і молекулами певної речовини; записати діагоналі опуклого десятикутника; знайти різні шляхи доставки виробів із заводу в магазини і визначити, який з них найбільш вигідний.

Методи розв’язування таких задач вивчають у розділі математики, який називається комбінаторикою, а самі задачі — комбінаторними.

Розв’язуючи комбінаторні задачі, розглядають скінченні множини, утворені з елементів будь-якої природи, та їх підмножини. Залежно від умови задачі розглядаються скінченні множини, у яких істотним є або порядок елементів, або їх склад, або і те і те одночасно. Такі скінченні множини (сполуки) мають певну назву.

Означення. Будь-яка впорядкована множина, що складається з п елементів, називається перестановкою з п елементів.

Перестановки відрізняються одна від одної лише порядком елементів.

Приклад. Із елементів множини А = можна утворити 6 перестановок: , , , , , .

Перестановки — впорядковані множини

Кількість усіх можливих перестановок у множині з п елементів позначається Р _n .

Один елемент можна розмістити одним способом: P ₁ = 1.

Два елементи можна розмістити двома способами: Р ₂ = 2.

Три елементи можна розмістити шістьма способами: Р ₃ = 6.

з першим елементом b — 6 перестановок;

з першим елементом с — 6 перестановок;

з першим елементом d — 6 перестановок.

Усього 24 перестановки: Р ₄ = 24.

Взагалі, кількість усіх можливих перестановок у множині з п елементів дорівнює добутку послідовних натуральних чисел, тобто

Дерево з варіантів . Деякі комбінаторні задачі можна вирішити, лише складаючи схеми, в яких буде детально вказана інформація про кожен елемент. Складання дерева можливих варіантів – ще один спосіб знаходження відповіді. Він підходить для вирішення не дуже-то складних завдань, в яких є додаткова умова.

Задача. Розглянемо задачу про складання трьохзначних чисел з цифр 1, 4, 7 ( цифри у запису числа не повторюються). Для її розв’язку строять схему-дерево можливих варіантів

Приклад. 12 осіб можна розмістити за столом, біля якого поставлено 12 стільців, Р _І2 = 12! способами.

12! = 479 001 600. Якщо гості будуть пересаджуватися щохвилини протягом 11 годин на добу 365 днів на рік з відпочинком 1 день у високосному році, то на це піде 1988 років і 140 днів.

Приклад . Мандрівнику потрібно виїхати з пункту А, відвідати пункти В, С, й і повернутися в пункт А. А D = 500 км, С D = 400 км, В D = 400 км, АВ = 300 км, АС — 200 км, ВС = 350 км. Скількома способами він може це зробити? Який варіант найбільш оптимальний?

Розглянемо схему руху мандрівника.

Оскільки йому потрібно відвідати три пункти, то можливих варіантів маршруту є 6: Р ₃ = 3! = 6.

Відповідь. Найбільш оптимальними є варіанти АВ D СА і АС D ВА.

Задача. Скількома способами можна скласти денний розклад з п’яти різних уроків, якщо в класі вивчають 10 навчальних предметів?

. Отже, загальна кількість способів, за якими можна поставити два перших уроки, становить 10 ∙ 9 = 90.

Для третього уроку залишається Я можливостей вибору предмета, бо два вже поставлено в розклад. Тому для розподілу трьох Маємо 10 різних можливостей запису в розклад першого уроку, бо кожний предмет можна поставити першим уроком.

Другим уроком можна поставити будь-який з 9 предметів, що залишилися перших уроків кількість різних способів дорівнюватиме 10 ∙ 9 ∙ 8 = 720.

Для четвертого уроку залишається 7 можливостей вибору предметів, для п’ятого — 6, тому, щоб поставити п’ять уроків у розклад, існує 10 ∙ 9 ∙ 8 ∙ 7 ∙ 6 = = 30 240 різних способів.

Розв’язуючи задачу, ми з множини, що містить 10 елементів, утворювали впорядковані підмножини, що містять по одному, два, три, чотири, п’ять елементів, тобто утворювали розміщення з 10 елементів відповідно по одному, два, три, чотири, п’ять. Кількість усіх можливих розміщень з m елементів по n елементів позначається .

= 10, = 10 ∙ 9, = 10 ∙ 9 ∙ 8, = 10 ∙ 9 ∙ 8 ∙ 7, = 10 ∙ 9 ∙ 8 ∙ 7 ∙ 6.

Аналізуючи закономірність утворення чисел , , , , . помічаємо, що:

• кожне з них дорівнює добутку стількох послідовних натуральних чисел, скільки елементів у розміщенні;
• на першому місці стоїть множник, що дорівнює кількості всіх елементів множини, з якої утворюються розміщення, а кожний наступний множник на одиницю менший від попереднього;
• останній множник дорівнює різниці між кількістю всіх елементів, з яких утворюється розміщення, і числом, на одиницю меншим від кількості
  елементів у розміщенні.

Припускаємо, що формула має вигляд:

Доведення можна провести методом математичної індукції на факультативному занятті.

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

Порядок елементів у множині неістотний, комбінації відрізняються лише складом елементів. Кількість усіх можливих комбінацій з т елементів по n позначається символом .

Комбінація відрізняється від розміщення тим, що у цій підмножині неістотним є порядок елементів.

Задача. Скількома способами можна призначити чотирьох вартових із 30 солдатів?

Будь-які дві групи відрізняються лише складом солдат, порядок у групі неістотний. Маємо справу з різними підмножинами з чотирьох елементів даної множини, що складається з 30 елементів. Будь-яка з цих підмножин є комбінацією з 30 елементів по 4. Якби ця підмножина була упорядкованою, то кількість таких груп можна знайти за формулою . У кожній з упорядкованих множин можна виконати Р ₄ перестановок, тому кількість усіх можливих комбінацій .

У загальному випадку кількість комбінацій з т елементів по л елементів можна обчислити за формулою:

Перетворимо цю формулу, використавши формули 2 і 1.

Отже, чотирьох вартових із 30 солдатів можна вибрати способами.

Приклад. На площині позначено n точок, з яких ніякі три не лежать на одній прямій. Скільки різних прямих можна провести через ці точки?

Оскільки через кожну пару точок можна провести лише одну пряму, то кількість різних прямих дорівнює кількості комбінацій з n елементів по 2 елементи, тобто .

Домашнє завдання.

1. Скільки слід взяти елементів, щоб кількість усіх перестановок, які можна утворити з них, дорівнювала 5040?
2. Скільки різних прямих можна провести через 10 точок площини, з яких ніякі три не лежать на одній прямій?
3. Спростити вираз: а) ; б) ; в) .

1. Скільки семицифрових чисел можна утворити за допомогою семи різних цифр, відмінних від 0, не повторюючи цифри у запису числа?

Шукане число дорівнює кількості перестановок із 7 різних елементів:

Р ₇ = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 = 5040.

Відповідь. 5040 різних семицифрових чисел.

Потрібно утворити впорядковані множини з двох елементів: 13, 31, 17, 71, . . Ці множини є розміщеннями з 4 елементів по 2, тобто кількість усіх двоцифрових чисел, що відповідають умові, становитиме = 4 ∙ 3 = 12.

1. Скільки можна утворити різних трицифрових додатних цілих чисел у десятковій системі числення, не повторюючи цифри у запису числа?

Із 10 цифр можна утворити = 10 ∙ 9 ∙ 8 = 720 різних трицифрових чисел. З них із цифри 0 починаються = 9 ∙ 8 = 72 числа. Усього чисел, що відповідають умові, можна утворити – = 648.

1. Відомо, що старосту і його заступника в класі можна вибрати шістьмастами різними способами. Скільки учнів у класі?

Позначимо кількість учнів у класі через де, ( х — натуральне число). Шукана підмножина є впорядкованою, тому можна записати:

– 24 не відповідає умові задачі.

4.2: Підмножини та набори живлення

Приклад \(\PageIndex<1>\label\) Діаграми Венна корисні для демонстрації встановлених відносин. Нехай \[\begin &=& \mbox, \\ S &=& \mbox, \\ P &=& \mbox, \\ R &=& \mbox, \\ L &=& \mbox, \\ C &=& \mbox. \end \nonumber\] Їх зв’язок відображається на малюнку \(\PageIndex<1>\) .

Малюнок \(\PageIndex<1>\) : Взаємозв’язок між різними наборами геометричних фігур. Мальовниче зображення на малюнку \(\PageIndex<1>\) називається діаграмою Венна. Ми використовуємо прямокутник для представлення універсального набору, а кола або овали для представлення множин всередині універсального набору. Відносні положення цих кіл і овалів вказують на взаємозв’язок відповідних множин. Наприклад, мати \(R\) , і \(L\) всередині \(P\) означає \(S\) , що ромби, квадрати і прямокутники є паралелограмами. Навпаки, кола незрівнянні з паралелограмами. Множина \(A\) – це підмножина іншого \(B\) множини \(A \subseteq B\) , позначається, якщо кожен елемент також \(A\) є елементом \(B\) . Див \(\PageIndex\) . Малюнок. Ми також \(B\) називаємо супермножину \(A\) , і пишемо \(B \supseteq A\) , яка схожа на \(y\geq x\) . Малюнок \(\PageIndex\) : Діаграма Венна для \(A \subseteq B\) .

Приклад \(\PageIndex<2>\label\) Зрозуміло, що \(\mathbb\subseteq\mathbb\) і \(\mathbb\subseteq\mathbb\) . Ми можемо вкласти ці два відносини в одне, і написати \(\mathbb\subseteq\mathbb \subseteq\mathbb\) . Більш загально, у нас є \[\mathbb \subseteq \mathbb \subseteq \mathbb \subseteq \mathbb. \nonumber\] Порівняти це з \(x \leq y \leq z \leq w\) . Ми виявимо багато подібності між \(\subseteq\) і \(\leq\) .

Приклад \(\PageIndex<3>\label\) Очевидно, що \[\ \subseteq \ \nonumber\] тому, що всі три елементи 1, 2 і 7 з набору зліва також виступають як елементи в наборі праворуч. Тим часом, \[\ \nsubseteq \ \nonumber\] тому що 7 належить до першого набору, а не другому.

Будьте впевнені, що ви можете чітко пояснити, чому ці зв’язки підмножини тримаються.

практичні вправи \(\PageIndex\label\)

Ці твердження правдиві чи хибні?

Не варто вважати, що якщо \(A\nsubseteq B\) тоді ми повинні мати \(B\subseteq A\) . Наприклад, якщо \(A=\\) і \(B=\\) , то \(A \nsubseteq B\) ; але ми також маємо \(B \nsubseteq A\) .

Останній приклад демонструє, що \(A\nsubseteq B\) це складніше, ніж просто зміна позначення підмножини, як ми робимо з нерівностями. Нам потрібно більш точне визначення співвідношення підмножини:

\[A \subseteq B \Leftrightarrow \forall x\in \,(x \in A \Rightarrow x \in B) \nonumber\]

\[A \nsubseteq B \Leftrightarrow \exists x\in \,(x \in A \wedge x \not\in B). \nonumber\] Звідси випливає, що Отже, щоб показати, що \(A\) це не підмножина \(B\) , нам потрібно знайти елемент \(x\) , який належить, \(A\) але ні \(B\) . Є три можливості; їх діаграми Венна зображені на малюнку \(\PageIndex\) .

Малюнок \(\PageIndex\) : Три випадки \(A \nsubseteq B\) .

У нас є \([3,6]\subseteq[2,7)\) , і \([3,6]\nsubseteq[4,7)\) . У нас теж є \((3,4) \subseteq [3,4]\) .

практичні вправи \(\PageIndex\label\)

Правда чи брехня: \([3,4) \subseteq (3,4)\) ? Поясніть.

З поняттям універсальної множини тепер ми можемо уточнити визначення множини рівності:

\[A = B \Leftrightarrow \forall x\in\,(x\in A \Leftrightarrow x\in B) \nonumber\]

Логічно, \(x\in A \Leftrightarrow x\in B\) це еквівалентно \[(x\in A \Rightarrow x\in B) \wedge (x\in B\Rightarrow x\in A). \nonumber\] Тому ми також можемо визначити рівність множин за допомогою підмножини відносин:

\[A = B \Leftrightarrow (A \subseteq B) \wedge (B \subseteq A) \nonumber\]

які можна порівняти з \[x=y \Leftrightarrow (x\leq y) \wedge (y\leq x) \nonumber\] для дійсних чисел \(x\) і \(y\) .

Це нове визначення множинної рівності говорить про те, що для того, щоб довести це \(A=B\) , ми могли б використовувати цей двоетапний аргумент:

Цей прийом стане в нагоді, коли неможливо або недоцільно перерахувати елементи \(A\) і \(B\) для порівняння. Це особливо вірно, коли \(A\) і \(B\) визначаються абстрактно. Ми будемо застосовувати цю техніку в наступних розділах.

Ці два відносини \(\subseteq\) і мають багато \(\leq\) спільних властивостей. Перехідне властивість – ще один приклад.

Нехай \(A\) \(B\) , і \(C\) бути набори. Якщо \(A\subseteq B\) і \(B\subseteq C\) , то \(A\subseteq C\) .

Обговорення

Твердження теореми має форму імплікації. Щоб довести \(p\Rightarrow q\) , ми починаємо з припущення і використовуємо його \(p\) , щоб показати, що також \(q\) має бути правдою. У цьому випадку ці два кроки стають

Як ми можемо це довести \(A\subseteq C\) ? Ми знаємо, що \(A\subseteq C\) це означає \[\forall x\in\,(x\in A\Rightarrow x\in C). \nonumber\] Отже, ми повинні почати з \(x\in A\) , і спробувати показати це \(x\in C\) також. Як ми можемо це показати \(x\in C\) ? Потрібно скористатися припущенням \(A\subseteq B\) і \(B\subseteq C\) .

Припустимо \(A\subseteq B\) і \(B\subseteq C\) . Нехай \(x\in A\) . Так як \(A\subseteq B\) , у нас теж є \(x\in B\) . Так само це \(B\subseteq C\) означає \(x\in C\) . Оскільки кожен елемент \(x\) в також \(A\) є елементом \(C\) , ми робимо висновок, що \(A\subseteq C\) .

Доказ спирається на визначення зв’язку підмножини. Багато доказів в математиці досить прості, якщо ви знаєте основні визначення.

Доведіть \(x \in A \Leftrightarrow \ \subseteq A\) , що для будь-якого елемента \(x\in\)

Обговорення

Ми називаємо \(p\Leftrightarrow q\) двозастережним твердженням, оскільки воно складається з двох наслідків \(p \Rightarrow q\) і \(p\Leftarrow q\) . Значить, нам потрібно довести це в два етапи:

Ми називаємо ці два наслідки необхідністю і достатністю біумовного твердження і позначаємо їх ( \(\Rightarrow\) ) і ( \(\Leftarrow\) ) відповідно. У цій проблемі

• ( \(\Rightarrow\) ) означає « \(x\in A\Rightarrow\\subseteq A\) ».
• ( \(\Leftarrow\) ) означає « \(\\subseteq A\Rightarrow x\in A\) ».

Ось як може виглядати доказ:

\[\begin (\Rightarrow) & \quad \text < Assume >x\in A. & \qquad\ldots\qquad & \text x \subseteq A. \\ (\Leftarrow) & \quad \text x \subseteq A. & \qquad\ldots\qquad & \text < Therefore >x \in A. \end \nonumber\]

Тепер приступаємо до завершення доказу.

( \(\Rightarrow\) ) Припустимо \(x \in A\) . Набір \(\\) містить лише один елемент \(x\) , який також є елементом \(A\) . Таким чином, кожен елемент також \(\\) є елементом \(A\) . За визначенням, \(\ \subseteq A\) .

( \(\Leftarrow\) ) Припустимо \(\ \subseteq A\) . Визначення відношення підмножини стверджує, що кожен елемент також \(\\) є елементом \(A\) . Зокрема, \(x\) є елементом \(\\) , тому він також є елементом \(A\) . Таким чином, \(x \in A\) .

Множина \(A\) є належною підмножиною \(B\) , позначається \(A \subsetneq B\) або \(A \subset B\) , якщо \(A\) є підмножиною \(B\) , і \(A\neq B\) . Символічно, \(A \subset B \Leftrightarrow (A \subseteq B) \wedge (A \neq B)\) . Аналогічно, \[A \subset B \Leftrightarrow (A \subseteq B) \wedge \exists x\in\,(x \in B \wedge x \not\in A). \nonumber\] див. Діаграму Венна на малюнку \(\PageIndex\) .

Малюнок \(\PageIndex\) : Визначення належної підмножини.

практичні вправи \(\PageIndex\label\)

Правда чи брехня: \((3,4)\subset[3,4]\) ? Як щодо \((3,4)\subset(3,4]\) ?

Для будь-якого набору \(A\) у нас є \(\emptyset \subseteq A\) і \(A \subseteq A\) . Зокрема, \(\emptyset\subseteq\emptyset\) .

Оскільки кожен елемент \(A\) також з’являється в \(A\) , відразу випливає, що \(A\subseteq A\) . Щоб показати це \(\emptyset\subseteq A\) , нам потрібно перевірити підтекст \[x\in\emptyset \Rightarrow x\in A \nonumber\] для будь-якого довільного \(x\in\) . Оскільки \(\emptyset\) порожній, завжди \(x\in\emptyset\) хибний; отже, імплікація завжди вірна. Отже, \(\emptyset\subseteq A\) для будь-якого набору \(A\) . Зокрема, коли \(A=\emptyset\) , отримаємо \(\emptyset\subseteq \emptyset\) .

Визначте істинні значення цих виразів.

1. \(\emptyset \in \emptyset\)
2. \(1 \subseteq \\)
3. \(\emptyset \in \\)

1. За визначенням, порожній набір не містить жодного елемента. Отже, твердження \(\emptyset\in\emptyset\) є помилковим.
2. Відношення підмножини існує лише між двома множинами. Зліва від символу \(\subseteq\) у нас є тільки число, яке не є набором. Значить, твердження є помилковим. Насправді цей вислів синтаксично невірно.
3. Набір \(\\) містить один елемент, який буває порожнім набором. Порівняйте це з порожнім ящиком всередині іншого ящика. Зовнішня коробка описується парою встановлених дужок \(\<\,\ldots\,\>\) , а (порожня) коробка всередині – \(\emptyset\) . Звідси випливає, що \(\emptyset\in\\) є правдивим твердженням.

практичні вправи \(\PageIndex\label\)

Визначте істинні значення цих виразів.

Безліч всіх підмножин \(A\) називається множиною потужності \(A\) , що позначається \(\wp(A)\) .

Оскільки сам набір потужності є набором, нам потрібно використовувати пару лівих і правих фігурних дужок (встановити дужки), щоб укласти всі його елементи. Її елементи являють собою самі набори, для кожного з яких потрібна своя пара лівих і правих фігурних дужок. Отже, нам потрібно щонайменше два рівні встановлених дужок для опису набору потужності.

Нехай \(A=\\) і \(B=\\) . \(A\) Підмножини \(\emptyset\) are \(\\) , \(\\) і \(\\) . Тому подібним \[\wp(A) = \big\< \emptyset, \, \, \ \big\>. \nonumber\] чином ми знаходимо \[\wp(B) = \big\ < \emptyset, \\big\>. \nonumber\] Ми можемо писати безпосередньо, \[\wp(\) = \big\< \emptyset, \, \, \ \big\>, \qquad\mbox\qquad \wp(\) = \big\ < \emptyset, \\big\> \nonumber\] не вводячи листи для представлення наборів, що беруть участь.

практичні вправи \(\PageIndex\label\)

Давайте оцінимо \(\wp(\)\) . Щоб переконатися, що жодна підмножина не пропущена, ми перерахуємо ці підмножини відповідно до їх розмірів. Оскільки \(\emptyset\) є підмножиною будь-якої множини, завжди \(\emptyset\) є елементом у наборі потужності. Це підмножина розміру 0. Далі перелічіть одноелементні підмножини (підмножини з одним елементом). Потім підмножини doubleton, і так далі. Заповніть наступну таблицю.

\[\begin <|c|l|>\hline \mbox & \mbox \\ \hline 0 & \emptyset \\ 1 & \, \, \ldots \qquad \\ 2 & \, \, \ldots \hskip2in \\ 3 & \, \ldots \hskip1in \\ 4 & \ldots \\ \hline \end \nonumber\] Так як \(A\subseteq A\) для будь-якого набору \(A\) потужність набір \(\wp(A)\) завжди містить \(A\) сам себе. В результаті остання підмножина в списку повинна бути \(A\) сама.

Тепер ми готові зібрати їх разом, щоб сформувати набір потужності. Все, що вам потрібно, це помістити всі підмножини всередині пари великих фігурних дужок (набір потужності сам по собі набір; отже, йому потрібна пара фігурних дужок у своєму описі). Помістіть остаточну відповідь у простір нижче.

Перевірте, щоб переконатися, що ліва і права дужки ідеально збігаються.

Оскільки \(A\) є підмножиною \(A\) , вона належить до \(\wp(A)\) . Тим не менш, це неправильно сказати \(A \subseteq \wp(A)\) . Чи можете ви пояснити чому? Якими повинні бути правильні позначення?

Набір потужності \(\wp(A)\) – це сукупність всіх підмножин \(A\) . Таким чином, елементи в \(\wp(A)\) є підмножинами \(A\) . Однією з таких підмножин є \(A\) сама множина. Отже, \(A\) сама з’являється як елемент в \(\wp(A)\) , і ми пишемо, \(A\in\wp(A)\) щоб описати це членство.

Це відрізняється від того, щоб сказати, що \(A\subseteq\wp(A)\) . Для того, щоб мати зв’язок \(A\subseteq\wp(A)\) підмножини, кожен елемент в також \(A\) повинен відображатися як елемент в \(\wp(A)\) . Елементи \(\wp(A)\) є множинами (вони є підмножинами \(A\) , а підмножини – множинами). Елемент не \(A\) збігається з підмножиною \(A\) . Тому, хоча і \(A\subseteq\wp(A)\) синтаксично коректно, його істинне значення хибне.

практичні вправи \(\PageIndex\label\)

Поясніть різницю між \(\emptyset\) і \(\\) . Скільки елементів є в \(\emptyset\) і \(\\) ? Це правда \(\wp(\emptyset) = \\) ?

Якщо \(A\) набір \(n\) -element, то \(\wp(A)\) має \(2^n\) елементи. Іншими словами, набір \(n\) -element має \(2^n\) різні підмножини.

Скільки підмножин ми \(A\) можемо побудувати? Щоб сформувати підмножину, ми проходимо кожен з \(n\) елементів і запитуємо себе, чи хочемо ми включити цей конкретний елемент чи ні. Оскільки існує два варіанти (так чи ні) для кожного з \(n\) елементів у \(A\) , ми знайшли \(\underbrace_<\mbox>\, =2^n\) підмножини.

практичні вправи \(\PageIndex\label\)

Скільки елементів є в \(\wp(\)\) ? Які вони?

практичні вправи \(\PageIndex\label\)

У чому полягає кардинальність \(\emptyset\) ? Як щодо \(\wp(\emptyset)\) ? Опишіть \(\wp(\emptyset)\) .

практичні вправи \(\PageIndex\label\)

Чи правильно писати \(|\wp(A)|=2^<|A|>\) ? Як щодо \(|\wp(A)|=2^A\) ? Поясніть.

Коли набір містить набори як елементи, його набір потужності може стати досить складним. Ось два приклади. \[\begin \wp(\big\,\\big\>) &=& \Big\< \emptyset, \big\\big\>, \big\<\\big\>, \big\,\\big\> \Big\>, \\ \wp(\big\<\emptyset,\\big\>) &=& \Big\< \emptyset, \, \big\<\\big\>, \big\<\emptyset,\\big\> \Big\>. \end \nonumber\] Переконайтеся, що ви розумієте позначення, використовувані в цих прикладах. Зокрема, вивчіть кількість рівнів встановлених дужок, які використовуються в кожному прикладі.

Резюме та огляд

• Множина \(S\) є підмножиною іншого \(T\) множини тоді і тільки тоді, коли кожен елемент в \(S\) можна знайти в \(T\) .
• В символах, \(S\subseteq T \Leftrightarrow \forall x\in\, (x\in S \Rightarrow x\in T)\) .
• Отже, щоб показати \(S\subseteq T\) , що, ми повинні почати з довільного елемента \(x\) в \(S\) , і показати, що \(x\) також належить \(T\) .
• Визначення відношення підмножини має на увазі, що для будь-якої \(S\) множини у нас завжди є \(\emptyset\subseteq S\) і \(S\subseteq S\) .
• Потужність множини \(S\) , що позначається \(\wp(S)\) , містить всі підмножини \(S\) .
• Якщо \(|S|=n\) , то \(|\wp(S)|=2^n\) . Отже, набір \(n\) -element має \(2^n\) підмножини.
• Для побудови \(\wp(S)\) перерахуйте підмножини \(S\) відповідно до їх розмірів. Обов’язково використовуйте пару фігурних дужок для кожної підмножини та вкладіть усі їх у пару зовнішніх фігурних дужок.

Вправи 4.2

Визначте, які з наведених нижче тверджень є істинними, а які – помилковими.

1. \(\ \subseteq \\)
2. \(\ \subseteq \mathbb\)
3. \(\ \subset [1,2]\)
4. \([2,4] \subseteq (0,6)\)
5. \([2,4) \subset [2,4]\)
6. \([2,4) \subseteq (2,4]\)

Визначте, які з наведених нижче тверджень є істинними, а які – помилковими.

1. \(a \subseteq \\)
2. \(\ \subseteq \\)
3. \(\emptyset \subseteq \emptyset\)
4. \(\emptyset \subseteq \\)
5. \(\emptyset \subset \\)
6. \(\ \subseteq \wp(\<\,\\>)\)

Поясніть, чому \(\mathbb \subseteq \mathbb\) . Зокрема, пояснити, як виражати ціле число як раціональне число.

Правда чи брехня: \(\mathbb \subseteq 6\mathbb\) ? Поясніть.

Якщо \(A\subseteq B\) \(B\subseteq C\) , і \(C\subseteq D\) , це правда \(A\subseteq D\) ? Як ви називаєте цю властивість?

Визначте, чи є такі твердження істинними чи хибними:

Знайдіть набір потужності наступних наборів.

Ми дізналися, що \(A\subseteq A\) для будь-якого набору \(A\) . Тоді ми повинні писати \(A\in\wp(A)\) чи \(A\subseteq\wp(A)\) ? Поясніть.

Доведіть, що \(X\in\wp(A)\) якщо і тільки якщо \(X\subseteq A\) .

Визначте, які з наведених нижче тверджень є істинними, а які – помилковими. Поясніть!

Визначте, які з наведених нижче тверджень є істинними, а які – помилковими. Поясніть!