2.2.2 Примеры решения задач

Задача 1. На множестве А={1, 2, 3, 4} задано отношение R ={<x; y>: x > y}. Найти область определения, область значений R. Задать матричным способом R ^-1; ; . Указать свойства отношения.

Решение. Укажем сначала все упорядоченные пары элементов множества А, которые принадлежат отношениюR:R= {<2, 1>,<3, 1>,<3, 2>,<4, 1>,<4, 2>,<4, 3>}.

Область определения отношения D_R= {2, 3, 4}, область значений отношенияE_R= {1, 2, 3}.

={<у; х>: <x;y>R}={<x;y>:y>x}={<x;y>:x<y}.

={<х; у>:<x;y>R}={<x;y>:xy}.

Матрицы отношений R,R ^-1; ипредставлены ниже:

;;

;.

Поясним способ определения элементов r_ijматрицыкомпозиции отношенияRс самим собой на нескольких примерах:

;

;

;

;

;

…

Отношение Rявляется антирефлексивным, так как для любого элементаxRне выполняется условиеx>x.

Отношение R– несимметрично, так как для любыхx,yА из того, чтоx>y, не следует, чтоy>x.

Отношение Rобладает свойством антисимметричности. Оно также и транзитивно, так как для любыхx,y,zА, еслиx>yиy>z, значитx>z.

Задача 2.На множествеN  N, гдеN – множество натуральных чисел, определим отношение: <х, у><u,v>x+v=y+u. Доказать, что- отношение эквивалентности на этом множестве.

Решение. Отношениеявляется рефлексивным, поскольку <х, у><х, у>, что следует из выполнения равенства х + у = у + х.

Докажем, что отношение является симметричным. Для этого нужно доказать, что если <х, у><u,v>, то <u,v><х, у>. В самом деле, еслиx+v=y+u, тоu+y=v+x.

Для того чтобы доказать, что отношение является транзитивным, необходимо доказать, что если <х, у><z,t> и <z,t><u,v>, то <х, у><u,v>. Это равносильно следующему условию:

.

Складывая почленно уравнения системы, получаем . Упрощая последнее равенство, получаем. Тем самым доказано, что отношениеявляется транзитивным.

Рефлексивное, симметричное и транзитивное отношение является эквивалентностью, следовательно –отношение эквивалентности.

Задача3. Доказать, что отношениеявляется эквивалентностью на множестве. Какое разбиение определяет указанная эквивалентность?

Решение.ОтношениеRобладает свойством рефлексивности, поскольку ему принадлежат пары <1, 1>, <2, 2>, <3, 3>.

Отношение Rсимметрично. В самом деле, найдем обратное ему отношение:. Очевидно, выполняется условие симметричного отношения:.

Проверим условие транзитивности: . Несложно показать,, следовательно,. Таким образом,R– эквивалентность на множестве.

Для вычисления разбиения, соответствующего данной эквивалентности, найдем классы эквивалентности, порожденные элементами 1, 2, 3:

;

;

.

Искомое разбиение имеет вид: ,.

Равенство классов эквивалентности, порожденных элементами 1 и 3, является наглядным подтверждением следующего общего факта: класс эквивалентности порождается любым своим элементом.

2.2.3 Задачи для самостоятельного решения

1. Пусть I= {х₁,x₂, х₃} - универсальное множество, а Х = {х₁, х₂},Y= {x₂,x₃},Z={x₃} – его подмножества. Определить перечислением множества:XX,ZZ,XY,YX,XYYX,XYYX.

2. Пусть и- отрезки действительной прямой. Найти геометрическую интерпретацию множеств:

а) ;

б) .

3. Доказать, что для произвольных множеств А, В, С, Dвыполняются тождества:

а) ;

б) .

4. Пусть X={«атом», «стол», «море», «мера»}, Y={а, м, о, р, е}. Составьте декартово произведение XY. Отметьте в нем пары, связанные соответствием «в слово x входит буква y».

5. Пусть V– множество положительных целых чисел от 1 до 20, на котором задано отношение R: «число x делится на число y», причем xV,yV. Выпишите все пары из множества V², находящиеся в отношении R.

6. На множестве определены отношения «быть меньше» и «отличаться на 2». Задать отношения различными способами. Найти область определения и область значения отношений, тождественное отношение, универсальное отношение, обратное отношение, дополнение, объединение и пересечение отношений, композицию отношений.

