1. теорія множин icon

1. теорія множин




Назва1. теорія множин
Сторінка4/6
Дата07.06.2012
Розмір0.7 Mb.
ТипДокументи
1   2   3   4   5   6

Вправи:

  1. , а , , ,   відношення на :

;

;

;

.

Побудувати матриці заданих відношень і з'ясувати, яке з них:

а) симетричне?

б) рефлексивне?

в) транзитивне?

г) антисиметричне?

  1. . Опишіть відношення на :

а) рефлексивне, але не симетричне, не транзитивне;

б) симетричне, але не рефлексивне, не транзитивне;

в) транзитивне, але не симетричне, не рефлексивне;

г) рефлексивне і симетричне, але не транзитивне;

д) симетричне і транзитивне, але не рефлексивне.

3. Якими властивостями характеризуються наступні відношення на множині :

а) ;

б) ;

в) .

  1. Якими властивостями характеризуються зазначені нижче відношення. Побудувати матриці відношень:

а) відношення, задані на множині елементів структури, зображеної на рис. 2.8:

  “бути безпосередньо зв'язаним з...…”;

 “бути начальником”;

  “бути безпосереднім начальником”.

б) відношення, задані на множині членів родини, що складається з 5 чоловік: бабуся, тато, мама, син, дочка, які проживають в 4-х кімнатній квартирі. В 1-й кімнаті - бабуся, в 2-й – мама і тато, в 3-й - син, в 4-й - дочка. За умови, що тато старіший від дружини, дочка старіша від брата, а бабуся - мама татка:

  “бути старіше”;

  “бути сином (дочкою)”;

  “мати спільну кімнату”.

в) відношення, задані на множині міст України: Харків, Полтава, Чугуїв, Кременчук, Богодухів, Донецьк, Горлівка, Конотоп, Ахтирка, Херсон, Каховка, Луцьк:

  “знаходитися в одній області”;

  “знаходитися в сусідніх областях (мають спільну межу)”.


    1. Операції над бінарними відношеннями


Тому що відношення на множині задаються підмножинами , то для них визначні ті ж операції, що й над множинами, а саме:

1. Об'єднання: .

2. Перетинання: .

3. Різниця: .

4. Доповнення: , де .

Крім того, необхідно визначити інші, ще не знайомі нам, операції над бінарними відношеннями.

5. Обернене відношення .

Визначення 2.11. Якщо   відношення, то відношення називається оберненим відношенням до даного відношення тоді й тільки тоді, коли .

Наприклад, якщо   “бути старіше”, то   “бути молодше”; якщо   “бути дружиною”, то   “бути чоловіком”.

Нехай або . У такому випадку .

Приклад 2.10. Знайти відношення , обернене даному .

Рішення: .

6. Композиція (або складене відношення):

Визначення 2.12. Нехай   відношення на , а   відношення на . Композицією відношень і називається відношення , певне як

.

Ця множина позначається .

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

.

Приклад 2.11. Нехай , , , і нехай відношення на і на задані у вигляді

;

.

Знайти композицію .

Рішення:

і ; ; і ; ;

і ; ; і ; ;

і ; ; і ; .

і ; ;

Отже, .

Приклад 2.12. Нехай і   бінарні відношення, задані на множині додатних цілих чисел у вигляді і . Знайти композиції і .

Рішення:

, .

7. Транзитивне замикання:

Визначення 2.13. Транзитивним замиканням називається множина, що складається з таких і тільки таких пар елементів з , тобто , для яких в існує ланцюжок з елементів : , між сусідніми елементами якої виконується відношення : , ,…,, тобто

.

Наприклад, для відношення   “бути дочкою” композиція   “бути онукою”,   “бути правнучкою” і т.д. Тоді об'єднання всіх цих відносин є транзитивне замикання   “бути прямим нащадком”.

Якщо відношення транзитивне, то .

Визначення 2.14. Транзитивне замикання на є найменше транзитивне відношення на , що містить як підмножину.

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

1) привласнити ;

2) обчислити , привласнити ;

3) зрівняти і . Якщо , то перейти до кроку 4, якщо , то привласнити і перейти до кроку 2;

4) .

8. Рефлексивне замикання:

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

Якщо транзитивне і рефлексивно, то .

Приклад 2.13. Нехай   відношення на множині дійсних чисел “бути менше”. Знайти рефлексивне замикання відношення .

Рішення:

,

, тому що   транзитивне, тоді

  “бути не менше”.

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

Розглянемо приклади операцій над бінарними відношеннями.

Приклад 2.14. Нехай на множині натуральних непарних чисел визначено відношення   “бути більше”. Задати характеристичною властивістю і списком відношення , обернене відношення , доповнення , композицію , транзитивне замикання і рефлексивне замикання .

