Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
дискретка_1.DOC
Скачиваний:
4
Добавлен:
01.03.2025
Размер:
6 Мб
Скачать
☆

Відношення порядку

Означення. Бінарне відношення R на множині A називають відношенням порядку, якщо воно антисиметричне ((xiAxj) (xjAxi) xi = xj) і транзитивне ((xiAxj) (xjAxk) (xiAxk).

Якщо ж відношення порядку до того ще й рефлексивне (xiAxi), то воно називається відношенням нестрогого порядку і позначається символом „ ”.

Якщо відношення порядку антирефлексивне ((xiAxj) xixj), то воно називається відношенням строгого порядку ( ).

Приклад. Для відношення нестрогого порядку А = „буде дільником” на множині X = {1, 2, 3, 4} й Y = {1, 2, 3, 4, 6, 7, 12} мають вигляд

AXX = ,

AYY = .

Приклад. Для відношення строгого порядку „>” на множині X = {1, 2, 3, 4, 5} матриця має вигляд

.

Граф цього відношення має вигляд

Якщо A є відношення строгого (нестрогого) порядку, то A -1 теж є відношенням строгого (нестрогого) порядку.

Відношення рівнопотужності

Означення. Множина A рівнопотужна множині B (потужність множини A дорівнює потужності множини B), якщо існує взаємно однозначна відповідність (бієкція) множини A на множину B. Цей факт записують як A ~ B.

Кількість елементів скінченої множині A називають потужністю множини A.

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

  • рефлективності (A ~ A) – відношення, яке виконується між елементом і ним самим;

  • симетричності (A ~ BB ~ A), що випливає з того, що відображення обернене до взаємно однозначного, також є взаємно однозначним;

  • транзитивності (A ~ B і B ~ CA ~ C), що випливає з того, що композиція двох взаємно однозначних відображень також взаємно однозначна.

Властивості скінченних множин

  1. Переріз скінченної кількості скінченних множин є скінченним.

  2. Об’єднання скінченної кількості скінченних множин – скінченне.

  3. Декартів добуток скінченної кількості скінченних множин є скінченним.

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

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

Властивості зчисленних множин

  1. Будь-яка підмножина зчисленної множини – скінченна або зчисленна.

  2. Об’єднання скінченної кількості зчисленних множин є зчисленним.

  3. Об’єднання зчисленної кількості скінченних множин є зчисленним.

  4. Об’єднання зчисленної кількості зчисленних множин є зчисленним.

Теорема Кантора. Множина всіх дійсних чисел відрізка [0, 1] не є зчисленною.

Всі числа з відрізка [0, 1] не можуть бути пронумеровані, оскільки множина всіх дійсних чисел відрізка [0, 1] є незчисленною. Її потужність називається континуумом.

Будь-який відрізок дійсної осі має потужність континуум.

Множина правильних дробів має потужність континуум.

Множина, утворена внаслідок вилучення з нескінченної множини елементів зчисленної – рівнопотужна початковій.

Задачі до теми „Відношення і функції”

Схема дослідження бінарних відношень:

а) з’ясувати, до якого типу належить відношення R (відношення еквівалентності, порядку, функціональне відношення);

б) якщо R – відношення еквівалентності, то з’ясувати, які елементи входять у класи еквівалентності;

в) якщо R – відношення порядку, то доцільно з’ясувати якого порядку: строгого, нестрогого чи лінійного;

г) Якщо R (RAB) – функціональне відношення, то з’ясувати, чи є воно відображенням;

д) якщо R – відображення, то яке воно: сюр’єктивне, ін’єктивне чи бієктивне;

е) доцільно записати обернене відношення R–1 і дослідити його за наведеною вище схемою.

Приклад 1. Задати матричним способом та за допомогою діаграми Хассе бінарне відношення на множинах A = {1, 2, 3, 4, 5, 6, 7, 8} і B = {2, 9, 11, 17, 18, 19, 20}:

1) R = {(a, b) | aA, bB; a – дільник b};

2) R = {(a, b) | aA, bB; a – взаємно просте із b};

3) R = {(a, b) | aA, bB; ab};

4) R = {(a, b) | aA, bB; ab};

5) R = {(a, b) | aA, bB; a – b  0};

