Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



4. Бінарні відношення Рекомендована література: [4, 8, 9, 10, 11, 15, 16, 17]. Властивості бінарних відношень

Скачати 80.89 Kb.

4. Бінарні відношення Рекомендована література: [4, 8, 9, 10, 11, 15, 16, 17]. Властивості бінарних відношень




Скачати 80.89 Kb.
Дата конвертації02.05.2017
Розмір80.89 Kb.

4. Бінарні відношення


Рекомендована література: [4, 8, 9, 10, 11, 15, 16, 17].

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


4.1. Указати, які з властивостей – рефлексивність, симетричність, антисиметричність, транзитивність – має відношення R на множині A, де:

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

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

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

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

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

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

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

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

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

4.2. Побудувати відношення:

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

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

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

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

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

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

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

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

4.3. Нехай R1, R2 – довільні симетричні відношення на тій самій множині. З'ясувати істинність твердження:

  1. R1R2 – симетричне відношення;
    І́стина - одна з центральних категорій гносеології, правильне відображення об'єктивної дійсності у свідомості людини, її уявленнях, поняттях, судженнях, умовиводах, теоріях об'єктивної дійсності.


  2. R1R2=R2R1.

4.4. Навести приклад антирефлексивних відношень R1, R2, таких, що R1R2 не є антирефлексивним.

4.2. Транзитивність відношень та їх замикання


4.5. Побудувати транзитивне і транзитивно-рефлексивне замикання відношення R на множині A={1, 2, 3}, де

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

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

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

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

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

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

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

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

  9. R={(1,1), (1,2), (3,1)};

4.6. Чи істинно, що композиція довільних транзитивних відношень на тій самій множині транзитивна?

4.7. Навести приклад транзитивного відношення R, для якого:



  1. RR=R;

  2. RRR.

4.8. Нехай відношення R задано на множині A з n елементів. Довести, що:

  1. R*=Ri;

  2. R =Ri;

4.9. Навести приклад n, множини A з n елементів і відношення R на A такі, що:

  1. R*Ri;

  2. R =Ri;

4.3. Властивості відношення еквівалентності


4.10. Визначити, чі є еквівалентністю відношення R на множині A. Для відношення, що не є еквівалентністю, указати, які з властивостей – рефлексивність, симетричність, транзитивність – порушуються:

  1. A={1, 2, 3}, R={(1,1), (2,2), (3,3), (1,2), (2,1)};

  2. A={1, 2, 3}, R={(1,1), (2,2), (3,3), (1,2), (2,3), (1,3)};

  3. A={1, 2, 3}, R={(1,1), (2,2), (3,3), (1,3), (3,1)};

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

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

  6. A={1, 2, 3}, R={(1,1), (2,2), (3,3), (1,2)};

  7. A={1, 2, 3}, R={(1,1), (2,2), (1,2), (2,1)};

  8. A={1, 2, 3}, R={(1,1), (3,3), (1,2), (2,3)};

  9. A={1, 2, 3}, R={(1,1), (2,2), (3,3), (1,2), (2,1), (2,3)};

4.11. Довести, що якщо R є транзитивним і симетричним відношенням на множині A і RR=A, то R є еквівалентністю на A.

4.12. Нехай R – відношення на A. Довести, що R є еквівалентністю тоді й тільки тоді, коли (RR-1)iA=R.

4.13. Нехай R1, R2еквівалентності на A.

Логічна еквівалентність (еквіваленція) - двомісна логічна операція, що має значення «істина» тоді і тільки тоді, коли обидва операнди мають однакове значення. В інших випадках еквіваленція буде хибною.
Довести:

  1. R1R1=AAR1=AA;

  2. R1R2=AAR2R1=AA;

4.14. Довести, що перетин двох еквівалентностей є еквівалентністю.

4.15. Довести, що об'єднання R1R2 двох еквівалентностей R1 і R2 є еквівалентністю тоді й тільки тоді, коли R1R2=R1R2.

