Juk_Ilyenko_Moklyachuk_Orlovskiy_DM_praktikum

№ 3.3. Нехай - множина тенiсистiв, якi беруть участь у турнiрi, де кожен учасник має зiграти сет iз трьох партiй. Нехай для вiдношення

означає, що виграв у в сетi.

1)З’ясувати, якi з властивостей виконанi для даного вiдношення

2)З’ясувати, якими є вiдношення , −1

3)Побудувати на скiнченнiй множинi вiдношення, яке має такий самий набiр властивостей, як i . Зобразити його графом та аналiтично.

4)Побудувати на нескiнченнiй множинi вiдношення, яке має протилежний набiр властивостей, нiж має .

Розв’язок. 1) Перевiримо, якi з властивостей виконуються для за-

даного вiдношення.

a)Вiдношення не є рефлексивним, адже тенiсист не може виграти сам

усебе;

b)Вiдношення є iррефлексивним, адже кожен тенiсист не виграв сам

усебе;

c)Вiдношення не є симетричним, адже якщо тенiсист виграв у тенiсиста , то тенiсист не виграв у тенiсиста ;

d)Вiдношення є антисиместричним, адже коли тенiсист виграв у тенiсиста , то обов’язково тенiсист не виграв у тенiсиста ;

e)Вiдношення не є транзитивним, адже можлива ситуацiя, коли виграв у , виграв у , i в той же час виграв у ;

f)Вiдношення є зв’язним, адже кожна пара тенiсистiв має зiграти мiж собою та визначити переможця.

50

2) З’ясуємо, як будуть виглядати вiдношення та −1.

За визначенням композицiї, означає, що знайдеться такий , що та . Тобто у вiдношення будуть вступати такi пари тенiсистiв та , коли виграв у , а виграв у .

Аналогiчним чином, у вiдношення −1 будуть вступати тенiсисти

та , для яких знайдеться тенiсист , котрий програв у та у . Це означає, що графiк вiдношення −1 будуть складати пари тенiсистiв, для яких знайдеться хоча б один тенiсист, який програв у них обох.

3) Побудуємо на скiнченнiй множинi вiдношення з тим самим набором властивостей, якi є у заданого спiввiдношення .

Нехай = ({ , , }, {( , ), ( , ), ( , )}). Зобразимо дане вiдношення у виглядi графа.

Рис. 3.1.

a)Це вiдношення не рефлексивне, адже ;

b)Це вiдношення iррефлексивне, адже , та ;

c)Вiдношення не є симетричним, адже та ;

d)Вiдношення є антисиметричним, адже та , та , та

;

51

e)Вiдношення не транзитивне, адже та , але ;

f)Вiдношення є зв’язним, так як кожна пара рiзних елементiв множини

{ , , } вступає у вiдношення тим чи iншим чином.

4)Побудуємо на нескiнченнiй множинi рефлексивне, не iррефлексивне, симетричне, не антисиметричне, транзитивне та не зв’язне вiдношення.

Побудуємо вiдношення на множинi = (0, +∞), де означає, що та мають однакову дробову частину.

a)Вiдношення рефлексивне, адже будь-яке число має однакову дробову частину саме з собою

b)Вiдношення не iррефлексивне, адже iснує число (наприклад, 1.32432), яке має однакову дробову частину саме з собою

c)Вiдношення симетричне, адже якщо та мають однакову дробову частину, то та теж мають однакову дробову частину.

d)Вiдношення не антисиметричне, адже iснують числа (наприклад, 1.65 та 5.65), якi не спiвпадають, проте 1.65 5.65 та 5.65 1.65;

e)Вiдношення є транзитивним, адже коли має однакову дробову частину з та має однакову дробову частину з , то та теж мають однакову дробову частину.

f)Вiдношення не є зв’язним, адже iснують елементи (наприклад, 3.1 та 1.6, 3.1 ̸= 1.6) такi, що 3.1 1.6 та 1.6 3.1

Побудоване вiдношення є рефлексивним, симетричним та транзитивним, отже, воно є вiдношенням еквiвалентностi.

52

№3.4. Для заданого вiдношення = ({1, 2, 3, 4, 5}, {(1, 2), (1, 3), (5, 4)})

1.Зобразити графом;

2.Добудувати до вiдношення еквiвалентностi;

3.Добудувати до вiдношення часткового порядку, вказати мiнiмальнi та максимальнi елементи, а також пари елементiв, що не порiвнюються;

4.Добудувати до вiдношення лiнiйного порядку, вказати мiнiмальний та максимальний елементи;

