Розв'язник вправ по дискретній математиці/Множини

Розв'язник вправ по дискретній математиці. Множини

Поняття «множини» не визначається, але можна його розуміти як сукупність об'єктів (елементів множини), яка розглядається як одне ціле.

Наприклад, множину "велосипед" можна визначити як сукупність, яка складається з елементів: "рама", "переднє колесо", "заднє колесо", "кермо", "сідло", "педалі".

Таке просте перерахування елементів множини є фактично описом множини. Виділяють наступні способи опису множини.

Способи опису множини

• Перерахуванням елементів. Елементи множини безпосередньо виписуються.
• Характеристичною властивістю. Вказується предикат p(x), який характеризує множину M і якщо він виконується для елемента x, тобто p(x) - істинний, то x належить M. Записують так: M = {x | p(x)}
• Генерувальна процедура. Всі елементи множини породжуються за допомогою функції або алгоритму. Записують так: M = {x | x:=f }.

Приклад. 1. Нехай перерахуванням задана множина $M=\{2,4,6,8,10,12,\dots ,98\}.$ Як її можна описати по іншому?

2. Як можна описати множину простих чисел до 100?

3. Як можна описати абетку - множину букв?

Позначення

Фігурні дужки {…} відповідають фразі «множина…(чогось)». Ці дужки можна використовувати по-різному. Наприклад:

• Можна перераховувати елементи множини:

{-3,-2,-1,0,1,2,3}

• Можна описувати елементи множини:

{цілі числа від -3 до 3 включно}

• Можна використовувати ідентифікатор (літеру x, наприклад) щоб показати типовий елемент, символ | замість фрази «такий як», а потім правило(а), яким наш ідентифікатор має підкорятися:

{ x|x ціле число і |x|<4} або { x|x Z ,|x|<4}

Останній спосіб описати множину може бути узагальнений до: x | P(x), де P(x) - це твердження (технічно, пропозиційна функція) стосовно x і множина - це сукупність усіх елементів x для яких вірно P.

Символ ∈ використовується в таких випадках:

• ∈ означає «є елементом...». Наприклад: собака ∈ {чотиринога тварина}

∉ означає «не є елементом...» Наприклад: Вашингтон ∉ {столиці Європи}

Множина може бути скінченна: {Британські міста} ... або нескінченно велика: {7,14,21,28,35,... } (Зазначте, що три крапки ... позначають нескінченну послідовність чисел .) Множини завжди позначають, використовуючи великі літери: A, B, ... Елементи завжди позначають малими літерами: x, y, ...

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

Універсум

Множина усіх «речей», про які йде мова, називається універсумом. Вона позначається U.

Універсум не позначає усі речі в світі. Навпаки, він включає лише ті, які є актуальними у визначений час. Наприклад, якщо в даній ситуації ми говоримо про числові значення – частоти, розміри, часи, вага, чи щось такого плану – універсумом буде, відповідно, множина чисел (див. нижче). У іншому контексті, універсумом може бути {символи алфавіту} або {усі люди на Землі}, і т.д.

Порожня множина

Множина, яка не містить елементів, називається пустою або порожньою. Її позначають парою фігурних дужок {} або символом ∅. Може здатися, що зайво позначати множину, котра не містить елементів. Однак, слід пам’ятати, що бувають випадки, коли ми шукаємо рішення задачі, а невідомо, існує взагалі це рішення чи ні. Якщо виявляється, що рішення немає, то порожня множина стає рішенням. Наприклад:

• Якщо U = {усі слова англійського алфавіту}, тоді {слова, у яких більш ніж 50 літер}=∅

Якщо U = {усі числа}{x|x^{2}=10}=∅

Операції над порожньою множиною

Операції, що здійснюються над порожньою множиною (нульарні операції), також можуть викликати замішання. Наприклад, сума елементів порожньої множини дорівнює 0, але добуток елементів порожньої множини дорівнює 1. Вони можуть здатися зайвими, оскільки у порожній множини немає елементів, тож яка різниця додаємо ми їх чи перемножуємо (все одно ж «вони» не існують)? Безумовно, результати цих операцій кажуть більше про самі операції, ніж про порожню множину. Наприклад, зауважте, що нуль - тотожний елемент для додавання, а одиниця – для множення.

Деякі особливі множини чисел

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

Натуральні числа

Злічувані числа (усі числа починаючи з 1) називаються натуральними. Множина натуральних чисел іноді позначається N. Так N = {1, 2, 3, ...} Слід зауважити, що на письмі ми не можемо виділити шрифт жирним , тож позначаємо ℕ;

Цілі числа

