Курсовая работа: Комбінаторика

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

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

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

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

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

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

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

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

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

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

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

Р А х В

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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