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

4. Як можна було б згрупувати різні за змістом відношення? – навколо певних наборів властивостей. У математиці відношення між елементами однієї множини поділяють принаймні на три групи: 1) відношення еквівалентності; 2) відношення порядку; 3) функціональні відношення. Розглянемо перші дві групи.

Означення: будь-яке рефлексивне, симетричне та транзитивне відношення f, визначене у множині Х, називається відношенням еквівалентності.

Прикладами відношень еквівалентності є відношення подібності на множині трикутників, паралельності на множині площин, «бути однокурсником» на множині студентів тощо. Як визначити, чи є задане відношення відношенням еквівалентності? – перевірити наявність у нього властивостей, які повинні бути у відношення такого типу. Покажемо це на конкретному прикладі.

Вправа: з’ясувати, чи є відношенням еквівалентності відношення «проживати на одній вулиці», задане на множині людей.

1. оскільки кожна людина проживає на одній вулиці сама з собою, то це відношення рефлексивне;

2. якщо людина А проживає на одній вулиці з людиною В, то і людина В проживає на одній вулиці з людиною А, тобто із (АαВ)→(ВαА);

3. якщо людина А проживає на одній вулиці з людиною В, а людина В проживає на одній вулиці з людиною С, то і людина А проживає на одній вулиці з людиною С, тобто із ((АαВ)^(ВαС))→(АαC).

Отже, відношення α:«проживати на одній вулиці», задане на множині людей, є рефлексивним, симетричним і транзитивним, а тому відноситься до відношень типу еквівалентності.

Розглядаючи поняття розбиття множини на підмножини, що попарно не перетинаються, ми з’ясували, що відношення «бути однокурсником» на множині студентів, розбило множину всіх студентів на п’ять підмножин. З’ясуємо властивості цього відношення. Легко бачити, що воно має властивості рефлексивності, симетричності і транзитивності (Чому?), а тому є відношенням типу еквівалентності. Сказане дає підстави припустити, що між розбиттям множини на класи, що попарно не перетинаються, і відношеннями типу еквівалентності існує певний зв'язок. Сутність цього зв’язку розкривається такою теоремою.

Теорема: для того, щоб відношення α дозволяло розбити множину Х на класи, що попарно не перетинаються, необхідно і достатньо, щоб відношення α було відношенням еквівалентності.

Оскільки у формулюванні цієї теореми є слова необхідно і достатньо, то доведення теореми складається із двох частин: 1) із доведення необхідності; 2) із доведення достатності. Цю теорему приймемо без доведення.

Означення: бінарне відношення α, визначене у множині Х, називається відношенням строгого порядку, якщо воно антирефлексивне, антисиметричне і транзитивне.

П рикладами відношень строгого порядку є: відношення «менше» у множині цілих чисел; відношення «бути старшим» на множині людей; відношення «бути вищим» на множині дерев тощо.

Означення: бінарне відношення α, визначене у множині Х, називається відношенням нестрогого порядку, якщо воно рефлексивне, антисиметричне і транзитивне.

Прикладами відношень нестрогого порядку є: відношення «більше або дорівнює» у множині раціональних чисел; відношення подільності на множині натуральних чисел тощо.

Означення: відношення порядку в множині Х називається відношенням лінійного порядку, якщо для будь-яких елементів х,уєХ виконується умова хαууαх. Якщо ж відношення не має такої властивості, то його називають відношенням часткового порядку.

Прикладом відношення лінійного порядку є відношення «більше» чи «менше» на множині чисел.

Означення: якщо відношення α в множині Х є відношенням часткового порядку, то множину Х називають частково впорядкованою множиною.

Означення: якщо відношення α в множині Х є відношенням лінійного порядку, то множину Х називають лінійно впорядкованою множиною.

Лінійно впорядковані множини мають ряд властивостей. Нехай а,в,сєХ і множина Х лінійно впорядкована відношенням α. Якщо відомо, що аαввαс, то говорять, що елемент в лежить між елементами а і с.

Означення: множина Х, яка лінійно впорядкована відношенням α, називається дискретною, якщо між будь-якими двома її елементами знаходиться лише скінченна множина елементів.

Прикладом дискретних множин є множини натуральних і цілих чисел.

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

Прикладом щільних в собі множин є множина дійсних чисел.

МОДУЛЬ 1: «Множини. Відповідності Відношення.».

Змістовний модуль1.3. «Елементи комбінаторики».

План.

1. Комбiнаторнi задачі. Правила суми i добутку.

2. Розміщення з повтореннями та без повторень.

3. Перестановки з повтореннями та без повторення.

4. Комбiнацiї та їх властивості.

ЛІТЕРАТУРА: [1] – с. 41-51; [2] – с. 54-64; [3] – с. 56-79.

1. Комбiнаторнi задачі. Правила суми i добутку.

1. Розглядаючи множини та операції над ними ми вказували, що порядок розміщення елементів немає значення, але є галузь математики, для якої порядок розміщення елементів множини має суттєве значення. Ця галузь математики називається комбінаторикою та розглядає задачі, пов’язані з розташуванням за певними правилами елементів скінченних множин i відшукання числа способів, якими це можна зробити. Такі задачі називаються комбінаторними. Наприклад: 1) скільки карточок спортлото потрібно купити, щоб точно вгадати 6 номерів? 2) скількома способами можна призначити в групі трьох чергових?; 3) скількома способами можна витягнути з колоди три карти, щоб набрати 21 очко?

Комбінаторика виникла з необхідності створення теорії азартних ігор. Найбільший вклад в її розвиток внесли П.Ферма, Б.Паскаль, Х.Гюйгенс, В.Лейбнiц, Я.Бернуллi. Значний інтерес до комбінаторики поновлюється в 50-х роках XX ст. у зв’язку з бурхливим розвитком кібернетики та дискретної математики i широким використанням електронно-обчислювальної техніки. Дуже широко використовується комбінаторика в теорії оптимального управління.

В комбінаториці є правила, які дозволяють елементарними способами розв’язати значну кількість комбінаторних задач. Розглянемо дві скінченні множини А i В такі, що n(A)=m і n(B)=k, причому АB=Ø. Якщо виконуються ці умови, то кількість елементів множини АВ визначається однозначно, тобто n(АВ)=m+k. Отже має місце таке твердження:

Правило суми: якщо множина А містить m елементів, а множина В - k елементів то множина AB містить m+k елементів.

Досить часто правило суми формулюють так:

Правило суми: якщо деякий елемент x з множини А можна вибрати m способами, а елемент y з множини В - k способами, причому жоден із способів вибору елемента x не співпадає зі способом вибору елемента y, то елемент x або елемент y можна вибрати m + k способами.

Це правило можна поширити на випадок будь-якої скінченної кількості множин. Розглянемо застосування цього правила до розв’язання наступних задач.

Задача 1: на столі є 4 ручки i 3 олівці. Скількома способами можна взяти зі столу один предмет?