Комбінаторика
§ 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. Відношення порядку. Упорядкована множина.
Серед
різних відношень
ми часто зустрічаємо
такі, які встановлюють
у множині певний
порядок.![]()
Інтуїтивне представлення про порядок об’єктів переважно пов’язано з їх взаємним розміщенням в просторі (вище – нижче, ближче – дальше, правіше – лівіше); в часі (раніше – пізніше); з порівнянням їх розмірів (більше – менше, легше – тяжче).
Ці відношення і подібні їм відносяться до важливого класу відношень, що називають відношеннями порядку.
Відношенням строгого порядку називається будь-яке відношення, яке є антирефлексивним, антисиметричним і транзитивним.
Отже, відношення р буде відношенням строгого порядку, якщо:
х
х
для будь-якого
х є А, тобто (х,
х)
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.Нужна помощь в написании работы?Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.