Примеры решения типовых задач

ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ

Соответствие есть тройка множеств q = (X, Y, Q), где

Х – область отправления;

Y- область прибытия;

Q Í X ´ Y – график соответствия;

Пр₁Q – область определения соответствия;

Пр₂Q – область значений соответствия;

М(Q) = - матрица соответствия:

. (1.1)

Если (х, у) Î Q, то говорят, что элемент y соответствует элементу x. Геометрически это изображают стрелкой, направленной от х к у.

Виды соответствий:

а) полностью (всюду) определенное;

б) частичное;

в) сюръективное;

г) однозначное (функциональное): образом любого элемента множества Пр₁Q Í X является единственный элемент множества Пр₂Q Q Í Y;

д) инъективное (обратимое): прообразом любого элемента множества Пр₂Q Q Í Y является не более, чем один элемент множества Пр₁Q Í X;

е) биективное: одновременно полностью определено, сюръективно, и инъективно;

ж) взаимно однозначное (1 – 1 соответствие: одновременно полностью определено, сюръективно, функционально и инъективно.

q^-1 = (Х, Y, Q^-1), Q^-1 Í Y ´ X – соответствие, обратное соответствию q: Q^-1 = {(y, x): (x, y) Î Q)};

q p = (Х, Z, S), S = Q P Í Х ´ Z – композиция соответствий, q = (X, Y, Q), Q Í (X, Y) и p Í (Y, Z, P), P Í Y ´ Z, матрица композиции M(S) = M(Q P) равна булеву произведению матриц M(Q) и M(P). Ее элементы определяются по формуле:

. (1.2)

Если соответствие q = (Х, Х, Г), Г Í Х², задано на одном множестве, то его композиция с самим собой называется n – й степенью соответствия Гⁿ.

Соответствие (Х, Y, Г), где Г Í Х ´ Y, называется отображением, если оно полностью определено, т.е. если Пр₁Г = Х. Отображение может быть записано как Г: Х ® Y.

Отображение (Х, Y, Г), Г Í Х ´ Y, называется функцией, если оно однозначно (функционально).

3.27. Назовите известные Вам отношения на следующих множествах

а) множество натуральных чисел N, б) множество треугольников, в) множество государств, г) множество людей, д) множество морей, е) множество уравнений. Какими свойствами обладают эти отношения, к какому виду относятся?

3.28. Найдите область определения и область значений для отношений «быть отцом» и «быть братом» на множестве людей.

3.29. Построить бинарные отношения:

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

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

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

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

3.30. Определить тип отношения на множестве подмножеств некоторого множества «иметь непустое пересечение».

3.31. Укажите графики следующих отношений, заданных на множестве

Х = {0, 2, 4, 6, 8, 9}. Дайте их графическое и матричное представления, найдите Пр₁Г и Пр₂Г:

а) x < y; б) х нацело делится на у; в) х делитель у; г) х + у = 6. Найти Г^-1, , , .

3.32. Установить, какие из следующих отношений на N рефлексивны, антирефлексивны, симметричны, антисимметричны, транзитивны:

а) m + n четно; б) m + n £ 100; в) m + n нечетно; г) m/n является степенью двойки; д) m/n четно; e) mn нечетно.

3.33. Какое из отношений на Z симметрично:

а) mГn означает, что m + n делится на три;

б) mГn означает, что m – n делится на три?

3.34. Доказать, что отношение Г на некотором множестве Х является одновременно симметричным и антисимметричным в том и только в том случае, когда его матрица диагональна, т.е. а_ij = 0 при i ¹ j.

3.35. Отношения R и S заданы на множестве людей:

R = {(x, y): y – брат х}, S = {(x, y): y - жена х}. Что означают отношения и ?

3.36. Какими свойствами обладают отношения (Х, Р), (Х, Р^-1), (Х, Q) и (X, Q^-1), если:

а) Х – множество геометрических фигур, Р = {(x, y): x конгруэнтна y}, Q = {(x, y): x подобна у};

б) Х – множество прямых на плоскости, Р = {(x, y): x || y}, Q = {(x, y): x ^ y};

в) Х – множество окружностей на плоскости, Р = {(x, y): x концентрична y}, Q = {(x, y): x касается y};

г) Х = N, Р = {(m, n): m делится на n};

д) Х = Z, P = {(x, y): x – y делится на z Î Z };