Усі числа, додатні, від’ємні, а також 0 – формують множину цілих чисел.Вона іноді позначається Z. Так Z = {..., -3, -2, -1, 0, 1, 2, 3, ...} На письмі виглядає так: ℤ

Дійсні числа

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

• повторюватися; напр. 8.127127127...
• або не повторюватися; напр. 3.141592653...

На письмі: ℝ.

Раціональні числа

Ті дійсні числа, які мають скінченну кількість цифр після коми, називаються раціональними. Множина раціональних чисел іноді позначається Q. Дійсні числа можна завжди записати у вигляді дробу p/q; де p та q – цілі числа. Якщо q дорівнює 1, то дріб - це p. Слід зазначити, що q не може дорівнювати 0, оскільки величина тоді невизначена.

• Наприклад: 0.5, -17, 2/17, 82.01, 3.282828... є раціональними числами.

На письмі: ℚ.

Ірраціональні числа

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

• Наприклад √2, √3, π

Відношення між множинами

Розглянемо різні шляхи відношення між множинами.

Рівність

Дві множини A і B називаються рівними, якщо і тільки якщо вони складаються з однакових елементів. У такому випадку ми просто пишемо:

A = B

Слід зазначити наступне:

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

Тож, наприклад, наступні множини рівні: {1, 2, 3} = {3, 2, 1} = {1, 1, 2, 3, 2, 2}

(Ви можете поцікавитися, як взагалі комусь спало на думку написати множину як {1, 1, 2, 3, 2, 2}. Згадаємо, коли ми давали визначення порожній множині, ми відзначили, що для тієї чи іншої проблеми може не бути ніяких рішень - звідси необхідність порожньої множини. Однак, тут ми можемо спробувати кілька різних підходів до вирішення проблеми, деякі з яких насправді ведуть нас до одного і того ж рішення. Коли ми будемо розглядати різні рішення, будь-які такі повтори будуть ігноруватися)

// Насправді в теорії множин не існує виразів, як {1, 1, 2, 3, 2, 2}. Всі елементи мають бути унікальними.

Підмножини

Якщо усі елементи множини A є одночасно елементами множини B, то кажуть, що A – підмножина B, і записують так:

A ⊆ B

Наприклад:

• Якщо T = {2, 4, 6, 8, 10} а E = {парні числа}, тоді T ⊆ E
• Якщо A = {знаки алфавіту} і P = {знаки, що друкуються}, тоді A ⊆ P
• Якщо Q = {чотирикутник} і F = {проста фігура, обмежена чотирма прямими }, тоді Q ⊆ F

Слід пам’ятати, що A ⊆ B не означає, що В обов’язково має містити інші елементи окрім елементів множини А; дві множини можуть бути рівними, як Q і F вище. Однак, якщо, в додаток, В все ж містить хоча б один елемент, якого немає у множині А, ми можемо сказати що А є істинною підмножиною В. У такому випадку пишемо:

A ⊂ B

З прикладів вище:

E містить ... -4, -2, 0, 2, 4, 6, 8, 10, 12, 14, ... , тож T ⊂ E

P містить $, ;, &, ..., тож A ⊂ P

Але Q та F – просто два різних способи написання одного і того ж, тому Q = F

Використання ⊂ і ⊆ аналогічне використанню знаків < і ≤ при порівнянні чисел.

Зазначимо також, що кожна множина є підмножиною універсуму, а порожня множина – підмножиною кожної множини. (Ви можете поцікавитися стосовно останнього твердження: як може порожня множина бути підмножиною чогось, коли вона взагалі не містить елементів? Сенс тут полягає в тому, що для будь-якої множини А, порожня множина не містить будь-яких елементів, що не входять у А. Таким чином, Ø ⊆ A для всіх множин А.)

Насамкінець, зауважимо, що якщо A ⊆ B і B ⊆ A тоді A і B повинні містити однакові елементи, і , отже, бути рівними. Іншими словами:

Якщо A ⊆ B і B ⊆ A тоді A = B

Неперетинні множини

Дві множини називаються неперетинними, коли вони не мають спільних елементів. Наприклад:

• Якщо A = {парні числа} і B = {1, 3, 5, 11, 19}, тоді A і B неперетинні множини

Діаграми Венна

Діаграми Венна можуть бути корисним способом ілюстрації відношень між множинами. У діаграмах Венна:

• Універсум представлений прямокутником. Крапки всередині прямокутника вказують на елементи в універсумі; крапки зовні прямокутника – на елементи, що не входять в універсум.
• Інші множини презентовані кільцями (овалами або кругами) усередині прямокутника. Знову ж таки, крапки всередині фігури вказують на елементи в універсумі; крапки зовні – на елементи, що не входять до універсуму.