7. Построить матрицу отношения , где. Найти;.

8. На множестве натуральных чисел заданы отношения и. Найти составные отношения,,,,,.

9. Отношение Rзадано на множестве А = {1, 2, 3} матрицей:

.

Выполнить операции над R: найти дополнение, обратное отношение, квадрат отношения.

4. На множествезаданы отношения–быть сыном,–не быть сыном,–быть сыном или внуком,–быть сыном или отцом. Задать отношения матричным способом (рисунок 3). Выразить,,через.

5. На множестве натуральных чисел задано отношение х делит у}. Найти;;,.

6. На множестве действительных чисел задано отношение . Найти;;,,,.

7. Каковы свойства отношений:

а) , заданного на множестве;

б) – быть делителем на множествеN;

в)–находиться на одинаковом расстоянии от начала координат на множестве точек плоскости;

г) –пересекаться (иметь непустое пересечение) на булеане некоторого множества;

д) –являться строгим включением.

е) ,.

ж),.

4. Задать в матричной форме отношение –быть дополнением, заданное на булеане множества. Найти свойства отношения.

5. Найти ,,,,для отношения. Установить свойства отношения.

6. Та же задача при условии, что х, у,А={1, 2, 3, 4, 5, 6}.

7. Привести примеры отношений:

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

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

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

4. Найти транзитивное замыкание отношения «быть сыном» на множестве (см. рисунок 3).

5. Пусть, отношениеRна М задано графически (рисунок 4). Вычислить транзитивное замыкание отношенияR.

6. Пусть отношение R– «быть руководителем» определено на множестве сотрудников организации М. Назвать отношения,, рефлексивное транзитивное и транзитивное замыканиеR. Каковы свойства отношений? Упорядочено ли множество М?

7. Разбиение множества Zстроится следующим образом:,,, …. Какую эквивалентность определяет это разбиение. Перечислить классы эквивалентности и фактор-множество.

8. На рисунке 5 схематично представлено расположение офисов семи подразделений, расположенных на двух этажах. На множестве офисов заданы отношения- «иметь общую стену» и- «находиться на одном этаже». Определить свойства отношений. Какое из этих отношений определяет эквивалентность на множествеM. Найти транзитивное замыкание нетранзитивного отношения.

4. Сформулировать алгоритм вычисления матрицы транзитивного замыкания нетранзитивного отношения.

5. На множестве Х = {х: xN, х<12} задано отношение R: «x и у имеют один и тот же остаток при делении на 5». Покажите, что R–отношение эквивалентности. Запишите все классы эквивалентности, на которые разбивается множество данным отношением.

6. Рассмотрите на множестве людей следующие отношения, укажите среди них отношения эквивалентности:

а) «х похож на у»;

б) «х и у живут в одном доме»;

в) «xи y - друзья»;

г) «х живет этажом выше, чем y».

4. Отношение S на множестве Х={1, 2, 3} состоит из пар: <1, 2>, <1, 1>, <2, 2>, <2, 1>, <3, 1>, <3, 3>. Является ли S отношением эквивалентности на множестве Х?

5. Какие из ниже перечисленных отношений являются отношениями порядка, строгого порядка?

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

б) «отрезок х короче отрезка у в 2 раза» (на множестве отрезков плоскости);

в) «xстарше по возрасту, чем у» (на множестве людей);

г) «х является сестрой у» (на множестве людей);

д) «х живет в одном доме с у» (на множестве людей);

е) «x–друг у» (на множестве людей);

ж) «число х не меньше числа y» (на множестве R);

з) «окружность х лежит внутри окружности у» (на множестве окружностей плоскости).

28. Докажите, что если R– частичный порядок, тоR^-1– также частичный порядок.

29. Привести пример линейного порядка на множестве N  N, гдеN – множество натуральных чисел.

30. Доказать, что всякий частичный порядок на конечном множестве может быть продолжен до линейного порядка.

31. Докажите, что если отношения R₁и R₂рефлексивны, то рефлексивны и отношения R₁R₂, R₁R₂.

32. Докажите, что если отношения R₁и R₂симметричны, то симметричны и отношения R₁R₂, R₁R₂.