Материал: Дискретная математика теория и практика

Функции называются также отображениями. Пусть ƒ – функция из A в B. Если A = Dom ƒ и Im ƒ B, то говорят, что ƒ есть отображение множества A

в множество B. Если A = Dom ƒ и B = Im ƒ, то говорят, что ƒ есть отображение множества A на множество B.

Определение 3.39. Функция ƒ A B называется инъективной, или инъ-

екцией, если ( x, y A) ƒ(x) = ƒ(y) x = y.

Определение 3.40. Функция ƒ A B называется сюръективной, или сюръекцией, если для каждого элемента y B существует хотя бы один элемент x A такой, что y = ƒ(x).

Заметим, что сюръективная функция ƒ A B является отображением A

на B.

Определение 3.41. Функция ƒ A B называется биективной (биекцией)

или взаимно однозначным соответствием между множествами A и B, если она одновременно инъективна и сюръективна.

Пример 3.29. Какие из соответствий, графы которых изображены на рис. 3.13, являются инъективными, сюръективными, биективными функциями?

Решение. Функции f2 и f3 являются инъективными; f3 и f4 – сюръективными; f3 – биективной.

Определение 3.42. Если соответствие, обратное к функции ƒ A B, является функциональным и полностью определенным, то оно называется функ- цией, обратной к ƒ и обозначается ƒ-1.

Так как в обратном соответствии образы и прообразы меняются местами, то для существования функции, обратной к функции f A B, необходимо и достаточно, чтобы Im f = B и каждый элемент y Im f имел единственный прообраз.

Утверждение 3.4. Для функции ƒ: A → B существует обратная к ней функция ƒ-1: B → A тогда и только тогда, когда ƒ – биекция.

Определение 3.43. Пусть даны функции ƒ: A → B и g: B → C. Функция h: A → C называется композицией (суперпозицией) функций f и g, если

( x A) h(x) = g( f (x)).

Композиция функций f и g обозначается через f ° g, при этом знак ° часто опускается.

Задачи и упражнения к главе 3

1. Для бинарного отношения P A B найти Dom P, Im P:

а) А = {1, 2, 3, 4, 5}, B = {{1}, {1,2}, {2,5}, {3}}, aPX a X, где a А, Х В; б) А = {1, 2, 3, 4, 5}, B = {12, 16}, aPb bM a (см. определение 4.26);

в) A = Z × Z, B = Q, (a, b)Pc c = a , где (a, b) Z × Z, c Q; b

г) A = Z, B = Q, aPb a b = 1;

д) P = {(x, y) R × R | y = x2 + x + 1}; е) P = {(x, y) R × R | y = lg(x2 + 1)};

ж) P = {(x, y) R × R | y = arcos x};

52

з) P = {(x, y) R × R | y = tg x}.

2. График отношения Р, заданного на множестве R, изображен на рис. 3.14.

а) Найти Dom P, Im P;

б) Установите, какие из следующих записей верны: 1Р2, 1Р1, –3Р–1.

y

3.На множестве Х = {2, 4, 6, 8, 10} задано отношение Р: «х кратно y». а) Построить граф отношения Р;

б) Перечислить все пары чисел из множества Х, находящихся в отношении Р; в) Указать Dom P, Im P.

4.Изобразить граф отношения Р = {(a, 1), (a, 2), (b, 2), (b, 3), (c, 1), (c, 4)} и

Q = {(1, α ), (2, β ), (3, α )}. Найти Dom P, Im Q, Q-1, P o Q.

5.Определить свойства бинарного отношения по его графу (рис. 3.15).

6.Выяснить, является ли отношение Р рефлексивным, симметричным, антисимметричным, транзитивным:

а) P1 = {(a,3), (a,2), (a,4), (b,1), (c,2), (c,4), (c,3)},

P2 = {(1,1), (2,2), (2,1), (3,3), (4,4), (4,3), (1,4), (2,4), (3,2), (3,4)}; б) P1 = {(b,2), (a,3), (b,1), (b,4), (c,1), (c,2), (c,4)},

P2 = {(1,1), (1,2), (1,4), (2,2), (2,4), (3,3), (3,2), (3,4), (4,4)}.

Изобразить Р1 и Р2 с помощью графов. Найти матрицу отношения (P o P )−1 .

1 2

Проверить с помощью матрицы P2 , является ли отношение Р2 рефлексивным,

антирефлексивным, симметричным, антисимметричным, транзитивным?

8. На рис. 3.16 приведены графы отношений P, Q, S, T. Укажите среди них отношения эквивалентности.

53

9. На множестве Х = {a, b, c, d, e} задано отношение Т = {(a, a), (a, b), (b, b),

(b, a), (c, c), (c, d), (d, c), (d, d), (e, e)}. Доказать, что Т – отношение эквивалентности. Найти классы эквивалентности.

10.На множестве A = {1, 2, 3, 4, 5} задано отношение эквивалентности Т. Оно определяет разбиение этого множества на классы эквивалентности:

A1 = {1, 3, 5}, A2 = {2, 4}. Построить граф отношения Т. Записать все упорядоченные пары чисел, принадлежащих этому отношению.

11.На множестве Х = {1, 2, 3, 4, 5, 6} задано отношение S = {(1,1), (1,2), (2,1), (2,2), (3,3), (4,4), (5,4), (5,5), (6,6), (4,6), (6,4), (5,6), (6,5), (4,5)}. Доказать, что S –

отношение эквивалентности. Построить граф отношения S. Разбить на классы эквивалентности множество Х.

