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

Дискретна математика – це галузь математики, яка вивчає дискретні об’єкти, тобто чітко віддільні частини. Наприклад, лего-кубики або картки є дискретними. Ми можемо комбінувати або розташовувати їх по-різному, але завжди працюємо з ними поодинці.

Термін “дискретна математика” і назви окремих галузей можуть звучати абстрактно і складно. Проте їх можна застосовувати навіть у легко уявних випадках, наприклад, у різних іграх.

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

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

Комбінаторика займається підрахунком можливостей, як можна комбінувати об’єкти один з одним. За допомогою комбінаторики можна визначити кількість способів розподілу групи гравців на дві футбольні команди.

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

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

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

Для роботи з множинами потрібно спочатку опанувати основні поняття і позначення та ознайомитися з різними способами запису множин (переліком, характеристичною властивістю, стандартним позначенням).

З множинами можна виконувати множинні операції, як-от, об’єднання та перетин. Ці операції спочатку бажано відпрацювати на конкретних прикладах. Коли ми розуміємо окремі випадки, настає черга загальних властивостей множин і множинних операцій. Для отримання уявлення та інтуїції корисно зображати множини за допомогою діаграм Венна.

До складніших тем належать множини множин та булеан.

Множина — це набір елементів. У множині не важливий порядок елементів і не враховуються повторювані елементи. Такі множини є однаковими:

• \{\square, \bigcirc, \triangle\}
• \{\bigcirc, \triangle, \square\}
• \{\square, \square, \square, \bigcirc, \bigcirc, \triangle\}

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

Інші множини записуємо двома основними способами:

Запис переліком. Просто перераховуємо елементи множини і записуємо їх за допомогою фігурних дужок. Наприклад, M = \{3, 7, 9\} – це триелементна множина, яка містить числа 3, 7 і 9.

Запис за допомогою характеристичної властивості. Визначаємо, з якої множини вибираємо елементи та яку властивість вони мають задовольняти. Наприклад, M = \{x \in \mathbb{N} \mid x < 10\} – це множина натуральних чисел, менших за 10.

• Кожна множина є своєю підмножиною: A\subseteq A.
• Множина не може бути своєю власною підмножиною.
• Порожня множина є підмножиною будь-якої множини: \emptyset \subseteq A.
• Порожня множина не має жодної власної підмножини.
• A \subseteq A \cup B
• A \cap B \subseteq A
• A \subseteq A \wedge B \subseteq A \Leftrightarrow A=B

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

Типова діаграма Венна для трьох множин:

Приклад із конкретними елементами (множина A містить червоні фігури, множина B містить кола, множина C містить заповнені фігури):

Діаграми Венна використовуються, наприклад, для наочної ілюстрації операцій над множинами. Наступний рисунок ілюструє B \cap (A \cup C):

Множина як елемент множини

Елементом множини може бути інша множина. З таким елементом працюємо так само, як і з іншими елементами, лише не варто плутатися.

Приклад: множина M = \{a, \{b, c, d, e\}, \emptyset\} містить три елементи:

• “звичайний” елемент a
• чотириелементну множину \{b, c, d, e\}
• порожню множину \emptyset

Слід відрізняти порожню множину від множини, яка містить порожню множину:

• \emptyset (також можемо записати \{\}) — це порожня множина, її розмір дорівнює 0,
• \{\emptyset\} — це множина, яка містить порожню множину, її розмір дорівнює 1.

Булеан

Булеан M містить усі підмножини множини M. Булеан позначаємо \mathcal{P}(M) (існують також інші позначення, наприклад, 2^M).

Приклад: для множини M = \{a, b, c\} усі її підмножини:

• \{\}
• \{a\}
• \{b\}
• \{c\}
• \{a, b\}
• \{a, c\}
• \{b, c\}
• \{a, b, c\}

Булеан — це множина всіх цих множин, тобто \mathcal{P}(M)=\{\{\}, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}.

Булеан множини M завжди містить як свій елемент саму множину M. Оскільки сама множина M є своєю підмножиною, вона обов’язково міститься у булеані.

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

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

Огляд тем з логіки, доступних на Знаємо математику:

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

Твердження