S = {(y, z) Î Y ´ Z: окружность y вписана в треугольник z};

б) Х – множество деталей, Y – множество технологических операций, Z – множество рабочих, P = {(x, y): над деталью х выполняется технологическая операция y}, S = {(y, z): операцию y выполняет рабочий z};

в) Х – множество преподавателей университета, Y – множество читаемых дисциплин, Z – множество академических групп, P = {(x, y): преподаватель х ведет занятия по дисциплине y}, S = {(y, z): дисциплина у преподается студентам z};

г) Х – множество мужчин, Y – множество людей, Z – множество женщин, P = {(x, y): х – отец у}, S = {(y, z): y – родитель z}?

Что означает для этих примеров соответствие ?

3.16. Дано: Х = {x₁, x₂, x₃, x₄}, Y = {y₁, y₂, y₃, y₄}, Z = {z₁, z₂, z₃}, P = {(x₁, y₂), (x₂, y₄), (x₃, y₁), (x₃, y₃)}, S = {(y₁, z₁), (y₁, z₂), (y₂, z₁), (y₃, z₃), (y₄, z₁)}.

Матричным и графическим способом найти соответствия , , .

3.17. Дано множество А = {a₁, a₂, a₃, a₄} и отображение его на себя Г = {(a₁, a₂), (a₁, a₄), (a₂, a₄), (a₃, a₁), (a₄, a₃)}. Написать степени этого отображения Г² и Г³, их матрицы и изобразить графически Г, Г², Г³.

3.18. Дано множество А = {1, 2, 3, 4, 5, 6} и отображение его на себя (подстановка) Г = {(1, 3), (2, 4), (3, 6), (4, 2), (5, 5), (6, 1)}. Написать степени этого отображения от Г² до Г⁶, их матрицы и изобразить их графически.

3.19. Построить функцию f: A ® A, где А = {0, 1}, не имеющую обратной.

3.20. Пусть f: A ® B и g: B ® С – соответствия. Что является областью определения , если: a) f и g – функции, б) f – функция, g – отображение, в) f – отображение, g – функция, г) f и g – отображения? В каком из этих случаев сюръективно?

3.21. Доказать, что если функция f инъективна, то существует f^-1.

3.22. Если функция f сюръективна, следует ли отсюда, что f^-1 – отображение?

3.23. Пусть f: A ® B и g: B ® С – функции. Доказать, что: а) если f и g инъективны, то тоже инъективна; б) если f и g сюръективны, то тоже сюръективна?

3.24. Пусть f: A ® B и g: B ® С – функции и g сюръективна. Достаточно ли этого для того, чтобы обеспечить сюръективность ?

3.25. Даны множества R, N, Z, Q, C. Рассмотреть следующие отображения их в себя: а) х ® х, б) х ® х³. Выяснить, являются ли они инъективными.

3.26. Дано х, у Î Х = {-10, -9, …, 0, 1, …, 9, 10}. Какие из указанных ниже отношений на множестве Х являются функциями? Дать противоречащие примеры в случаях, когда отношение не является функцией.а) Г₁ = {(x, y): x = y²}, б) Г₂= {(x, y): x²= y}, в) Г₃ = {(x, y): x = - у}, г) Г₄ = {(x, y): x £ y},

д) Г₅ = {(x, y): x y = 6}, е) Г₆ = {(x, y): x³ = y}, ж) Г₇ = {(x, y): x = y³},

з) Г₈ = {(x, y): x = |y|}, и) Г₉ = {(x, y): |x| = |y|}, к) Г₁₀ = {(x, y): у |y| = x |x| }

Отображение (Х, Г) на одном множестве Г Í Х², называется отношением (бинарным отношением). Если элемент y Î Х находится в отношении Г к элементу х Î Х, т.е (х, у) Î Г, то пишут уГх. Отношение не обязательно полностью определено и не обязательно сюръективно.

Основные свойства, которыми могут обладать отношения:

а) связанные с одним элементом х:

- рефлексивность: хГх – истинно;

- антирефлексивность: хГх – ложно;

б) связанные с двумя элементами х и у:

- симметричность: из хГу следует уГх;

- антисимметричность: из (хГу и уГх) следует х = у;

- несимметричность: если хГу истинно, то уГх – ложно;

в) связанные с тремя элементами x, y и z:

- транзитивность: из хГу и уГz следует хГz.