4.16. Довести, що композиція R1R2 двох еквівалентностей R1 і R2 є еквівалентністю тоді й тільки тоді, коли R1R2=R2R1.

4.17. Нехай R1, R2 – еквівалентності. Довести, що якщо R1R2=R2R1, то R1R2 є найменшим відношенням еквівалентності, яке включає в себе R1R2.


4.4. Відношення часткового порядку

4.4.1. Загальні властивості


4.18. Указати мінімальні, максимальні, найменші, найбільші елементи у частковому упорядкуванні R множини A={1, 2, 3, 4, 5}, а також множини верхніх граней і нижніх граней підмножини B. У завданні R вважається, що з кожними двома парами вигляду (x,y), (y,z) воно містить також і пару (x,z), яка не записується:

  1. R=iA{(1,2), (1,3), (1,4), (5,2)}, B={1, 5};
    Па́ра (рос. пар; англ. vapour, steam; нім. Dampf m) - газоподібний стан речовини в умовах, коли газова фаза може перебувати в рівновазі з рідкою чи твердою фазами тієї ж речовини. При низькому тиску і високій температурі властивості пари наближаються до властивостей ідеального газу.


  2. R=iA{(1,2), (1,3), (1,4), (5,2)}, B={2, 3};

  3. R=iA{(1,2), (1,3), (4,1), (5,1)}, B={1};

  4. R=iA{(1,2), (1,3), (4,1), (5,1)}, B={2, 3};

  5. R=iA{(1,2), (1,3), (1,4), (5,2)}, B={4, 5};

  6. R=iA{(1,3), (2,3), (2,4), (3,5), (4,5)}, B={3, 4};

  7. R=iA{(1,3), (2,3), (2,4), (3,5), (4,5)}, B={3};

  8. R=iA{(1,3), (2,3), (2,4), (3,5), (4,5)}, B={1, 2};

  9. R=iA{(1,3), (2,3), (2,4), (3,5), (4,5)}, B={5};

4.19. Нехай відношення <,  на множині N означено як звичні упорядкування. Довести:

  1. <<  <;

  2. < = <;

  3. <<  <;

  4. < = <;

  5. ><  N2;

  6. >  N2;

  7. <> = N2;

  8. <  N2.

4.20. Довести, що iA є частковим порядком на множині A.
Частково впорядкованою множиною ( P , ⩽ ) , називається множина P із заданим на ній рефлексивним, антисиметричним та транзитивним бінарним відношенням ⩽ (називається - відношення нестрогого порядку).

4.21. Нехай на множині N={0, 1, 2, …} означено ab a ділить b. Вважаємо, що 0 ділить 0. Довести, що  є частковим порядком. Які елементи є мінімальними та максимальними у цьому упорядкуванні на множині



  1. N;

  2. N\{0};

  3. N\{0, 1}.

4.22. Нехай R1 і R2 – часткові порядки на множині A. Довести, що R1R2 є частковим порядком тоді й тільки тоді, коли R1=R2.

4.23. Нехай A – скінченна частково упорядкована множина. Довести:



  1. A містить мінімальний та максимальний елементи.

  2. aA (B)(ab і b – максимальний елемент) і (c)(ca і c – мінімальний елемент).

  3. її упорядкування можна доповнити до лінійного.

4.24. Нехай A – частково упорядкована множина, в якій кожний ланцюг має не більше m елементів, а кожна підмножина попарно непорівнюваних елементів містить не більше, ніж n елементів. Довести, що A складається не більше, ніж з mn елементів.

4.25. Нехай A і B є частковими порядками на множинах A і B відповідно. Прямим добутком частково упорядкованих множин A і B називається множина AB з відношенням :

(a1, b1)(a2, b2)  a1 A a2 і b1 B b2.

Довести, що  є частковим порядком.

4.26. Нехай A і A1 – частково упорядковані множини, f:AA1 – монотонна взаємно однозначна функція з A в A1. Довести, що f-1 може бути немонотонною.

4.4.2. Лінійно та цілком упорядковані множини