Твердження — це судження, для якого має сенс питання, чи є воно правдивим чи неправдивим, причому може бути лише одна з цих можливостей.

Приклади тверджень:

• Місто Харків знаходиться в Україні (правдиве твердження)
• Харків є столицею України (неправдиве твердження)
• На Марсі закопано скарб (твердження, істинність якого нам невідома)

Приклади речень, які не є твердженнями: Ти голодний? Піди до крамниці за яйцями.

Логічні сполучники

Тавтології та суперечності

Тавтологія — це формула твердження, яка завжди правдива. Приклади:

• A \vee \neg A (закон виключеного третього)
• (A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \neg A)

Суперечність — це формула твердження, яка завжди є неправдивою. Прикладом є формула A \wedge \neg A (закон протиріччя).

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

Таблиця істинності логічних операцій

Переписування імплікації та еквівалентності

Заперечення складених тверджень

Правила для заперечення диз’юнкції та кон’юнкції (2-й та 3-й рядок таблиці) називаються Законами де Моргана.

Аналогічні закони, як і при обчисленні з числами

Для логічних операцій \wedge, \vee також діють комутативні (1-й та 2-й рядок наступної таблиці), асоціативні (3-й та 4-й рядок) та дистрибутивні закони (5-й та 6-й рядок):

Квантифікатори

Приклади висловів з квантифікаторами

Властивість: число x парне можна виразити, як існує ціле число k таке, що x = 2\cdot k. Це можна записати як \exists k \in \mathbb{Z}: x = 2\cdot k.

Твердження Підводні човни (P) не можуть літати (L). можна записати, як \forall x: P(x) \Rightarrow \neg L(x).

У складніших висловах з кількома квантифікаторами ми маємо дбати про порядок квантифікаторів:

• \exists x\in M\ \forall y \in M: y \leq x – існує елемент у множині M, який є більшим або рівним усім іншим елементам у M, тобто вислів каже, що множина має найбільший елемент.
• \forall x\in M\ \exists y \in M: y \leq x – для кожного елемента у множині M існує елемент x, який менший або рівний X. Оскільки можна вибрати y=x, то це виконується для будь-якої множини (для просунутих: лише якщо розглядаємо множини чисел і \leq як звичайне упорядкування на числах).

\exists x\in M\ \forall y \in M: y \leq x – існує елемент у множині M, який є більшим або рівним усім іншим елементам у M, тобто вислів каже, що множина має найбільший елемент. \forall x\in M\ \exists y \in M: y \leq x – для кожного елемента у множині M існує елемент x, який менший або рівний x. Оскільки можна вибрати y=x, це виконується для будь-якої множини (для просунутих: лише якщо розглядаємо множини чисел і \leq як звичайне упорядкування на числах).

Заперечення тверджень з квантифікаторами

Під час заперечення тверджень з квантифікаторами змінюємо існуючий квантифікатор на загальний (і навпаки) і переміщуємо заперечення «всередину». Приклад:

• Не є правдою, що всі коти (К) чорні (Ч).
• \neg (\forall x: K(x) \Rightarrow C(x))
• Змінюємо загальний квантифікатор на існуючий і заперечуємо твердження.
• \exists x: \neg(K(x) \Rightarrow C(x))
• Тепер заперечуємо імплікацію за допомогою правила \neg(A \Rightarrow B) \Leftrightarrow (A \wedge \neg B).
• \exists x: K(x) \wedge \neg C(x)
• Існує кіт, який не є чорним.

Терміни

• Перестановка – це розміщення елементів у фіксованому порядку.
• Комбінація (k елементів) – це вибір k елементів із заданої множини.
• Комбінація з повторенням (k елементів) – це вибір k елементів із заданої множини, причому елементи можуть повторюватися.
• Варіація (k елементів) – це впорядкований вибір k елементів із заданої множини.
• Варіація з повторенням (k елементів) – це впорядкований вибір k елементів із заданої множини, причому елементи можуть повторюватися.

Приклади

Формули

Кількість перестановок, комбінацій та варіацій наведено в наступній таблиці:

Комбінаторне число вказує на кількість комбінацій, тобто способів, як вибрати k елементів із множини з n елементів. Комбінаторні числа дуже часто зустрічаються в комбінаторних обчисленнях, тому мають спеціальне позначення \binom{n}{k} (читаємо „n над k“).