12.На множестве Х = {a, b, c, d, e, f} задано отношение эквивалентности Т. Оно определяет разбиение этого множества на классы эквивалентности {a, b}, {c}, {d}, {e, f}. Записать все пары элементов, принадлежащих этому отношению. Построить его граф.

13.Доказать, что отношение P: (a,b)P(c,d) a2 + b2 = c2 + d2 является отношением эквивалентности на множестве R × R. Найти классы эквивалентности и изобразить их на координатной плоскости.

14.На множестве N задано бинарное отношение P: aPb последняя цифра в десятичной записи числа а совпадает с последней цифрой в десятичной записи числа b. Доказать, что P – отношение эквивалентности. Сколько элементов в фактор-множестве N/P?

15.Пусть А = {1, 2, 3}. Доказать, что заданное на Р(А) бинарное отношение R:

X R Y X = Y , является отношением эквивалентности. Найти классы эквива-

лентности.

16. Доказать, что следующие отношения являются отношениями эквивалентности:

a) отношение Р на множестве точек плоскости: (М1, М2) Р ординаты точек М1 и М2 равны;

б) отношение Р на множестве С: (z1, z2) Р z1 = z2 ;

в) отношение Р на множестве С \ {0}: (z1, z2) Р arg z1 = arg z2. Найти классы эквивалентности. Изобразить их на плоскости.

17.Даны множества: А – множество букв латинского алфавита, В = {a, b, c, d, e, f}, C = {c, f}, D = {b, a, d}, E = {k, l, m, n, d}, F = {k, l, m, n}. Рассмотреть между ними отношение Р: «быть подмножеством». Построить граф отношения Р. Выписать все пары множеств, находящихся в отношении Р. Определить свойства этого отношения. Доказать, что <М, Р> – частично упорядоченное множество, где М – множество всех множеств, указанных выше. Построить диаграмму Хассе частично упорядоченного множества <М, Р>. Определить минимальные и максимальные элементы, наименьший и наибольший элементы (если они имеются).

18.Отношение Р задано на множестве А = {a, b, c, d, e} с помощью

графа (рис. 3.17). Доказать, что пара <А, Р> – частично упорядоченное множество. Построить диаграмму Хассе.

54

22.Пусть А = {0; 1; 2}×{2; 5; 8}. Отношение частичного порядка R на А определено следующим образом: (a, b)R(c, d) (a + b)>(c + d) (a + b делит c + d). Нарисовать диаграмму Хассе для частично упорядоченного множества А. Какие элементы на частично упорядоченном множестве будут являться максимальными, минимальными? Имеет ли А наибольший и наименьший элементы?

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

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

б) f: R → R, f(x) = 2x; в) f: R → R, f(x) = 2x;

г) f: R → R, f(x) = x2 – 2x + 2; д) f: R+ → R, f(x) = lg x;

е) f: R → R, x a 2x 2 +3x + 4 ;

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

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

и) A – конечное множество, f: Р(А) → N, X a X ;

к) f: R → R, x a x3.

55

Глава 4. Алгебраические структуры

4.1. Алгебраические операции и их свойства

Бинарные и n-местные алгебраические операции

Пусть А – непустое множество.

Определение 4.1. Отображение множества А×А в А называется бинарной

алгебраической операцией на множестве А.

Примерами бинарных алгебраических операций являются обычное сложение и умножение на множестве целых чисел, объединение и пересечение на булеане непустого множества.

Определение 4.2. Отображение множества Аn в А называется n-арной

(n-местной) алгебраической операцией на множестве А, а число n (n ≥ 1) – ран-

гом операции. Выделение (фиксация) некоторого элемента множества А назы-

вается нульарной (нульместной) операцией на множестве А, число 0 – рангом

нульарной операции.

Определение 4.3. Частичная функция из множества Аn в А называется

частичной n-арной алгебраической операцией на множестве А.

Пример 4.1. 1. Пусть А ≠ . Отображение, ставящее в соответствие каж-

дому подмножеству X Р(A) его дополнение X , является унарной алгебраической операцией на Р(А).

2.Операция деления рациональных чисел является частичной бинарной алгебраической операцией на множестве рациональных чисел.

3.Операция, ставящая в соответствие каждому кортежу натуральных чисел длины n наибольший общий делитель этих чисел, является n-арной алгеб-

раической операцией на множестве N.

Для обозначения n-арной алгебраической операции используется та же форма записи, что и для произвольных отображений. Если f есть n-арная ал-

гебраическая операция на множестве А и ((x1, x2, …, xn), xn+1) f, то пишут

xn+1 = f (x1, x2, …, xn) и говорят, что xn+1 является значением операции f при значениях аргументов x1, x2, …, xn.

Свойства бинарных алгебраических операций

Пусть и ◦ – произвольные бинарные алгебраические операции на непустом множестве А.

Определение 4.4. Бинарная алгебраическая операция называется ком-

мутативной, если ( a, b А) a b = b a.

Определение 4.5. Бинарная алгебраическая операция называется ассо-

циативной, если ( a, b, c А) a (b c) = (a b) c.

Если операция ассоциативна, то можно опускать скобки и писать a b c вместо a (b c) или (a b) c.

Определение 4.6. Бинарная алгебраическая операция ◦ называется дист- рибутивной относительно бинарной операции , если

( a, b, c А) (a b) ◦ c = (a ◦ c) (b ◦ c) и c ◦ (a b) = (c ◦ a) (c ◦ b).

56