1.7. Соответствие, отображения и функции

Соответствие – соответствием между множествами А и В называется подмножество GА х В. Соответствие G называется функциональным или однозначным, если образом любого элемента множества G₁ является единственный элемент множества G₂, причем G₁, G₂ G.

Пример. Англо-русский словарь устанавливает соответствие между множеством английских и русских слов. Это соответствие не является функциональным.

Функцией называется функциональное соответствие. Если функция f устанавливает соответствие между множествами А и В, то говорят, что функция f имеет тип АВ (обозначение f : АВ). Полностью определенная функция f : АВ называется отображением А в В. Образ А при отображении f обозначается f(A).

Если f(A) состоит из единственного элемента, то f называется функцией –константа.

Отображение типа АА называется преобразованием множества А.

Важным понятием при построении математических моделей дискретной математики является понятие отношения между элементами двух множеств. Если для каждого элемента x  X можно сказать, что элемент x находится либо не находится в данном отношении  с элементом y  Y, то говорят, что между элементами множества X и Y задано отношение , и пишут x  y, в том случае, когда x находится в отношении с элементом y. Например, между множеством Х студентов данного курса и множеством Y всех учебных предметов по данной специальности существует отношение  такое, что х  y означает «студент х сдал экзамен по предмету y. Между элементами множеств Х и Y может существовать много различных содержательных отношений, если Х и Y - содержательные множества. Например, такими отношениями являются всевозможные функциональные отношения, или отображения.

Отображения. Отношения  между элементами множеств X и Y называют отображением множества Х в множество Y, если каждый элемент х  Х обязательно находиться в отношении с некоторым элементом y  Y, причем этот элемент y  Y - единственный для данного элемента х  Х. Отображение множества Х в множество Y обозначают через  (либо другой подходящей буквой) и пишут : Х  Y, при этом вместо х  y для х  Х и y  Y часто пишут y = (х) и говорят что y есть образ элемента х при отображении. На картинке отображение  : Х  Y удобно представлять в виде двудольного графа.

х₁ х₂ х₃ х₄

X



Y

у₁ у₂ у₃ у₄

Здесь точки верхнего ряда изображают элементы множества Х, нижнего ряда - множества Y, и если имеет место y = (x), то из точки х выходит стрелка, заходящая или входящая в точку y. Такую картинку называют двудольным графом отображения : X  Y, причем точки этой картинки именуют вершинами графа, а стрелки - дугами графа и говорят, что отображение  является :

а). Инъективным, если в каждую вершину y  Y заходит или входит не более одной дуги ;

б). Сюръективным, если в каждую вершину y  Y входит не менее одной дуги ;

в). Биективным, или биекцией, если  инъективно и сюръективно одновременно.

Для любого отображения  : X  Y и любого не пустого подмножества А  Х множество образов всех элементов х  А при отображении  называют образом множества А и обозначают (А),так что (А) = y Y : y = (x) для некоторого х  А.

Для общности и стройности суждений полагают () = . Если (Х) = Y, то, очевидно,  является сюръективным отображением.

В приложениях часто используется отображение : Х  R⁺, при этом (х) выступает в роли цены, или веса, или длины, или пропускной способности элемента х  Х.

Очевидно, задание биекции : X  Y равносильны установлению взаимно однозначного соответствия между элементами множеств Х и Y.

Отображения : Х  Y и Y₁: Х  Y называются равными, если из х  y следует x ₁ y и наоборот, т.е. если эти отображения можно изобразить одним и тем же двудольным графом отображения.

Пусть Х и Y - конечные непустые множества, причем |X| = m, |Y| = n. Тогда количество всех отображений : X  Y равно n^m. Действительно, чтобы получить произвольное отображение  X  Y, надо построить двудольный граф этого отображения, для чего выбрать для каждой вершины x  X одну и только одну дугу среди n дуг (n = |Y| ), которые могут выходить из вершины х и заходить в вершины y  Y, причем для разных вершин х, х₁ Х указанный выбор дуг делается независимо. Поэтому количество всех таких выборов, а значит, и всех двудольных графов отображений будет n*n*...*n, где количество сомножителей равно m = |X|, так что получается искомое количество n^m.

Множество всех отображений : X  Y иногда обозначают как Y^x, ибо для конечных X и Y тогда получают формулу |Y^x| = |Y^|x||. Но никто и нечто не мешает рассматривать последнюю формулу для бесконечных X и Y и считать эту формулу правилом возведения в кардинальную степень |X| кардинального числа |Y|.

Например, с = 2^a . Далее, сумму |X| + |Y| произвольных кардинальных чисел определяют как мощность |X + Y| множества X + Y, составленного из всех вершин х  Х и y  Y двудольного графа произвольного отображения : X  Y, а произведение |X| * |Y| определяют как мощность |X * Y| множества X * Y, составленного из всевозможных упорядоченных пар (x, y), где x  X, y  Y, т.е. из дуг двудольного графа, в котором из каждой вершины x  X выходят дуги в каждую вершину y Y. Такое определение суммы и произведения кардинальных чисел согласуется с обычным смыслом m + n и m * n для конечных множеств X и Y при m = =|X|, n = |Y|.

Преобразования. Отображение :X  X называют преобразованием множества Х и на картинке изображают в виде орграфа (ориентированного графа) преобразования, вершинами которого являются элементы x  X, а дугами - пары (х₁, х₂) такие, что х₁ х₂ , т.е. х₂ = (х₁). Преобразования : X  X можно изображать двустрочной записью, помещая в первой строке этой записи элементы x  X, а во второй - под ними их образы (х). Например, для