Для n \geq k \geq 0 виконується формула: \binom{n}{k} = \frac{n!}{k!(n-k)!}

Для комбінаторних чисел існує ряд інших співвідношень, наприклад:

• \binom{n}{k} = \binom{n}{n-k}
• \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}
• \sum_{k=0}^n \binom{n}{k} = 2^n

Приклади:

Випадкова подія — це результат випадкового експерименту, щодо якого можна після його проведення визначити, чи відбулася вона, чи ні. Її типовою ознакою є те, що вона може (але не обов’язково повинна) відбутися. Імовірність події — це міра очікування, що подія станеться. Імовірність — це число між 0 та 1. У повсякденному житті ми часто виражаємо ймовірність у відсотках, що є стократним збільшенням імовірності, яку використовують у математиці.

Поняття та позначення

Приклад

• У мішечку є п’ять куль, з яких дві червоні, дві сині та одна жовта. Кулі повністю однакові, крім кольору. Експеримент полягає в тому, щоб навмання витягнути кулю з мішечка.
• «Витягну червону кулю» — це випадкова подія. Це елементарна подія. Її імовірність становить 0,4 (у повсякденному житті ми могли б сказати: 40%).
• «Витягну червону або жовту кулю» — це складена подія. Її імовірність становить 0,6.
• «Витягну кулю» — це достовірна подія.
• «Витягну зелену кулю» — це неможлива подія.

Статистична сукупність має обсяг n, оскільки вона містить саме n одиниць. Наприклад, статистичною сукупністю з обсягом 10 може бути група з 10 дітей з третього класу. Окремі учні та учениці є одиницями статистичної сукупності.

Приклади статистичних ознак, які можуть нас цікавити: ім’я, зріст або оцінка з природознавства. Припустімо, що імена дітей нашої групи з десяти учнів такі: Анна, Єва, Ян, Ян, Ян, Ванесса, Ванесса, Маринка, Гліб, Миколка.

Отже, ознака імені в нашій статистичній сукупності набуває семи різних значень: Анна, Єва, Ян, Ванесса, Маринка, Гліб, Миколка. Деякі діти можуть мати однакові імена.

Абсолютна частота значення ознаки в даній статистичній сукупності – це кількість одиниць статистичної сукупності, які мають дане значення ознаки.

Наприклад, абсолютна частота значення „Ян“ ознаки імені становить 3, оскільки у групі є три учні на ім’я Ян. Абсолютна частота значення „Єва“ ознаки імені становить 1.

Відносна частота значення ознаки в даній статистичній сукупності обчислюється як частка кількості одиниць з даним значенням ознаки до загальної кількості одиниць статистичної сукупності. Також можна сказати, що відносна частота значення ознаки – це частка абсолютної частоти цього значення ознаки та обсягу n статистичної сукупності. Відносна частота подається як число в інтервалі [0,1] або у відсотках.

Наприклад, відносна частота значення „Ванесса“ ознаки імені дорівнює \frac{2}{10}=0{,}2, оскільки у групі загалом з десяти дітей є дві учениці на ім’я Ванесса. Відносну частоту значення „Ванесса“ ознаки імені можна записати також як 20\ \%.

Сума абсолютних частот усіх значень однієї ознаки дорівнює обсягу n даної статистичної сукупності.

Сума відносних частот усіх значень однієї ознаки дорівнює 1 або 100\ \%.

Кореляція – це зв’язок між двома величинами. Коефіцієнт кореляції – це число, яке виражає силу цього зв’язку.

Існує кілька способів вимірювання кореляції. Найчастіше використовується коефіцієнт кореляції Пірсона. Він позначається r і має такі властивості:

• Набуває значень з інтервалу [-1, 1].
• Вимірює лише лінійну залежність між величинами.
• Якщо значення додатне, збільшення однієї величини відповідає збільшенню іншої.
• Якщо значення від’ємне, збільшення однієї величини відповідає зменшенню іншої.
• Якщо значення нульове, між величинами немає лінійної залежності.
• Якщо значення точно 1 або -1, між величинами є точна лінійна залежність.