5.Добудувати до вiдношення строгого порядку;

6.Добудувати до вiдношення строгого лiнiйного порядку.

Розв’язок. 1) Зобразимо вiдношення графом.

2

1

3

Рис. 3.2.

2) Добудуємо до вiдношення еквiвалентностi, додаючи мiнiмальну кiлькiсть ребер. Позначимо графiк отриманого вiдношення 1. Тодi 1

53

буде мати вигляд:

2 = {(1, 2), (1, 3), (5, 4), (1, 1), (2, 2), (3, 3),

(4, 4), (5, 5), (2, 1), (3, 1), (4, 5), (2, 3), (3, 2), }.

Зобразимо граф даного вiдношення.

2

1

3

Рис. 3.3.

3) Добудуємо вiдношення до вiдношення часткового порядку. Позначимо графiк отриманого вiдношення 2. Тодi даний графiк буде мiстити наступнi елементи:

2 = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (1, 3), (5, 4)}.

Побудуємо граф отриманого вiдношення.

2

1

3

54

Рис. 3.4.

Мiнiмальними елементами в отриманому вiдношення є 1 та 5, а максимальними - 2, 3 та 4. Пари елементiв, що не порiвнюються - {1, 4},

{1, 5}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {2, 3}.

4) Добудуємо до вiдношення лiнiйного порядку. Позначимо графiк отриманого вiдношення 3. Тодi будемо мати, що

3 = 2 {(2, 3), (4, 1), (4, 2), (4, 3), (5, 1), (5, 2), (5, 3)}.

Побудуємо граф отриманого вiдношення.

2

1

3

Рис. 3.5.

Найбiльшим елементом в даному випадку є 3, а найменшим - 5.

5)Вiдношення уже є вiдношенням строгого порядку, так що в даному випадку його не потрiбно добудовувати.

6)Добудуємо до вiдношення строгого лiнiйного порядку. Позначимо графiк отриманого вiдношення 4. Тодi

4 = 3 =

55

57

№3.6. Нехай - певна множина, - вiдношення на цiй множинi.

1)З’ясувати, якi з властивостей виконанi для даного вiдношення

2)З’ясувати, якими є вiдношення , −1

3)Побудувати на скiнченнiй множинi вiдношення, яке має такий самий набiр властивостей, як i . Зобразити його графом та аналiтично.

4)Побудувати на нескiнченнiй множинi вiдношення, яке має протилежний набiр властивостей, нiж має .

1.= {Множина студенiв ВУЗу}, та вчаться на одному курсi;

2.= {Множина всiх кiл на площинi}, та дотикаються;

3.= {Жителi України за даними перепису населення},

та подружжя;

4.= {Прямi в просторi}, та перетинаються;

5.= {Натуральнi числа}, та мають однакову остачу вiд дiлення на 3;

6.= {Дiйснi числа}, 2 + 2 = 1;

7.= {Читачi бiблiотеки}, та прочитали одну й ту саму книгу;

8.= {Вектори на площинi}, та мають однакову довжину;

9.= {Жителi України за даними перепису населення},

батько ;

58

10.= {Жителi України за даними перепису населення},

онук .

№3.7. Для заданого вiдношення

a)Зобразити графом;

b)Добудувати до вiдношення еквiвалентностi;

c)Добудувати до вiдношення часткового порядку, вказати мiнiмальнi та максимальнi елементи, а також пари елементiв, що не порiвнюються;

d)Добудувати до вiдношення лiнiйного порядку, вказати мiнiмальний та максимальний елементи;

e)Добудувати до вiдношення строгого порядку;

f)Добудувати до вiдношення строгого лiнiйного порядку.

1.= ({1, 2, 3, 4, 5}, {(1, 2), (3, 2), (2, 4)});

2.= ({1, 2, 3, 4, 5}, {(2, 1), (5, 1), (4, 2)});

3.= ({1, 2, 3, 4, 5}, {(1, 2), (3, 4), (4, 5)});

4.= ({1, 2, 3, 4, 5}, {(3, 1), (2, 5), (5, 4)});

5.= ({1, 2, 3, 4, 5}, {(1, 5), (5, 4), (4, 3)});

6.= ({1, 2, 3, 4, 5}, {(2, 3), (3, 5), (5, 1)});

7.= ({1, 2, 3, 4, 5}, {(1, 2), (4, 3), (4, 5)});

8.= ({1, 2, 3, 4, 5}, {(3, 5), (4, 2), (1, 2)});

59