Введение в теорию множеств и комбинаторику


Практическая работа  № 6. Бинарные отношения


Вопросы к работе

1. Что такое “бинарное отношение на множестве”?

2. Как можно записать бинарное отношение?

3. Какое отношение называют рефлексивным?

4. Какое отношение не является рефлексивным?

5. Какое отношение называют симметричным?

6. Какое отношение не является симметричным?

7. Какое отношение называют транзитивным?

8. Какое отношение не является транзитивным?

9. Что такое «эквивалентность на множестве»?

10.Какое отношение называют порядком?

11.Какие вы знаете еще специальные типы отношений?


Образцы решения заданий


Пример 1. Дано множество A = {1; 2; 3; 4; 5; 6}  N. На нем задано бинарное отношение  «больше», т. е. (xy  <=> x > у. Построить граф и график этого отношения. Какими свойствами обладает это отношение? 


Решение. 1) Граф указанного отношения:



2) строим график этого отношения:



  3) Рефлексивность. Если бы это отношение было рефлексивным, то x > x для  А. Например, было бы верно 2 > 2 (ложь ). Значит отношение «>» на А не является рефлексивным.

Симметричность. Если бы это отношение было симметричным на множестве А, то x > у => у > х. Например, 3 > 2 => 2 > 3(ложь). Значит, отношение « > » на А не является симметричным.

Транзитивность. Если бы это отношение было транзитивным на множестве А, то x > уу > z => x > z. Это утверждение истинно для любых натуральных чисел, т. е. и чисел из А. Значит, отношение « > » на А является транзитивным.

 Асимметричность: Ни для каких чисел A не может быть  одновременно истинным , т. е. отношение «>» на A асимметрично. Отношение « > » на множестве A является отношением строгого порядка, т. к. оно асимметрично и транзитивно.

отношение «>» на множестве A является связным. Т. к. отношение «>» на множестве А связное и является отношением строгого порядка, то оно есть отношение строгого линейного порядка.

Пример 2. На множестве людей Земли введено бинарное отношение «быть родственником по крови». Будет ли это отношение отношением эквивалентности? 

Решение. Обозначим через A множество людей Земли, а заданное отношение буквой . Тогда xу <=> человек x является родственником человека у. Что бы отношение  было отношением эквивалентности, оно должно быть рефлексивным, симметричным, транзитивным.

Рефлексивность. Если бы  было рефлексивным, то было бы верно:   xx, т. е. любой человек Земли является родственником самому себе (истина), т. е. отношение  на A рефлексивно.

Симметричность. Если бы  было симметрично. (x=> yx), т. е. если бы человек x был родственником человека у, то у был бы родственником человека x (истина). Значит, отношение  на A симметрично.

Транзитивность. Если бы  было транзитивно на A, то если бы человек x был бы родственником человека у, а у был родственником человека z, то x был бы родственником z. Но это не обязательно. Например, человек x родственник для y по матери, а у – родственник для z по отцу. Тогда x и у могут не быть родственниками  по крови. Значит, отношение  на А не является транзитивным.

Следовательно, отношение «быть родственником по крови» на множестве людей Земли не является отношением эквивалентности. 

Пример 3. Построить граф отношения «легче, чем» на множестве = {кролик, заяц, собака, поросёнок}, если известно, что заяц тяжелее собаки, кролик легче поросёнка, а собака тяжелее поросёнка. Кто из животных самый легкий, кто – самый тяжелый. 

Решение. Строим граф указанного отношения:

Итог: кролик – самый легкий, заяц – самый тяжелый.


Упражнения

1. Найдите область определения рr1 и область значений рr2 каждого из следующих отношений, заданных на множестве

А = {1; 2; 3; ...,10}   N, и укажите, какими свойствами оно обладает:

1) а<=> а -  b = 8;

2) а<=> b  =  а2;

3) а<=> аb = 12;

4) а<=> b  >  а2.

2. На множестве А  = {3; 5; 7; 9; 11}  N задано отношение x > у. Выпишите все пары элементов, находящиеся в этом отношении.

3. Построить граф отношения 

xу <=> x  =  у  +  2 на  множестве 

{–3;  –1;  1;  2;  3;  4}  Z.

4. На множестве Y ={ у | у  Z , –13  ≤   у  ≤  –2 } задано отношение R:

xRу <=> x  = 2у.

Какие из следующих записей верны:

а) (–6;  –3)  R;                        б) (–3;  –6)  R;

 в) (–4;  –2)  R;                        г) (–8;  4)  R.

5.На множестве М = {–8; –6; –4; –2;  0;  2; 4}  Z  задано отношение xу <=> число x кратно числу у. Запишите множество , перечислив все его элементы. Принадлежит ли  пара (– 4;– 4)?  Найдите  (2),  (–8),  (0). Найдите -1(4), -1(–6), -1(0). Что значит отношение ху?   Найдите    (–4), (–2).

6. Дано множество числовых выражений 

М = {10; –2•3; (8 – 5)•3;

11•2 – 15,9(16)}. Постройте граф этого отношения «меньше, чем» на этом множестве.

7.Множество М членов семьи Смирновых состоит из отца (Ивана Михайловича), матери (Елены Андреевны) и четырёх детей: Миши, Тани, Васи и Оли. Между членами семьи существуют отношения родства, которые можно выразить словами: «быть мужем», «быть братом» и т. д.

а) укажите всевозможные отношения на множестве М;

б) запишите отношения «быть дочерью» с указанием всех его элементов и построить граф этого отношения;

в) постройте графы отношений «быть братом», «быть матерью».

8. На рис. 16 изображен граф отношения «а брат в» на множестве детей нашего двора {А; Б; В; Г; Д; Е; Ж; 3; И}. Кто из них является мальчиком? Кто девочкой? О ком нельзя по этому графу ничего сказать?


                                                                 

              


Рис. 16

9. Класс выставил на соревнования по плаванию команду мальчиков. В нее входили: Витя, Коля, Андрей и Саша. Коля проплыл дистанцию быстрее Андрея, но медленнее Саши, Андрей затратил на ту же дистанцию времени больше, чем Витя, который плавал медленнее Коли. Как распределились места на соревнованиях.(3адачу решите с помощью построения графа соответствующего бинарного отношения).

10. М – множество озер Канады. На М задано бинарное отношение «иметь одинаковый объем воды». Будет ли это отношение эквивалентностью?

9. Класс выставил на соревнования по плаванию команду мальчиков. В нее входили: Витя, Коля, Андрей и Саша. Коля проплыл дистанцию быстрее Андрея, но медленнее Саши, Андрей затратил на ту же дистанцию времени больше, чем Витя, который плавал медленнее Коли. Как распределились места на соревнованиях.(3адачу решите с помощью построения графа соответствующего бинарного отношения).

10. М – множество озер Канады. На М задано бинарное отношение «иметь одинаковый объем воды». Будет ли это отношение эквивалентностью?

Индивидуальные задания

1. На множестве N для каждого из следующих отношений найдите область определения рr1 и область значений рr2 и укажите, какими свойствами оно обладает:

1) ху  НОД (х;  у) = 1;

2) ху  у < 2х;

3) ху  х  =  у2;

4) ху  х ≤  у;

5) ху  у - х  = 12;

6) х у |у - х|  = 12;

7) ху (х - у) : 3;

8) ху  х у  = 30;

9) ху  х < у + 1;

10) ху  у = 2х + 1.

2. Будет ли заданное отношение эквивалентностью на указанном множестве:

1) «иметь одинаковую высоту» (на множестве гор в Европе);

2) «находиться на одинаковой высоте над уровнем моря» (для всех населенных пунктов Тибета);

3) «иметь одинаковую протяженность» (для всех рек России);

4) «иметь одинаковую загрязненность санитарной зоны предприятия» (для всех предприятий Смоленска);

5) «иметь численность населения не менее 5000 человек» (для всех населенных пунктов Подмосковья);

6) «иметь одинаковую степень риска извержения» (для всех вулканов Земли);

7) «иметь общую границу» (для всех государств Европы);

8) «иметь общие экономические интересы на Ближнем Востоке» (для всех государств – членов ООН);

9) «иметь одинаковую глубину» (для всех ущелий Кавказа);

10) «быть равноудаленными от Москвы» (на множестве городов России).

Задания для самоконтроля

1. Пусть  и σ отношения эквивалентности на множестве М. Докажите или опровергните, что   σ и  σ – есть отношения эквивалентности.

2. Известно, что отношение  – отношение эквивалентности. Дополните граф этого отношения.