Х = 1,2,...,7 одно из преобразований изобразим двустрочной записью и орграфом :

1 2 3 4 5 6 7 3

=

3 7 2 5 4 6 1 1 2 4 5 6

7

Видно, что это преобразование биективно, причем (А) = А для множеств А=, А = 1,2,3,7 А = 4,5 ,А = 6, и только для них.

Биективные преобразования называют подстановками. Очевидно орграф подстановки  конечного множества распадается на части, однозначно определяемые подмножествами А такими, что А = (А). Такие части (вершины вместе с дугами ) принято называть циклами подстановки . Максимальное количество циклов имеет тождественная подстановка , т.е. такая, что х = (х) выполняемая для любого х  Х. Подстановки, имеющие один цикл, называются одноцикловыми. Одноцикловые подстановки служат, например, моделями для описания обхода одним человеком n различных пунктов (начав движение в исходном пункте, человек обходит все остальные по одному разу и возвращается в исходный пункт). Заметим, что количество всех подстановок n -элементного множества Х равно n! = n * (n-1)*...*2*1, потому что элементу x₁  X можно поставить в соответствие любой из n элементов множества Х, но элементу х₂ при х₂  х₁, можно поставить в соответствие по подстановке  любой элемент из оставшихся n-1 элементов, которые не являются образом элемента х₁ и т.д.

В связи со сказанным выше удобно обозначить через Х! множество всех бииективных преобразований множества Х, ибо тогда | X! | = | X |! для конечных множеств Х.

Рекомендуется помнить, что 10! = 3628800, а 0! = 1 (по соглашению).

Разумеется, количество всех одноцикловых подстановок n - элементного множества равно (n-1)!.

Пример 1. Каждое натуральное число можно разложить на произведение простых чисел. Если расположить простые делители в определенном порядке например не убывание то получим функцию

G(42)=(2, 3, 7); G(23)=23;

G(100)=(2, 2, 5, 5) и т. д.

Пример 2. Каждому человеку соответствует множество его знакомых.

G(Иванов)=(Сидоров, Николаев,…..,Семенов)

Способы задания функций.

Наиболее простой способ задания функций – это таблица, т. е. список пар (x, f(x)). Однако таким образом могут задаваться только функции, определенные на конечном множестве. Таблицы функций, определенных на бесконечных множествах (например, тригонометрических) задают эти функции только в конечном числе точек.

Другим способом задания функций является формула, описывающая функцию, как суперпозицию других (исходных) функций. Для задания функции могут использоваться также графики

Еще два способа задания функций:

а) рекурсивная процедура

б)  x, если xM

f(x) = 

 0, если xM

Все приведенные положения по теории множеств используются при изложении остальных разделов дискретной математики.

Упражнения.

1. Найдите множества АВ, АВ, А\В, В\А, если:

а) А={3,5,6,7,9}, В={4,6,7,8};

б) А={3,5,6,7,9}, В={2,4,8};

в) А={2,3,4,5,6}, В={3,4,5};

г) А=Z, В=N; д) А=R, В=Q,; е) А=Z, В=Q;

ж) А=xxR, -1x5,В=xxR, -3x2;

з) А=xxR, -1x3, В=xxR,3x5;

и) А-множество всех прямоугольников, В- множество всех ромбов.

2. Найдите множества Аи В если:

а) А\В=a,b,В\А=c,d,АВ=x,y,z;

б) АВ=a,b,c,d,e,f,АВ=c,d,А\В=a,e,f;

в) АВ=a,b,c,d, АВ=, А\В=a.

3. Пусть А - множество решений уравнений f(x)=0, В - множество решений уравнения п(ч)=0 .Выразите через А и В множество решений:

а) уравнения f(x)g(x)=0;

б) уравнения f(x)g(x)=0;

f(x)=0;

в) системы уравнений

g(x)=0.

4. Выразите множество действительных корней уравнения f(x)=0

через множества А=xf(x)0и В=xf(x)<0.

5. Найдите следующие множества:

а) А; б) А; в) АА; г)АА;

д) А\А; е) А\; ж) /А.

6. Даны множества А и В , причем АВ. Найдите:

а) АВ; б) АВ; в)А\В.

7. На диаграмме Эйлера-Венна изображены множества А,В,С(рис.8). Укажите (заштрихуйте)на этой диаграмме множества:

а) АВ(ВС); б) А(ВС);

в) (А\В)С;

г) (А\В)(В\С).

8. Докажите, что для любых множеств А,В,С:

а) А(ВС)=(АВ)(АС);

б) А(ВС)=(АВ)(АС);

в) А\(ВС)=(А\В)(А\С).

9. Пусть А и В - подмножества множества М. Докажите, что :

а) АВ=АВ; б) АВ= АВ.

10. Множество А состоит из n элементов , а множество В- из m элементов (m>n)/ какое наибольшее и наименьшее число элементов могут содержать множества АВ, АВ, А\В, В\А?

11. докажите, что если А состоит из n элементов, В- из m элементов, АВ - из k элементов, то множество АВ состоит из n+m-k элементов.

12. Каждый ученик в классе изучает английский или французкий язык. Английский язык изучают 25 человек, французкий-27, а оба языка-18. Сколько учеников в классе ?

13. В классе 30 учеников. Каждый из них занимается футболом, либо хоккеем. Половина учеников класса занимается хоккеем, а 5 учеников -и хоккеем и футболом. Сколько учеников в классе занимается футболом ?