6) R = {(a, b) | aA, bB; a3b2};

7) R = {(a, b) | aA, bB; a2b}.

Розв’язування 1). Зобразимо дане бінарне відношення матрицею

2

9

11

17

18

19

20

1

1

1

1

1

1

1

1

2

1

0

0

0

1

0

1

3

0

1

0

0

1

0

0

4

0

0

0

0

0

0

1

5

0

0

0

0

0

0

0

6

0

0

0

0

1

0

0

7

0

0

0

0

0

0

0

8

0

0

0

0

0

0

0

За допомогою діаграми Хассе точками зобразимо елементи множини A B, потім проведемо стрілки від a до b, якщо aRb. Коли ж eRc, то проведемо „петлю” від e до c:

1

2

3

4

5

6

7

8

9

20

11

17

18

19

Приклад 2. Скільки бінарних відношень існує на множині з n елементів? (Відповідь: ).

Приклад 3. Визначити, які з наведених відношень на множині натуральних чисел N рефлексивні, симетричні, анстисиметричні, транзитивні:

1) m + n – парне; 2) m + n  17; 3) m + n – непарне;

4) – степінь двійки; 5) – нескоротний дріб; 6) mn – непарне.

Приклад 4. Доведіть, що

1) якщо R1R2, то ;

2) ( )–1 = ;

3) (R2R1)–1 =  .

Розв’язування задачі 4, 3). Нехай (a, b)  (R2R1)–1, тоді (b, a)  R2R1. А це означає, що при деякому c: (b, c)  R2, (c, a)  R1. Тоді (a, c)  (R1)–1, (c, b)  . Звідки (a, b)   , Отже, (R2R1)–1   .

Проведемо доведення у зворотному порядку. Нехай (a, b)   . Тоді при деякому c: (a, c)  (R1)–1, (c, b)  , а це означає, що (c, a)  R1 і (b, c)  R2. Звідси (b, a)  R2R1. Тоді (a, b)  (R2R1)–1. Отже,   (R2R1)–1. Розглянуту властивість доведено.

Приклад 5. Нехай R1, R2 – рефлексивні та симетричні відношення. Показати, що такі умови еквівалентні:

1) R1R2 – симетричне;

2) R1R2 = R2R1;

3) R1R2 = R1 R2.

Приклад 6. На множині A = {1, 2, ..., 10} визначено відношення: елемент a перебуває у відношенні R з елементом b, якщо a і b мають однакову кількість натуральних дільників. Покажіть, що R – відношення еквівалентності, та випишіть усі класи еквівалентності за відношенням R.

Приклад 7. Розгляньте відношення і з’ясуйте, чи це відношення: а) порядку; б) строгого порядку; в) нестрогого порядку:

1) R = {(1, 2), (2, 2), (2, 3), (1, 3), (4, 3)};

2) R = {(1, 2), (2, 3), (1, 3), (4, 3), (1, 4), (4, 2)};

3) R = {(a, b) | aN, bN; b a}.

Розв’язування задачі 7, 3). Дане відношення рефлексивне, оскільки кожне натуральне число ділиться само на себе. Це відношення – антисиметричне. Справді, якщо (a, b)  R, то a b, якщо (b, a)  R, то b a, а це можливо лише тоді, коли a = b.

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

Отже, R – відношення нестрогого порядку, причому 2  4, 3  3, оскільки (2, 4)  R, (3, 3)  R (але (4, 6)  R і (6, 4)  R).

Приклад 8. Довести, що об’єднання (перетин) двох функцій f1, f2 з A в B є функцією з A в B тоді і тільки тоді, коли f1 = f2.

Приклад 9. Довести, що для кожної функції f

1) f(A B) = f(A) f(B);

2) f(A B)  f(A) f(B);

3) f –1(A B) = f –1(A) f –1(B);

4) f –1(A B) = f –1(A) f –1(B).

Приклад 10. Скільки існує сюр’єктивних відображень з триелементої множини в двоелементну?

Приклад 11. Нехай f, g, h: RR відображення множини дійсних чисел в себе: f(x) = x3 – 4x, g(x) = (x2 + 1)–1, h(x) =x4. Знайти fgh, fhg, hgf, ff, g g, h h, gh, hg.