klevoz.ru страница 1
скачать файл




Лекція № 1

Тема: Елементи теорії множин і відношень

План лекції:

0. Зміст та задачі дискретної математики.

1. Поняття множини. Способи задання множини.

2. Відношення між множинами. Діаграми Ейлера-Венна.

3. Основні операції над множинами.

4. Властивості операцій над множинами.

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

6. Основні поняття теорії відношень.

7. Графічне представлення відношень.

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

9. Розбиття і відношення еквівалентності.

10. Відношення порядку.
Література:

Бардачов Ю.М. та ін. Дискретна математика. – К.: Вища школа, 2002. – 287с. – с. 14-21; 81-106.


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

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

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

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

Основними задачами дискретної математики є:


  • з'ясування того, які властивості мають ті чи інші дискретні об’єкти разом з заданими на них функціями, операціями, відношеннями (аналіз);

  • побудова дискретних об’єктів, які задовольняють заданим властивостям (синтез).

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

Сьогодні дискретна математика є важливою ланкою математичної освіти, вона є фундаментом для вивчення практично всіх спеціальних курсів, які читаються в технічних вузах. Дискретна математика включає такі вже сформовані розділи математики, як теорію множин, математичну логіку, теорію алгебраїчних систем, комбінаторику і нові розділи, які найбільш інтенсивно стали розвиватися в середині XX сторіччя в зв'язку з науково-технічним прогресом і масовим використанням ЕОМ: теорію графів, теорію алгоритмів, теорію кодування, теорію скінчених автоматів та ін.


1. Поняття множини. Способи задання множини
Теорія множин є теоретичною основою не лише дискретної, а й усієї сучасної математики.

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

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

Під множиною розуміють сукупність певних об’єктів, які об’єднані спільними властивостями. При цьому природа самих об'єктів, що становлять ту або іншу множину нас не буде цікавити. Творець теорії множин Георг Кантор давав наступне означення множини – "множина є багато чого, мислиме нами як ціле."

У повсякденному житті та практичній діяльності для позначення поняття множини використовують також слова: набір, клас, система, комплекс і т. ін. Але й у математиці термін множина має низку синонімів. Так, замість «множина значень змінної» можна сказати «область значень змінної», замість «множина кривих» – «сім’я кривих», замість «множина двох рівнянь» – «система двох рівнянь» і т. ін.



Об’єкти будь-якої природи, що утворюють множину, називаються її елементами. Наприклад, в множині студентів університету елементом буде студент, в множині днів тижня елемент – «четвер». Елементами множин можуть бути самі множини. Наприклад, множина академгруп університету, кожна академгрупа – множина студентів.

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

Для деяких особливо важливих числових множин прийняті стандартні позначення, яких слід дотримуватися. Так, буквами , , Q, R позначають відповідно множину натуральних чисел, множину цілих чисел, множину раціональних чисел і множину дійсних чисел.

Для позначення елементів множин використовують малі букви латинського алфавіту: або малі букви з індексами .

Належність елемента множині позначається символом : – елемент належить множині (знак є стилізацією першої букви грецького слова – бути, існувати); неналежність елемента множині позначається символом : .

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

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



Способи задання множин

1. Найбільш природним є спосіб задання множини переліком (або списком) елементів.

Наприклад: .

Порядок елементів у записі множини значення не має:

.

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

Приклади стислого представлення множин:
1. ;

2. ;

3. .

2. Універсальним є спосіб задання множини за допомогою характеристичних властивостей її елементів (тобто властивостей, які мають всі елементи даної множини і тільки вони). Наприклад:

1. ,

2. ;

3. .



3. Аналітичний, за допомогою символів операцій над множинами та дужок.

4. Вербальний (мовний) за допомогою опису характеристичних властивостей, які повинні мати елементи множини.
2. Відношення між множинами. Діаграми Ейлера-Венна
В множині можуть бути виділені підмножини.

Означення. Множина називається підмножиною множини , якщо кожен елемент множини належить множині .

