Приклади розв’язання типових задач

Задача 1. Нехай . Вказати властивості відношення , заданого на множині .

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

Задача 2. Класифікувати відношення та – особи одного року народження } на множині людей.

Розв’язання. Відношення рефлексивне (адже твердження “ та – особи одного року народження” істинне для будь-якого з множини людей, отже, містить усі діагональні пари), симетричне (якщо , то це означає, що та – особи одного року народження, але тоді та також є особами одного року народження, звідки ), транзитивне (якщо та , тобто та – особи одного року народження й та – особи одного року народження, то й та – особи одного року народження, отже, ). Таким чином, дане відношення є відношенням еквівалентності.

Задача 3. Нехай , та – бінарні відношення на множині . Довести, що: a) ; b) .

Розв’язання.

a) Використовуючи означення доповнення відношення та означення відношення, оберненого до даного, маємо: . Отже, . Покажемо, що . Маємо: . Це і означає, що .

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

Задача 4. Нехай та – часткові порядки на . Довести, що – частковий порядок на .

Розв’язання. Покажемо, що відношення є рефлексивним, антисиметричним та транзитивним. Оскільки та – часткові порядки на , то відношення та є рефлексивними, тобто і відношення рефлексивне. Нехай та . Тоді і , звідки з антисиметричності випливає, що . Отже, відношення – антисиметричне. Доведемо транзитивність. Нехай та . Тоді . З транзитивності відношень та випливає, що та , тобто . Таким чином, є частковим порядком на .

Задача 5. З’ясувати, чи будуть відношення , та , задані на множинах та , відображеннями (або частковими відображеннями).

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

Задача 6. З’ясувати, чи будуть сюр’єктивними відображення , , та , , де та .

Розв’язання. Для кожного елемента з множини обчислимо повний прообраз : , , . Таким чином, Ø для кожного , отже, є сюр’єктивним відображенням (відображенням на ). В той же час для відображення маємо Ø, тому не є сюр’єктивним.

Задача 7. З’ясувати, чи будуть ін ’є ктивними відображення , , та , , де та .

Розв’язання. Відображення є ін’єктивним, оскільки різні елементи з області визначення мають різні образи. В той же час у відображенні різні елементи та мають однаковий образ 2, тому не є ін’єктивним.

Задача 8. З’ясувати, чи будуть бієктивними (взаємно однозначними) відображення , , та , , де , та .

Розв’язання. Відображення є сюр’єктивним, оскільки кожен елемент множини має прообраз; крім того, різні елементи множини мають різні образи, отже, є ін’єктивним. Таким чином, є бієкцією. Відображення не є ін’єктивним, хоча є сюр’єктивним. Отже, не є бієктивним.

A3

1. Навести приклади унарних відношень на множині натуральних чисел та на множині людей .

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

3. Скільки унарних та тернарних відношень можна побудувати на множині , якщо вона містить елементів?

4. На множині побудувати відношення тотожності : .

5. На множині побудувати відношення : “мати спільний дільник, що не дорівнює 1”. Задати це відношення графіком, матрицею та стрілковою діаграмою.

6. Нехай та – відношення на множині , , . Знайти , , .

7. Нехай – множина людей, , є дитиною . Яким буде відношення ?

8. Відношення задане на множині дійсних чисел. Побудувати .

9. Визначити властивості відношень , , якщо:

a) ;

b) .

10. Визначити властивості відношень, побудованих чи наведених у задачах № 4, 5, 6, 7.

11. Вказати властивості відношення, заданого на множині людей : та мають спільного предка.

12. На множині побудувати відношення, яке є

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

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

13. Класифікувати відношення:

a)

b) .

Для відношень еквівалентності побудувати класи еквівалентності.

14. З’ясувати, чи є наведені відношення відношеннями еквівалентності:

a) “вчитись в одній групі” на множині студентів КПІ;

b) “мати таку ж парність, як …” на множині ;

c) “мати стільки ж знаків, скільки …” на множині ;

d) на множині прямих;

