Комбінаторика

З ВІДНОШЕННЯМ


§ 2. 1. Упорядковані пари. Прямий (декартів) добуток множин.

Множини {1,5} і {5,1}, що містять одні і ті ж самі елементи, рівні, причому запис порядку їх елементів не має значення. Проте, якщо розглядати на площині дві точки А (1,5) і В (5,1), то порядок запису їх координат (1 ; 5) має принципове значення. Можна навести і інші приклади, коли треба врахувати порядок розміщення елементів множини (вектор на площині, вектор у просторі). У зв’язку з цим вводиться поняття упорядкованої сукупності об’єктів, зокрема упорядкованої пари.

Упорядкована пара це двоелементна множина, елементи якої розміщені в певному порядку.

Якщо а є А і b є В, то пару утворену з цих елементів позначають (a; b).

Елемент а називають лівою (першою)координатою (компонентою), а

b – правою (другою) координатою упорядкованої пари (а; b).

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

Прямим (декартовим) добутком множин А і В називається множина усіх можливих пар, перші елементи яких належать множині А, а другій множині В і позначається А х В.

Отже, А х В = {(а; b)| а є А, b є В}

Декартів добуток множин не комутативний

А х В ≠ В х А

А х В = В х А лише тоді, коли А = В або одна із множин порожня.

Щодо асоціативного закону, то йому декарті добуток не підлягає навіть тоді, коли множини А, В і С рівні. Отже, якщо А ≠ Ш, то А х (А х А) ≠ (А х А) х А.

Для прямого добутку справедливі такі дистрибутивні закони:

(А В) х С = (А х С) (В х С)

А х (В С) = (А х В) (А х С)

(А ∩ В) х С = (А х С) ∩ (В х С)

А х (В ∩ С) = (А х В) ∩ (А х С)

А х (В С) = (А х В) (А х С)

Декартів добуток АхА називають декартовим квадратом і позначається

А І = А х А = {(a, b) | а є А, b є А}

Декартів добуток множин А, В, С визначається так само як і декартів добуток двох множин

А х В х С = {(a, b, с) | а є А, b є В, с є С}

Декарті добуток А х А х А називається декартовим кубом і позначається

А і = А х А х А

Якщо множину дійсних чисел R = (- ∞: + ∞) можна ототожнювати з числовою прямою, то декартів квадрат R х R дійсних чисел можна ототожнювати з числовою площиною. Очевидно, R х R – сукупність всіх можливих упорядкованих пар дійсних чисел (х; y).

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

У зв’язку з цим прямий добуток множин і називають декартовим.

§ 2. 2. Бінарні відношення. Способи задання відношень.

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

Розглянемо бінарне відношення, тобто відношення між двома елементами однієї або різних множин.

Спочатку розглянемо приклад бінарного відношення між елементами двох множин А і В.

А = {Сашко, Борис, Володя, Галя, Таня, Оленка}

В = {футбол, волейбол, плавання, гімнастика, теніс}

За допомогою слів „займатися яким-небудь видом спорту” між елементами цих множин встановлено зв’язок, або, як говорять в математиці, відношення. В результаті ми одержали третю множину Р

Р = {(Сашко, волейбол), (Сашко, теніс), (Борис, футбол),

(Володя, плавання), (Галя, волейбол), (Оленка, теніс)}

Наведений приклад показує, що будь-яке бінарне відношення (відповідність) між елементами множин А і В повністю характеризується трьома множинами: А, В і Р – множиною пар, що є підмножиною А х В.

Р А х В

Множину упорядкованих пар Р називають графіком розглядуваного відношення.

Якщо буквою р позначити відношення із А в В, то відповідність р: „учень х є А займається видом спорту у є В залишається: хру.

У математиці досить часто доводиться мати справу з тими чи іншими відношеннями між певними об’єктами.

Найважливіші з них мають певні назви і позначення:

відношення рівності (═); відношення перпендикулярності (); відношення паралельності (║); відношення подільності ; відношення включення (); відношення конгруентності (); відношення подібності (~).

Бінарне відношення можна задати сукупністю впорядкованих пар, стрілочним і графічним способами.

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

При графічному зображенні відношення Р на площині ставимо точки, які відповідають парам (х; у), що належать відношенню Р. Множина цих точок і буде графіком даного відношення.


§ 2. 3. Властивості бінарних відношень.

Найважливішими властивостями бінарних відношень є рефлексивність, симетричність, транзитивність.

Бінарне відношення р називається рефлексивним, якщо для будь-якої пари (х, х) є А І, елемент х знаходиться у відношенні р сам з собою.

Антирефлексивним називається таке відношення для якого х не знаходиться у відношенні р з х для будь-якої пари (х, х) є А І.

Рефлексивним є, наприклад, такі відношення рівності (═), не більше (≤), подільності (), рівносильності висловлювань (), паралельності (║), конгруентності () та подібності (~).

Антирефлексивними є відношення нерівності (≠), більше (>), менше (<), перпендикулярності (), не подільності ().

Бінарне відношення р називається симетричним, якщо для пари

(х, у) є А І із хру випливає урх.

Антисиметричним називається таке відношення для якого для будь-якої пари (х, у) є А І із хру випливає .

Симетричними є відношення рівності (═), рівносильності (≡), перпендикулярності (), конгруентності (), подібності (~).

Асиметричними є відношення більше (>), менше (<), не більше (≤), включення ().

Бінарне відношення р називається транзитивним, якщо для будь-яких трьох елементів х, у, z з множини А із хру і урz випливає xpz.