4.27. Описати всі лінійно упорядковані множини, такі, що при будь-яких a і b, a<b, існує скінченна множина таких c, що acb.
Скінченна множина - це множина, кількість елементів якої є скінченна, тобто існує натуральне число k, що є числом елементів цієї множини. В протилежному випадку множина є нескінченною. Визначення 2. Множина, що не має рівнопотужної з нею власної підмножини, а також порожня множина, називається скінченною

4.28. Нехай A – лінійно упорядкована множина не менш ніж з двох елементів, B=AA2…An… Означимо при будь-яких x1,… , xn, y1,…, ym з A, де n, m  1,

(x1,… , xn)(y1,…, ym) 

 (nm і x1=y1,… , xn=yn)(x1=y1,… , xi-1=yi-1, xi<yi при деякому in, im).

Довести, що (B, ) є


  1. лінійно упорядкованою;

  2. цілком упорядкованою.

4.29. Знайти всі цілком упорядковані множини A з упорядкуванням R, такі, що R-1 також є повним упорялкуванням A.

4.30. Довести:



  1. кожна скінченна лінійно упорякована множина є цілком упорядкованою;

  2. множина N з порядком 0<1<2<… є цілком упорядкованою;

  3. множина N з порядком 0<2<4<…<1<3<5<… є цілком упорядкованою;

  4. множина N з порядком …<3<2<1<0 не є цілком упорядкованою;

  5. множина Z з природним порядком …<-2<-1<0<1<… не є цілком упорядкованою;

  6. множина Q рацональних чисел з природним порядком  не є цілком упорядкованою;

  7. множина R дійсних чисел з порядком  не є цілком упорядкованою;

  8. множина чисел вигляду 1-1/n, де nдодатнє ціле, з порядком  є цілком упорядкованою;

  9. множина чисел вигляду 1/n, де n – додатнє ціле, з порядком  не є цілком упорядкованою;

  10. множина раціональних чисел з відрізка [0;
    Раціональність (від лат. Ratio - розум) - термін у найширшому сенсі означає розумність, свідомість, протилежність ірраціональності. У більш вузкому значенні - характеристика знання з точки зору його відповідності деяким принципам мислення.
    1] з природним порядком  не є цілком упорядкованою;

4.31. Чи можна в цілком упорядкованій множині виділити нескінченно спадний ланцюг x1>x2>x3>…?

4.32. Нехай A – цілком упорядкована множина. Довести, що не існує такої монотонної взаємно однозначної відповідності f:AA, що f(a)<a при деякому aA.

4.33. Довести, що лінійно упорядкована множина (A, R) є скінченною тоді й тільки тоді, коли вона цілком упорядкована відносно R і відносно R-1.

4.34. Нехай A – цілком упорядкована множина, BA і при будь-якому xA множина B задовольняє умову: якщо {yA | y<x}B, то xB. Довести, що B=A (принцип трансфінітної індукції).

Трансфінітна індукція - метод доведення, що узагальнює математичну індукцію у випадку незліченного числа значень параметра.


4.4.3. Решітки


4.35. Указати, чи є часткове упорядкування R множини A решіткою. Якщо R не є решіткою, то указати всі пари елементів, які не мають точної нижньої або точної верхньої грані. У завданні R вважається, що з кожними двома парами вигляду (x,y), (y,z) воно містить також і пару (x,z), яка не записується:

  1. A={1, 2, 3, 4, 5}, R=iA{(1,2), (1,3), (1,4), (2,5), (3,5), (4,5)};

  2. A={1, 2, 3, 4, 5}, R=iA{(1,2), (1,3), (2,4), (3,4), (4,5)};

  3. A={1, 2, 3, 4, 5}, R=iA{(1,2), (2,3), (2,4), (3,5), (4,5)};

  4. A={1, 2, 3, 4, 5, 6}R=iA{(1,2), (1,3), (1,4), (1,5), (2,6), (3,6), (4,6), (5,6)};

  5. A={1, 2, 3, 4, 5, 6}, R=iA{(1,2), (1,3), (3,4), (3,5), (4,6), (5,6)};

  6. A={1, 2, 3, 4, 5, 6}, R=iA{(1,2), (2,3), (2,4), (3,5), (4,5), (5,6)};

  7. A={1, 2, 3, 4, 5, 6}, R=iA{(1,2), (2,3), (2,4), (2,5), (3,6), (4,6), (5,6)};

  8. A={1, 2, 3, 4, 5}, R=iA{(1,3), (2,3), (2,4), (3,5), (4,5)};

  9. A={1, 2, 3, 4, 5}, R=iA{(1,2), (1,3), (2,4), (3,4), (3,5)};

  10. A={1, 2, 3, 4, 5}, R=iA{(1,3), (2,3), (3,4), (3,5)};

  11. A={1, 2, 3, 4, 5}, R=iA{(1,2), (1,3), (2,4), (3,4), (2,5), (3,5)};

  12. A={1, 2, 3, 4, 5, 6}, R=iA{(1,2), (1,3), (2,4), (2,5), (3,4), (3,5), (4,6), (5,6)};

  13. A={1, 2, 3, 4, 5, 6}, R=iA{(1,2), (1,3), (3,4), (3,5), (4,6), (5,6)};

  14. A={1, 2, 3, 4, 5}, R=iA{(1,3), (1,4), (2,3), (2,4), (3,5), (4,5)};

4.36. Довести:

  1. будь-яка лінійно упорядкована множина є решіткою;

  2. множина всіх підмножин будь-якої множини, упорядкована відношенням включення, є решіткою;

  3. множина всіх відношень еквівалентності на будь-якій множині є решіткою;

  4. у решітці будь-який максимальний елемент є найбільшим;

  5. у решітці будь-який мінімальний елемент є найменшим;

  6. у будь-якій скінченній решітці є найбільший і найиенший елемент.

4.37. Навести приклад решітки:

  1. без найбільшого, але з найменшим елементом;
    Решітки (біл. вёска Рашаткі) - село в складі Молодечненського району Мінської області, Білорусь. Село підпорядковане М'ясотській сільській раді, розташоване в західній частині області.
    Елеме́нт (лат. elementum - стихія, первинна речовина) - нерозкладний (у даній системі) компонент складних тіл, матеріальних систем, теоретичних побудов; будь-який об'єкт, пов'язаний певними відношеннями з іншими об'єктами в єдиний комплекс.


  2. без найменшого, але з найбільшим елементом;

  3. без найбільшого і без найменшого елементів.

4.38. Нехай d позначає відношення "ділить" на множині натуральних чисел. Вважаємо, що 0 d 0.

  1. Довести, що (N, d) є решіткою.

  2. Довести, що (N, d) є повною решіткою.

  3. Чи є решіткою (N\{0}, d)?

  4. Чи є повною решіткою (N\{0}, d)?

  5. Чи є решіткою (N\{0, 1}, d)?

4.39. Нехай  – "природне" упорядкування множини Q[0,1] раціональних чисел з відрізка [0,1]. Указати, чи правильно, що повною решіткою є:

  1. (Q[0,1], );

  2. ({1/n | n1}; );

  3. ({1-1/n | n1}; ).

Відповідь обгрунтувати.

4.40. Нехай A={a, b}, A* – множина всіх послідовностей з a і b, тобто слів у алфавіті A.

Абе́тка (А́збука, Алфаві́т) (грец. Αλφάβητο, лат. Abecedarium) - розташована в певному порядку сукупність літер, що застосовуються для запису певної мови.
Чи є повною решіткою:



  1. лексикографічне упорядкування множини A*?

  2. відношення "є підсловом" s на A*, задане як (w1 s w2)  (w2=v1w1v2, де v1, v2A*)?


Скачати 80.89 Kb.

  • 4.2. Транзитивність відношень та їх замикання
  • 4.3. Властивості відношення еквівалентності
  • 4.4. Відношення часткового порядку
  • 4.4.2. Лінійно та цілком упорядковані множини
  • 4.4.3. Решітки