Це позначається як () – « включається в » ( включає ), де – знак нестрогого включення. Кажуть, що множини і знаходяться у відношенні включення, а елементи множини до самої множини – у відношенні належності.

Наприклад: , , – підмножина .

Позначення: – « включається в А», – знак нестрогого включення.

Якщо и , то називається власною, строгою чи істинною підмножиною . Позначення: , де – знак строгого включення.

Очевидно, що для будь-якої множини і .



і називаються невласними підмножинами множини .

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

Означення. Множини і називаються рівними, якщо вони складаються з одних і тих самих елементів.

Приклад. , .

Множини і рівні (=), якщо і :



і

Для кожної множини існує множина, елементами якої є всі її підмножини.



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

У разі скінченної підмножини , що складається з елементів, булеан містить елементів:



.

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



Приклад. Розглянемо утворення булеана множини:

:

;



:

.

Перша й остання підмножини невласні, інші – власні.

Порожня множина має властивість: при будь-якому . Універсальна множина має властивість: при будь-якому .


Множини і відношення між ними зручно задавати графічно за допомогою так званих діаграм Ейлера-Венна. Діаграми Ейлера-Венна (Джон Венн (1834-1923) англійський логік і математик, професор Кембриджського університету) є геометричним зображенням множин. Множина зображується замкненою кривою довільної форми (найчастіше – кругом). Точки, які лежать всередині замкненої кривої, можна розглядати як елементи відповідної множини.

Наприклад:

Універсум на діаграмах Ейлера-Венна зображується у вигляді прямокутника.



Діаграму Ейлера-Венна можна розглядати як окремий випадок задання множини переліком його елементів. В цьому випадку всередині діаграми Ейлера-Венна можуть бути зображені символічні позначення елементів.



Наприклад: На наступній діаграмі Ейлера-Венна задані множини , в універсумі :



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

,

де – знак об’єднання.

На діаграмі Ейлера-Венна об’єднання показується штриховкою:




Об’єднання складається з усіх елементів множини , усіх елементів множини і не містить ніяких інших елементів.

Об’єднання називається також теоретико-множинною сумою.

Операція об’єднання узагальнюється на довільну сукупність множин.

У загальному випадку використовується позначення:



.

Приклади:

  1. , , ;

  2. , , ;

  3. {парні числа}, {непарні числа }, .

Означення. Перерізом двох множин і називається множина , яка складається з усіх тих і тільки тих елементів, що належать і , і В:
,

де – знак перерізу.

На діаграмі Ейлера-Венна переріз показується штриховкою:




Переріз називається також теоретико-множинним добутком.

Операція перерізу узагальнюється на довільну сукупність множин.

У загальному випадку використовується позначення:

.

Приклади:


  1. , , ;

  2. , , ;

  3. , ,

  4. {прямокутники}, {ромби}, {квадрати}.


Означення. Різницею множин і називається множина , яка складається з усіх тих елементів множини , які не належать :

,

де – знак різниці.



Приклади:

  1. , , , ;

  2. , , ;

  3. , {непарні числа}, {парні числа}.

В означенні різниці, взагалі кажучи, не припускається, що . Якщо , то різниця називається доповненням множини В до множини і позначається .

Проілюструємо поняття різниці множин за допомогою діаграм Ейлера-Венна:






Означення. Різниця універсальної множини і будь-якої її підмножини А називається доповненням множини до універсальної . Позначається .

Геометрична ілюстрація:




Означення. Симетричною різницею множин і називається різниця об’єднання і перерізу множин і (виключне "АБО"), яка позначається .

,

де

Приклади:


  1. , ,

.

Геометрична ілюстрація:



Використовуючи операції ∩¸ ¸ \¸ можна виражати одні множини через інші. За умовчанням приймається пріоритет операцій: . Для зміни цього порядку у виразі використовують дужки.

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

Приклад. Нехай ; ; ; .

;

;


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

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




1. – комутативність

1*. – комутативність

2.

асоціативність



2*. – асоціативність

3. – дистрибутивність відносно

