9957

1.3.Функциональные отношения.

Определение. Бинарное отношение f Х × У называется

функциональным, если каждому элементу x из X такому, что (х, у) f ,

соответствует один и только один элемент y из Y. Все элементы (упорядоченные пары) функционального бинарного отношения имеют различные первые координаты.

Отличительной особенностью матрицы функционального отношения является то, что в каждом ее столбце содержится не более одного единичного элемента. Граф функционального отношения характеризуется тем, что из

51

функции. Множество тех пар (x, y) , для которых выполнено соотношение x f y

называют графиком функции.

Пример 1.40.

К

Рис. 1.10 График функции.

Для того, чтобы задать соответствие, необходимо указать:

1.Множество Х, элементы которого сопоставляются с элементами другого множества.

2.Множество У, с элементами которого сопоставляются элементы xi Х .

3.Множество f Х ×У , определяющее закон, по которому перечисляются все пары (x, y) , участвующие в сопоставлении.

Примеры 1.41.

52

5)Пусть задано отношение f Х ×У , где Х – множество ключевых слов, а

У– множество Web-страниц. Пара (x, y) принадлежит f , если и только

если ключевое слово х содержится на странице у. Данное отношение функциональным не является, так как одно слово может встречаться на нескольких страницах.

Типы отображений.

Различают отображения X в Y, где каждый элемент x X имеет один и только один образ y = f(x) из Y. Примером такого отображения может служить рассмотренный выше пример (рис. 1.10).

Говорят, что имеет место отображение X на Y в том случае, если любой элемент из Y есть образ, по крайней мере, одного элемента из X. Такое отображение получило название сюръекция.

Если для любых двух и более различных элементов из Х их образы

множествами A и B, при котором каждому элементу a A отвечает один и только один элемент b B, и каждому элементу b B отвечает один и только один элемент a A. Функция, определяющая взаимно-однозначное соответствие называется биективной функцией или биекцией.

Примеры 1.42.

54

Пример 1.43.

Построим на множестве M={a, b, c, d} отношение, сюръекцию, инъекцию и биекцию максимальной мощности.

Решение. Отношение максимальной мощности совпадает с декартовым произведением M × M и его мощность равна 16.

При построение инъекции необходимо учитывать, что разным х соответствуют разные у, например F1={(a,b), (b, c), (c,d), (d,a)}, Для построения сюръекции нужно использовать все элементы у, F2={(a,a), (b,d), (c,c), (d,b)}. Обе эти функции являются как сюръекциями, так и инъекциями, следовательно, они – биекции. Мощность во всех случаях равна четырем.

Сами решения могут быть и другие, но максимальная мощность

Тогда имеют место следующие свойства:

1.(A1 Ì A2 ) ( f (A1 ) Ì f (A2 )).

2.f (A1 Ç A2 ) Ì f (A1 ) Ç f (A2 )

3.f (A1 È A2 ) = f (A1 ) È f (A2 )

4.f (A1 ) \ f (A2 ) Ì f (A1 \ A2 ).

5.f −1 (B1 È B2 ) = f −1 (B1 )È f −1 (B2 );

6.f −1 (B1 Ç B2 ) = f −1 (B1 )Ç f −1 (B2 );

7.f 1 (Y \ B) = X \ f −1 (B);

8.f 1(B1 \ B2 ) = f −1 (B) \ f −1 (B2 );

9.B1 Ì B2 f −1 (B1 ) Ì f −1 (B2 ).

10.f (f −1(B))Ì B

55

11. A f −1 ( f (A)).

Функции, отображения помимо математики широко используются в различных прикладных областях: теоретическом программировании, теории графов, теории систем и системотехнике, математической лингвистике, в теории чисел.

Множества A и B называются эквивалентными (A B), если между ними существует биекция (хотя бы одна). Эквивалентные множества называют равномощными, что обозначается так: |A|=|B|.

Эквивалентными друг другу оказываются все конечные множества с одинаковым числом элементов n (мощность каждого из этих множеств равна n).