e) на множині прямих.

Для відношень еквівалентності побудувати класи еквівалентності.

15. Відношення еквівалентності на множині задано розбиттям на класи Представити це відношення множиною впорядкованих пар, матрицею та графом.

16. На множині різнокольорових кульок різного діаметра побудувати відношення еквівалентності.

17. Нехай – скінченна множина. Які відношення еквівалентності породжують найбільшу та найменшу кількість класів еквівалентності?

18. Класифікувати відношення, , задане на множині . Побудувати матрицю цього відношення та діаграму Хаасе. Вказати мінімальний, максимальний, найбільший та найменший елементи.

19. На булеані множини задане відношення . Побудувати діаграму Хаасе, вказати елементи, які не можна порівняти за цим відношенням. Вказати мінімальний, максимальний, найбільший та найменший елементи.

20. Скільки різних відношень часткового порядку можна побудувати на трьохелементній множині. Побудувати діаграми Хаасе.

21. Чи може один і той же елемент частково впорядкованої множини бути одночасно мінімальним і максимальним?

22. Якщо впорядкована множина має найменший елемент, то він єдиний. Довести.

23. Класифікувати відношення , задане на множині . Побудувати матрицю цього відношення та діаграму Хаасе.

24. З’ясувати тип порядку (частковий, строгий, лінійний):

a) на множині співробітників банку задане відношення “підлеглий – начальник”;

b) на множині офіцерських звань задане відношення “бути молодшим за званням”;

c) на множині деталей задане відношення “бути важчим”.

25. Розташувати у лексикографічному порядку елементи множини:

a) де b) де

26. Бінарне відношення є одночасно симетричним і антисиметричним. Довести, що – транзитивне.

27. Довести, що об’єднання двох рефлексивних відношень є рефлексивним.

28. Нехай – бінарні відношення, задані на множині . Довести:

a)

b)

c) – транзитивне .

29. Нехай Побудувати приклади відношень кожне з яких є:

a) повністю визначене на і не функціональне;

b) не повністю визначене на і не функціональне;

c) не повністю визначене на і функціональне;

d) повністю визначене на і функціональне.

30. Нехай – відношення між елементами множин та В яких випадках можна розглядати як відображення, якщо:

a) – множина студентів, – множина навчальних дисциплін; вивчає ;

b) – множина спортсменів, – множина дійсних чисел; має зріст ;

c) – множина деталей, – їх маса; має масу ?

31. З’ясувати властивості відображення , якщо

a) с)

b) d)

32. Вибрати множини та побудувати на них відображення, яке є:

a) довільним; b) сюр’єктивним, але не ін’єктивним; c) ін’єктивним, але не сюр’єктивним; d) бієктивним; e) тотожним.

33. Чи є рівнопотужними множини:

a) та ; с) та ;

b) та ; d) та ?

34. Множини і – скінченні. Якщо ці множини еквівалентні, то вони містять однакову кількість елементів. Довести.

35. Чи будуть множини і еквівалентними, якщо

a) ; b) ?

36. Чи будуть еквівалентними множини точок на будь-яких двох відрізках і ?

37. Нескінченна підмножина зліченної множини зліченна. Довести.

B3

1. На множині студентів навести приклади повного та порожнього бінарного відношення.

2. На множині побудувати відношення : . Задати його різними способами.

3. Задати відношення координатним способом:

a) ; b) та ).

4. Нехай на множинах та задано відношення і . Побудувати .

5. Нехай на множині людей задані такі відношення є батьком та є донькою . Описати такі відношення: .

6. Відношення задане на множині , вказати його властивості, якщо:

a) ;

b) ;

c) ;

d) ;

e) .

7. З’ясувати, які властивості мають відношення, задані на множині натуральних чисел:

a) та взаємно прості;

b) є дільником ;

c) ;

d) .

8. Навести приклад відношень, кожне з яких є

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

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

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

9. Довести, що відношення , задане на множині , є відношенням еквівалентності.

10. Чи буде відношенням еквівалентності відношення подібності на множині трикутників?