3*. – дистрибутивність відносно

закони поглинання

4.

4*.

закони де Моргана

5.

5*.

6.




закони ідемпотентності

7.

7*.

властивості і

8.



8*.



9.

9*.

10. ,

11.




12.





5. Декартовий добуток множин
Введемо ще одну операцію над множинами.

Нехай і – довільні множини.



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

Дві впорядковані пари вважаються рівними, якщо рівні їх відповідні компоненти:



.

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

.

Якщо , то кажуть про декартовий квадрат множини :



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


Приклади:

1. Нехай , , . Тоді



;

;

.

2. , – множини символів, які позначають горизонтальні і вертикальні поля шахівниці. Тоді – множина всіх кодів кліток шахівниці.

3. Нехай R – множина всіх дійсних чисел. Тоді декартовий квадрат є просто множина всіх декартових координат на площині відносно заданих координатних осей (– множина точок площини). Якщо , то – одиничний квадрат на площині.

4. – множина точок простору. Якщо , то – одиничний куб на площині.



5. – скінченна множина , елементами якої є символи (букви, цифри, розділові знаки і т.д.), тобто /– алфавіт. Елементи множини називаються словами довжини в алфавіті . Множина усіх слів в алфавіті є . При написанні слів (які за означенням є -ками) не прийнято користуватися ні комами, ні дужками як роздільниками, але вони можуть виявитися символами самого алфавіту. Тому слово в алфавіті – це просто скінчена послідовність символів алфавіту . Наприклад, десяткове ціле число – слово в алфавіті {0,1, …, 9}. Текст, надрукований на принтері є словом в алфавіті, обумовленому довжиною клавіатури (включаючи розділові знаки і пробіл).
6. Основні поняття теорії відношень
Означення. Для будь-яких двох множин і довільна підмножина називається бінарним відношенням між і (або просто на , якщо =). Для впорядкованої пари використовують позначення і кажуть, що знаходиться у відношенні з . Якщо ж два елементи не зв’язані відношенням , то записуємо , або .

Приклади. 1. Нехай . Визначимо на цій множині відношення : . Явний запис відношення має вигляд:

.

2. Множина є відношенням на множині :; ; .

3. Множина є відношенням на множині : ; , ,.

4. Множина є відношенням на множині .

5. Множина всіх пар точок , площини таких, що , є відношенням ”бути симетричним відносно осі ”.

6. Множина задає добре знайомі декартові координати точки на площині. Оскільки ця множина дорівнює множині , то за означенням вона є відношенням.

7. На множині людей також можна вказати відношення: „бути начальником”, „бути братом”, „бути молодшим”, „жити в одному місті”, «вчитися в одній академгрупі».

Для будь-якої непорожньої множини визначимо такі окремі випадки відношень:



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

Таким чином, .

Універсальними є: відношення з прикладу 7, відношення „вчитися в одній академгрупі” на множині студентів групи ІБД 2х.

Означення. Порожнім відношенням називається відношення, яке не виконується для жодної пари елементів множини .

Таким чином, оскільки , то є відношенням на .

Порожнім є відношення „бути братом” на множині жінок.

Означення. Тотожним (діагональним) відношенням називається відношення, яке виконується тільки між елементом і ним.

.

Тотожнім є відношення з прикладу 5.

З кожним бінарним відношенням на множинах і зв’язані дві множини – область визначення і область значень.

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

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

Приклад. Розглянемо відношення з прикладу 1, явний запис якого має вигляд:

.

Тоді , .



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

Оскільки відношення – це множина, над ним можна виконувати всі теоретико-множинні операції: переріз, об’єднання, віднімання, доповнення. Крім того для відношень має зміст операція обернення. Перехід від до здійснюється взаємною перестановкою компонент кожної пари, яка входить до відношення.



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

.

Таким чином, обернене відношення зв’язує ті ж самі пари елементів, що й , але в зворотному порядку. Отже, якщо , то і , .

Приклад. Нехай і : . Тоді