Рішення:

  “бути більше”;

.

  “бути менше”;

.

  “бути не більше”;

.

;

, тому що   транзитивне.

  “бути більше або дорівнює”, де   тотожне відношення, ;

.

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

і . Визначити відношення: ; ; ; .

Рішення:



; ; ; ; ;

;

.

Аналогічно знайдемо

= ;

;

.

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




Рис. 2.10

Рішення:

Тут задана множина . Матриці відношень і наведені на рис. 2.11. Елементи відношень і виглядають у такий спосіб:

;

.



1

2

3

4

5

6

7






1

2

3

4

5

6

7

1

0

0

0

0

0

0

0




1

0

0

0

0

0

0

0

2

1

0

0

0

0

0

0




2

1

0

0

0

0

0

0

3

1

0

0

0

0

0

0




3

1

0

0

0

0

0

0

4

1

0

0

0

0

0

0




4

1

0

0

0

0

0

0

5

0

0

1

0

0

0

0




5

1

0

1

0

0

0

0

6

0

0

1

0

0

0

0




6

1

0

1

0

0

0

0

7

0

0

0

1

0

0

0




7

1

0

0

1

0

0

0

Рис. 2.11.

Опишемо властивості отриманих відношень:

відношення   нерефлексивне, антирефлексивне, несиметричне, антисиметричне, нетранзитивне;

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

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

Таблиця 2.3.

Присутні

Відсутні

,



,



,




Додамо до відношення елементи, для яких порушена умова транзитивності: і одержимо відношення . Відношення збігається з відношенням   “бути підлеглим”. Можна переконатися, що .

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

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

1   2   3   4   5   6

Схожі:

1. теорія множин iconФормат опису модуля
Булева логіка, логіка предикатів, теорія множин, теорія відношень, основи комбінаторики, теорія графів, теорія дерев
1. теорія множин iconПротокол №9) Програма вступних фахових випробувань для вступників на навчання для здобуття окр магістра (спеціаліста)факультет прикладної математики та інформатики
Теорія множин. Точна верхня та нижня межі множини. Числові послідовності та підпослідовності. Границя числової послідовності. Часткові...
1. теорія множин iconПротокол №19) Програма вступних фахових випробувань для вступників на навчання для здобуття окр магістра (спеціаліста) на факультет прикладної математики та інформатики
Теорія множин. Точна верхня та нижня межі множини. Числові послідовності та підпослідовності. Границя числової послідовності. Часткові...
1. теорія множин iconПротокол №9) Програма вступних фахових випробувань для вступників на навчання для здобуття окр магістра (спеціаліста) на факультет прикладної математики та інформатики
Теорія множин. Точна верхня та нижня межі множини. Числові послідовності та підпослідовності. Границя числової послідовності. Часткові...
1. теорія множин iconПротокол №19) Програма вступних фахових випробувань для вступників на навчання для здобуття окр магістра (спеціаліста) на факультет прикладної математики та інформатики
Теорія множин. Точна верхня та нижня межі множини. Числові послідовності та підпослідовності. Границя числової послідовності. Часткові...
1. теорія множин iconПротокол №19) Програма вступних фахових випробувань для вступників на навчання для здобуття окр магістра (спеціаліста)факультет прикладної математики та інформатики
Теорія множин. Точна верхня та нижня межі множини. Числові послідовності та підпослідовності. Границя числової послідовності. Часткові...
1. теорія множин iconПротокол №9) Програма вступних фахових випробувань для вступників на навчання для здобуття окр магістра (спеціаліста) на факультет прикладної математики та інформатики
Теорія множин. Точна верхня та нижня межі множини. Числові послідовності та підпослідовності. Границя числової послідовності. Часткові...
1. теорія множин iconПрограма вступних фахових випробувань для вступників на навчання для здобуття окр магістра (спеціаліста)факультет прикладної математики та інформатики Напрям підготовки: інформатика Математичний аналіз
Теорія множин. Точна верхня та нижня межі множини. Числові послідовності та підпослідовності. Границя числової послідовності. Часткові...
1. теорія множин iconПрограма вступних фахових випробувань для вступників на навчання для здобуття окр магістра (спеціаліста) на факультет прикладної математики та інформатики Напрям підготовки: прикладна математика Математичний аналіз
Теорія множин. Точна верхня та нижня межі множини. Числові послідовності та підпослідовності. Границя числової послідовності. Часткові...
1. теорія множин iconПрограма вступних фахових випробувань для вступників на навчання для здобуття окр магістра (спеціаліста) на факультет прикладної математики та інформатики Напрям підготовки: системний аналіз Математичний аналіз
Теорія множин. Точна верхня та нижня межі множини. Числові послідовності та підпослідовності. Границя числової послідовності. Часткові...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи