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

Матеріал з Вікіпідручника

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

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

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

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

Способи опису множини[ред.]

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

Приклад. 1. Нехай перерахуванням задана множина Як її можна описати по іншому?

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 неперетинні множини

Діаграми Венна[ред.]

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

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