Отношение Г есть

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

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

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

г) доминирования, если оно антирефлексивно, несимметрично и может не выполняться свойство транзитивности;

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

Так как соответствия, отображения и отношения определены на множествах, то для них естественно определены операции дополнения , объединения È и пересечения Ç.

2.1. Пусть даны множества Х = {a, b} и Y = {1, 2, 3}. Привести примеры следующих соответствий между этими множествами:

а) полностью определенные; б) частичные; в) сюръективные; г) однозначные; д) инъективные; изобразить их графически и записать матрицы.

Имеем Х ´ Y = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}. График любого из указанных соответствий Q Í X ´ Y.

Примеры соответствий:

а) всюду определенные: Q₁ = {(a, 1), (a, 2), (b, 3)}, Q₂ = { (a, 2), (b, 1)} – рисунок 2.1 а, б;

, .

б) Частичные Q₃ = {(b, 1), (b, 2)}, Q₄ = {(a, 2)} – рисунок 2.1 – в, г;

, .

в) Сюръективные Q₅ = {(a, 1), (a, 2), (a, 3)}, Q₆ = {(a, 1), (a, 3), (b, 2), (b, 3)} – рисунок 2.1 д, е;

, .

г) Однозначные Q₇ = {(a, 2), (b, 3)}, Q₈ = {(a, 2), (b, 2)} - рисунок 2.1 ж, з;

, .

е) Инъективные Q₉ = {(a, 2), (b, 1), (b, 3)}, Q₁₀ = {(a, 1), (a, 3)}- рисунок 2.1 – и, к.

, .

2.2. Даны соответствия q = (X, Y, Q), где Q = {(х₁, у₁), (х₁, у₂), (х₂, у₃), (х₂, у₄)} и p = (Y, Z, P), где Р = {(у₁, z₁), (y₂, z₁), (y₃, z₂), (y₄, z₂)}. Найти их графиче-

в) (N ², Q, S), S Î N ² ´ Q, S = {((m, n), q): m, n Î N, q Î Q; q = };

г) (Х ´ Y, Z, P): P Í (Х ´ Y) ´ Z; Х – множество прямых на плоскости, параллельной заданной прямой а; Y – множество прямых той же плоскости, не параллельных а; Z – множество точек этой плоскости Р = {((x, y), z): прямая х Î Х пересекается с прямой у Î Y в точке z Î Z};

д) то же, что и в предыдущем пункте, но все прямые рассматриваются в трехмерном пространстве.

3.8. Является ли соответствие (N, N₀, S), где N₀ = N È {0}, S = {(m, n) Î

N ´ N₀: остаток от деления m на 3 равен n} отображением, функцией?

3.9. Дать графическое и матричное представление соответствия (Х, Г), заданного на одном множестве, где Х = {a, b, c, d, e, f }, Г = {(a, a), (a, c), (a, f), (b, a), (b, e), (d, a), (d, d), (d, f), (f,b), (f, c), (f, e), (e, f)}.

3.10. Соответствия на одном множестве, заданные графически на рисунке 3.1, представить в матричной форме; записать графики этих соответствий.

Рисунок 3.1 – Соответствия задачи 3.10

3.11. Для соответствий, представленных в задаче 3.10, найти: Р^-1, Р², , , , .

3.12. Сколько имеется:

а) сюръективных соответствий из трехэлементного множества в двухэлементное? б) инъективных соответствий из трехэлементного множества в четырехэлементное?

3.13. Изобразить все: а) функциональные, б) взаимно-однозначные соответствия из трехэлементного множества в трехэлементное.

3.14. Даны три множества: X = {a, b, g, d}, Y = {a, b, c, d, e}и Z = {1, 2, 3}. Они связаны двумя соответствиями p = (X, Y, P) и q = (Y, Z, Q), где P = {(a, b), (b, a), (b, d), (g, a), (g, e), (d, d)} и Q = {(a, 2), (b, 1), (d, 1), (e, 1)}.

Найти композицию этих соответствий . Изобразить графически и записать матрицы этих соответствий и их композиции.

3.15. Что означает композиция соответствий (X, Y, P) и (Y, Z, S) если:

а) Х – множество точек плоскости, Y – множество окружностей, Z – множество треугольников, P = {(x, y): Î Х ´ Y: точка х – центр окружности у},

Дата добавления: 2015-06-26