Множество A называется счетным, если оно эквивалентно натуральному ряду N (A N).

С помощью биекции ϕ=N→A можно пересчитать все элементы из A,

снабдив их индексами. Можно записать, что А = {an }, n=1,2,…, ∞. Множество

вложены: Nчет N Z Q.

Хотя для любых двух из этих множеств нет равенства, они эквивалентны друг другу, то есть имеют одинаковую мощность и являются счетными: | Nчет |

= |N| = |Z| = |Q|.

Существуют бесконечные несчетные множества, и их мощность естественно считать большей, чем |N|.

Множество точек отрезка [0, 1] = {x R; 0≤x≤1} не является счетным (теорема Г. Кантора). Его мощность называется континуум и обозначается малой буквой c: |[0, 1]|=c.

Множество [0, 1] и любое эквивалентное ему множество называются

континуальными.

На вещественной оси R континуальными (и значит эквивалентными друг

56

другу и отрезку [0, 1]) являются, например, множества:

[a,b],

(a, b), при любом a<b;

(0, +∞);

множество (– ∞, + ∞), равное R.

Для любой биективной функции существует обратная функция.

Если f: X → Y – инъективное отображение, то для любых подмножеств А, А1, А2 его области определения X имеют место соотношения:

1.f (A1 Ç A2 ) = f (A1 )Ç f (A2 );

2.f (A1 \ A2 ) = f (A1 ) \ f (A2 );

3.A1 Ì A2 Û f (A1 ) Ì f (A2 );

4.f −1 ( f (A)) = A.

Композиция g f – это последовательное применение отображений

(первым действуем отображение f, вторым g).

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

Пример 1.44. Пусть f, g: R → R действуют по правилам:

Найдем g f ..

Перепишем выражение для f, убрав знак модуля:

57

1) Если x (1, ∞), то отображение f действует по правилу x3 и множество

(1, ∞) отображается во множество (1, ∞). На полученном множестве действие отображения g определяется как верхней, так и средней строкой, чтобы четко определить, когда какая строка действует. Исходное множество разобьем точкой x= 2 на два подмножества: (1;2] и (2; ∞), тогда f ((1; 2]) = (1; 8], и интервал (1,8]

целиком попадает в среднюю строку определения отображения g, а f((2; ∞)) = =(8;∞), что соответствует верхней строке определения g. Таким образом, мы получили, что

2)Если x [– 1; 1], то f ([– 1; 1]) = [– 1; 1], а это множество целиком попадает

всреднюю строку определения g. Значит,

отображение g определяется как своей средней, так и нижней строкой. Разобьем множество (– ∞,–1) на две части: (– ∞;–2) и [–2; –1). Рассмотрим каждую из этих частей отдельно.

58

Задачи

1.Будут ли следующие отношения функциональными? Найти их область определения и область значения.

a)f = {(1,3),(2,4),(3,5),(4,3),(5,4)}

b)f = {(1,2),(2,2),(1,3),(3,3),(4,2)}

c)f = {(х, у) х2 = у} R × R

d)f (х, у) = х

2. Пусть даны два множества N = {1, 2,…} – множество натуральных чисел и

59

6.Определите свойства отображения f (интъективность, сюръективность, биективность). Укажите область значения Im f .

a)f : N → N , f (x) = x + 2 ;

b)f : R → R, f (x) = 2x ;

c)f : R ® R, f (x) = 2x ;

d)f : R ® R, f (x) = x2 - 2x + 2 ;

e)f : R ® R, x 2x 2 +3x + 4 ;

f)f : Z × Z → Z , (a,b) a + b ;

g)f : Z → Z × Z , a (a, a) ;

h)A - конечное множество, f : B( A) ® N , X X ;

i)f : R ® R, x x3 .

инъективным, сюръективным, биективным?

8.Укажите, какие из перечисленных функций на множестве Z имеют обратную:

9.Приведите примеры отображения f : Х ® У:

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

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

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

d)биективного.

10.На заданных множествах-доменах:

1)Построить матрицы заданных отношений, определить тип отношений.