11. Нехай – множина прямих. З’ясувати, чи будуть наступні відношення відношеннями еквівалентності:

a) пряма перетинається з прямою ;

b) пряма лежить в одній площині з прямою ;

c) пряма перетинає ті ж самі площини, що і пряма .

12. Нехай на множині задано відношення . З’ясувати, чи буде відношенням еквівалентності, якщо:

a)

b)

c)

d)

Для кожного відношення еквівалентності побудувати класи еквівалентності..

13. Знайти класи еквівалентності для відношень, заданих на :

a) b) c) .

14. Класифікувати відношення, задані на множині :

a) , ;

b) ділить .

Побудувати матриці відношень та діаграми Хаасе. Вказати мінімальний, максимальний, найбільший та найменший елементи.

15. Нехай . Скільки відношень часткового порядку можна побудувати на цій множині? Вказати їх.

16. З’ясувати, чи будуть наведені відношення відношеннями порядку:

a)

b)

c) ділиться на з остачею .

Вказати тип впорядкованості у випадках, коли це можливо. Побудувати діаграми Хаасе.

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

18. Довести, що перетин двох симетричних відношень є симетричним.

19. Нехай та – іррефлексивні відношення. Чи завжди буде добуток таких відношень іррефлексивним? Навести приклади.

20. Нехай , та – бінарні відношення, задані на множині . Довести:

a) ;

b) ;

c)

21. Чи кожна підмножина множини є графіком певного відображення ?

22. На множинах і задано відношення:

;

;

;

;

.

Які з них: a) всюди визначені; b) функціональні; c) ін’єктивні; d) сюр’єктивні; e) бієктивні (взаємно однозначні)?

23. Чи є відношення

a) ;

b) ;

c) ;

d) ;

e) ;

f) ;

g) .

відображеннями? Вказати їх властивості.

24. Що можна сказати про множини та , коли відомо, що кожне відображення є: а) сюр’єкцією; b) ін’єкцією; c) бієкцією?

25. Навести приклад множини , що еквівалентна множині . Скільки взаємно однозначних відображень існує між та ?

26. Чи є зліченною множина ?

27. Чи будуть множини і еквівалентними, якщо:

a) ; b) ?

28. Довести, що декартів добуток двох зліченних множин є множина зліченна.

29. Чи є зліченною множина ?

С3

1. Множина складається з елементів. Скільки різних бінарних відношень можна побудувати на цій множині? Скільки буде серед них:

a) рефлексивних відношень; b) симетричних відношень?

2. Визначити, чи будуть вказані відношення відношеннями еквівалентності:

a) , ;

b) , ;

c) , ;

d) .

Для відношень еквівалентності задати класи еквівалентності.

3. Чи можна стверджувати, що об’єднання двох відношень еквівалентності теж буде еквівалентністю? Відповідь обґрунтувати.

4. Побудувати відношення часткового порядку на множині трикутників.

5. Якщо – відношення часткового порядку, то теж відношення часткового порядку. Довести.

6. Нехай ділиться на . Вказати мінімальний, максимальний, найменший, найбільший елементи, якщо:

a) ; b) ; c) .

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

8. Нехай на множині задано відношення . Знайти лінійний порядок , для якого . Скільки існує таких лінійних порядків?

9. Нехай і – бінарні відношення, задані на множині . Довести:

а) ; b) .

10. Довести, що – симетричне відношення тоді і тільки тоді, коли .

11. Довести, що – антисиметричне відношення тоді і тільки тоді, коли .

12. Якщо – відношення еквівалентності, то та . Довести.

13. Нехай та – відношення еквівалентності. Довести, що – відношення еквівалентності тоді і тільки тоді, коли .

14. Нехай . Скільки можна побудувати різних відображень ?

15. Нехай . Скільки можна побудувати різних бієкцій ?

16. На множинах та задано відношення . За яких умов відношення є: a) всюди визначеним; b) функціональним; c) ін’єктивним; d) сюр’єктивним; e) бієктивним?