.
7. Графічне представлення відношень
Графічні представлення відношень мають властивість наочності (при невеликих ) і можливі в наступних формах:

1. Графіки. В декартовій системі координат на осях (ось абсцис відповідає області визначення , ось ординат – області значень ) відмічаються точки, які являють собою елементи множин і , на яких визначено відношення . Потім відмічаються точки з координатами , в яких , .

Наприклад, графіки відношень з прикладів 1, 2 і 4 мають відповідно такий вигляд:


1 2 4

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



Приклад. Стрілкова схема 1 для приклада 1 має вигляд:



Стрілкова схема 2. На двох вертикальних лініях відмічаються точки, які являють собою елементи множин і . Потім з’єднуються стрілками точки на осях, які відповідають елементам .

Приклад. Стрілкова схема 2 для приклада 1 має вигляд:


Стрілкова схема 3. Будується графічна діаграма у вигляді множин точок (вузлів), які являють собою елементи множин і . Потім з’єднуються стрілками пари точок, які входять у відношення .

Приклад. Стрілкова схема 3 для приклада 1 має вигляд:

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



Приклад. Таблиця для приклада 1 має вигляд:



1

2

3

4

5

6

1

1

1

1

1

1

0

2

0

1

0

1

0

0

3

0

0

1

0

0

0

4

0

0

0

0

0

0

5

0

0

0

0

0

0

6

0

0

0

0

0

0


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

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



Означення. Відношення називається рефлексивним, якщо воно завжди виконується між елементом і ним самим. ().

Приклади.

  1. Відношення нестрогої нерівності на множинах .

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

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

Приклади.

1. Відношення строгої рівності на множинах .

2. Відношення „бути начальником”, „бути братом”, „бути молодшим” на множині людей.

Приклад відношення, яке не є ні рефлексивним, ні антирефлексивним :

Відношення ”бути симетричним відносно осі ” не є ні рефлексивним, ні антирефлексивним (точка є симетричною самій собі, якщо вона лежить на осі , і не є симетричною самій собі в протилежному випадку)



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

Приклади:

1. Відношення рівності на множинах .

2. ”Бути симетричним відносно осі ”.

3. Відношення „бути братом” на множині людей.

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

Означення. Відношення називається антисиметричним, якщо і виконуються одночасно тоді і тільки тоді, коли . ()

Приклади:

1. Відношення нестрогої нерівності на множинах .



и .

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



Зауваження. Властивості симетричності і антисиметричності не є взаємно виключними.

Означення. Відношення називається асиметричним, якщо для будь-яких елементів або або . ()

Приклади.

1. Відношення строгого включення в множині всіх підмножин деякого універсуму.

2. Відношення „бути батьком” в множині людей.

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

Приклади.

1. Відношення =, , «жити в одному місті».

2. Відношення ‘‘мати непорожній переріз’’ на системі множин не є транзитивним.

На графі транзитивного відношення для кожної пари стрілок, напрямлених від до і від до існує також стрілка, напрямлена від до .


9. Розбиття і відношення еквівалентності
При роботі з множинами, які містять велику кількість елементів часто буває зручно розбити їх на підмножини меншої потужності, щоб дослідити потрібні властивості. Розглянемо способи отримання таких розбиттів.

Означення. Покриттям непорожньої множини називається сукупність підмножин таких, що . Позначається (від cover – покривати).

Приклад. 1. – покриття множини .

2. – покриття множини .



Означення. Розбиттям непорожньої множини називається покриття, яке містить тільки такі підмножини, які не перерізаються Позначається (від break – розбивати).

=, якщо і

Приклад. 1. – розбиття множини .

2. – розбиття універсуму.

3. – розбиття універсуму.

Розбиття визначається однозначно, і частини розбиття породжують особливий вид відношень. Ці відношення поводять себе так, як відношення "=" між числами або множинами.



Означення. Відношення називається відношенням еквівалентності (позначається спеціальним символом ~ ) на множині , якщо воно рефлексивне, симетричне і транзитивне, тобто:

1) ~;

2) ~~;

3) ~ і ~ ~.

Приклади:

1. Відношення рівності на будь-якій множині.

2. Відношення подібності на множині плоских трикутників.

3. Відношення ‘‘мати ту саму остачу від ділення на 7’’ на множині .

4. Відношення паралельності на множині всіх прямих площини.

Означення. Класом еквівалентності елемента множини називається множина всіх елементів множини , які еквівалентні . Позначається .

~ }.



Приклад. Нехай – фіксоване натуральне число. Визначимо на множині цілих чисел відношення:

.

Для класи еквівалентності мають вид:

=={11, 21, ..., -9, 10976631, ...};

=={12, 22, ..., -8, 10976632, ...};

=={66, 226, -24, ...}.

Має місце



Теорема. Сукупність всіх класів еквівалентності є розбиттям множини . Справедливе і обернене: Нехай – довільне розбиття множини і для будь-яких елементів задане бінарне відношення належать одному й тому ж класу розбиття. Тоді є відношенням еквівалентності.

Означення. Множина всіх класів еквівалентності деякої множини , утворених за відношенням еквівалентності ~, називається фактормножиною множини за даним відношенням еквівалентності. Позначається ~.

Фактормножина ~ визначає розбиття множини на підмножини, які попарно не перерізаються – на класи еквівалентності.


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

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

Відношення нестрогого порядку є узагальненням відношення на множині натуральних чисел , тому можна легко перевірити властивості цього відношення:

1) рефлексивність:

2) антисиметричність: ;

3) транзитивність:

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

Відношення строгого порядку є узагальненням відношення на множині натуральних чисел , тому можна легко перевірити властивості цього відношення:

1) антирефлексивність:

2) асиметричність: ;

3) транзитивність:

Обидва типи відношень називаються відношенням порядку.



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

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

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

Приклади:

1. і – відношення нестрогого порядку для чисел; і – відношення строгого порядку. Обидва відношення цілком впорядковують множини і .

2. На множині підмножин множини відношення нестрогого включення задає нестрогий частковий порядок, а відношення строгого включення задає строгий частковий порядок.

Перевіримо властивості відношення нестрогого включення :

1) рефлексивність: ;

2) антисимметричність: ;



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

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

скачать файл



Смотрите также:
Лекція №1 Тема: Елементи теорії множин і відношень План лекції: Зміст та задачі дискретної математики
321.62kb.
2 Основні поняття теорії множин Поняття множини належить до категорії найзагальніших, основоположних понять математики. Відповісти на питання «Що таке множина?» не так просто, як це здається на перший погляд
950.93kb.
Лекція №8 Тема: Мета та технологія проектування План Цілі проектування реляційної бази даних. Оптимальне число відношень
49.59kb.
Зміст вступ Постановка задачі Математичний опис задачі
168.17kb.
Пропоную вашій увазі серії літературних задач, які можна використати на уроках математики у другому та третьому класах. Задачі об’єднані за математичними ознаками: задачі на знаходження суми та остачі (2 клас)
28.56kb.
Конспект лекції укладач: Ю.Ївженко Київ 2009 р. Зміст План уроку Праця Гідна праця. Якість життя
280.16kb.
Конспект лекцій Черкаси 2004 Зміст тема №1. предмет мікроекономіки
1116.69kb.
Лекція 12. Самоорганізація колективу агентів у часі (самосинхронізація) Постановка задачі самосинхронізації колективу
43.82kb.
Пояснювальна записка Передбачений програмою (3-4 кл.) зміст є органічною частиною цілісного курсу математики в початковій школі
44.77kb.
Доцент Даннік Л. А. Дисципліна «Теорія і методика трудового навчання» Назва теми лекції та анотований зміст: Загальні питання трудової підготовки учнів
294.1kb.
Навчально-методична картка (план) уроку №3(107) Предмет – «Математика» Тема уроку
33.85kb.
Множення чисел 1 і Множення на 1 і задачі на дві і три дії
68.54kb.