Антитранзистивним відношенням називається таке відношення для якого для будь-яких трьох елементів х, у, z з множини А із хру і урz випливає

Транзитивним є відношення менше (<), не більше (≤), подільності (), рівносильності (≡), конгруентності (), паралельності (║), подібності (~).

Антитранзистивними є відношення перпендикулярності ().

Відношення між елементами множин можуть мати одну, дві, три або не володіти ні однією властивістю.

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


§ 2. 4. Відношення еквівалентності.

Бінарне відношення р називається відношенням еквівалентності, якщо воно рефлексивне, симетричне і транзитивне.

Відношення: „бути однокурсником” у множині студентів; „мати один і той же корінь” у множині слів є відношеннями еквівалентності.

Якщо між елементами деякої множини, встановлено відношення еквівалентності, то цим самим ми розбиваємо задану множину на класи.

Розглянемо відношення р: „давати однакову остачу при діленні на 3” у множині невід’ємних цілих чисел. Цим самим ми розбиваємо задану множину на такі класи, які не перетинаються:


К1 = {0, 3, 6, 9 ......} – остача нуль

К2 = {4, 7, 10 ......} – остача один

К3 = {5, 8, 11 ......} – остача два

Класи, на які відношення еквівалентності розбиває множину А називаються класами еквівалентності. Це розбиття характеризується такими властивостями:

1. Ці класи не порожні

Кі ≠ Ш для всіх і = 1, 2, 3, ......, n

2. Будь-які два класи не перетинаються

Кі ∩ Ку = для будь-яких і, у = 1, 2, 3, ......, n

3. Об’єднання усіх класів дає універсальну множину А

Кі = А

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

Теорема

Будь-яке відношення еквівалентності р здійснює розбиття множини А на класи еквівалентності так, що будь-які два елементи одного класу знаходяться у відношенні р, а будь-які два елементи різних класів не знаходяться у даному відношенні між собою.

Доведення

Нехай в множині А є відношення еквівалентності р. Візьмемо з цієї множини якийсь елемент а і виділимо в окремий клас К (а) всі елементи, які знаходяться з а у відношенні р

К (а) = {у | у є А, ару} (1)

Задане відношення р розіб’є всю множину А на ряд класів К, в результаті чого ми одержимо множину класів {К (а)}.

Доведемо, що множина {К (а)} для всіх а є А є розбиттям на класи, тобто що вона задовольняє трьом умовам розбиття на класи, а саме, що:

1) К (а) ≠ Ш

2) К (а) ∩ К (b) = Ш

3) К (а) = А

Покажемо, що справедлива перша умова.

Раз р є відношенням еквівалентності, то воно є рефлексивне, тобто ара. Значить К (а) має хоча б один елемент а і вже К (а) не порожня множина

К (а) ≠ Ш

Покажемо, що справджується умова 2) для будь-яких а і b є А,

якщо а b.

Доведемо цю умову виходячи з протилежного.

Припустимо, що К (а) ∩ К (b) ≠ Ш. Тоді у них є спільний елемент с, тобто

с є К (а) і с є К (b)

Але елементи одного класу, відповідно до (1) знаходяться у відношенні р між собою, значить

арс і bрс

Із симетричності відношення р із bрс слідує срb, а із транзитивності відношення р випливає:

якщо арс і срb, то арb.

А це протирічить умові, що аb.

Значить, припущення не вірне і

К (а) ∩ К (b) = Ш.

Покажемо, що виконується і умова 3).

Із формули (1) видно, що будь-який а є А належить класові К (а), тобто

а є К (а). Отже, щоб одержати множину А треба об’єднати усі ці класи

К (а) = А

а є А

Ми довели, що відношення р розбиває множину А на класи еквівалентності.

Тепер покажемо, що: 1) два елементи одного класу еквівалентні між собою, а 2) два елементи різних класів не еквівалентні. Доведемо перше.

Нехай b і с будь-які два елементи одного класу К (а). Доведемо, що bрс. Раз b є К (а), то по формулі (1) – арb, а з того, що с є К (а) слідує, що арс. За симетричністю відношення р – з а р b слідує b р а. За транзитивністю відношення р маємо bра і арс, то bрс.

Доведемо друге. Нехай маємо два різні класи К (b) ≠ К (с). Покажемо, що b с. Доведемо від супротивного. Припустимо, що bрс. Нехай d – довільний елемент множини К (с), тоді cpd.

За симетричністю р маємо із bрс слідує срb.

За транзитивністю із bрс і срd слідує bpd.

Значить d є К (b).

Ми довели, що якщо d є К (с), то d є К (b) для вільного d.

Отже, К (с) К (b).

Аналогічно доводимо, що К (b) К (с).

Отже, К (b) = К (с).

А це протирічить умові. Значить, наше припущення не вірне і bс.


§ 2. 5. Відношення порядку. Упорядкована множина.

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

Інтуїтивне представлення про порядок об’єктів переважно пов’язано з їх взаємним розміщенням в просторі (вище – нижче, ближче – дальше, правіше – лівіше); в часі (раніше – пізніше); з порівнянням їх розмірів (більше – менше, легше – тяжче).

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

Відношенням строгого порядку називається будь-яке відношення, яке є антирефлексивним, антисиметричним і транзитивним.

Отже, відношення р буде відношенням строгого порядку, якщо:

  1. хх для будь-якого х є А, тобто (х, х)

    Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
    Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

    Поможем написать работу на аналогичную тему

    Получить выполненную работу или консультацию специалиста по вашему учебному проекту
    Нужна помощь в написании работы?
    Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: