Дискретная математика (стр. 2 )

A ´ B ¹ B ´ A (Декартово произведение не подчиняется коммутативному закону, и A ´ B = B ´ A справедливо, если А = В)

A2 = {(a, a), (a, b), (b, a), (b, b)}

A3 = {(a, a, a), (a, a, b), (a, b, a), (a, b, b), (b, a, a), (b, a, b), (b, b, a),
(b, b, b)}

Контрольные вопросы

1. Перечислите элементы множества M = {x ½ x ΠZ & x2 < 100}, где Z – множество целых чисел.

2. Установите истинность или ложность следующих утверждений:

а) {2} Î {1, 2, 3, 4, 5}

б) Æ = {Æ}

в) x Π{2, a, x}

г) 3 Î {1, {2, 3}, 4}

3. Равны ли между собой множества А и В? Если нет, то почему?

а) А = {2, 5, 4}, B = {5, 4, 2}

б) A = {1, 2, 4, 2}, B = {1, 2, 4}

в) A = {1, {2, 5}, 6}, B = {1, {5, 2}, 6}

г) A = {1, {2, 5}, 6}, B = {1, 2, 5, 6}

4. Определите, какие из следующих утверждений истинны, а какие ложны:

а) A ∩ Æ = A;

б) A ∆ A = Æ;

в) A \ A = A;

5. Пусть X = {0, 1}, Y = {a, b}. Найти:

а) X ´ Y

б) Y ´ X

в) X2

г) X ´ Y ´ X

д) X ´ Æ

2. Отношения

2.1. Понятие бинарного отношения

Бинарные (двухместные) отношения используются для определения каких-то взаимосвязей, которыми характеризуются пары элементов в множестве А (так, на множестве людей могут быть заданы, например, следующие бинарные отношения: «быть моложе», «быть сыном» и т. п.). Тогда все пары (a, b) элементов из А, между которыми имеет место данное отношение R, образуют подмножество, называемое бинарным отношением R, т. е. (a, b) Î R, при этом R Í A ´ A. Такое отношение (где а ΠА и b Î А) называют отношением на множестве А.

Пример. M = {дед, отец, внук}

M ´ M = {(дед, дед), (дед, отец), (дед, внук),

(отец, дед), (отец, отец), (отец, внук),

(внук, дед), (внук, отец), (внук, внук)}

R – «быть моложе»

R = {(отец, дед), (внук, дед), (внук, отец)}

Пусть А и В – два множества. В общем случае (бинарным) отношением R из множества А в множество В называется подмножество пар (a, b) Î R прямого произведения А и В: R Í A ´ B.

Для бинарных отношений обычно используется инфиксная форма записи:

a R b  = (a, b) Î R Í A ´ B

Пример. Пусть на множестве M = {2, 4, 6} определено отношение R – «быть меньше».

Задать списком отношение R.

R = {(2, 4), (2, 6), (4, 6)}.

2.2. Обратное отношение

Обратное отношение: R–1 = {(a, b) ½ (b, a) Î R}

Пример. Если R = {(1, 2), (1, 3), (2, 3)} («быть меньше»),

то R–1 = {(2, 1), (3, 1), (3, 2)} («быть больше»).

2.3. Композиция отношений

Пусть R1 Í А ´ B – отношение из множества А в множество B, а R2 Í B ´ C – отношение из множества B в множество C. Композиция отношений действует из А в В посредством R1, а затем из В в С посредством R2. Композицией двух отношений R1 и R2 называется отношение R Í А ´ C из А в C, определяемое следующим образом:

R = R1 ° R2 = {(a, c) ½ a Î A & c Î C & $ b Î B a R1 b & b R2 c}

Пример. A = {1, 2, 3}, B = {x, y}, C = {ÿ, D, O, *}

R1 Í A ´ B = {(1, x), (1, y), (3, x)}

R2 Í B ´ C = {(x, ÿ), (x, D), (y, O), (y, *)}

R1 ° R2 = {(1, ÿ), (1, D), (1, O), (1, *), (3, ÿ), (3, D)}

Пример. Если R – «быть сыном», то R ° R – «быть внуком».

Степенью отношения R на множестве А называется его композиция с самим собой:

Соответственно, R0 = I; R1 = R; R2 = R ° R и вообще говоря Rn = Rn–1 ° R.

2.4. Векторы

Вектор (кортеж) – упорядоченный набор элементов

v = (a1, a2, …, an) или v = <a1, a2, …, an>,

где а1, а2, …, an – компоненты (координаты) вектора. Число n компонент называется длиной (размерностью) вектора.

Два вектора v1 = (a1, a2, …, an) и v2 = (b1, b2, …, bm) равны, если они имеют одинаковую длину и соответствующие их координаты равны, т. е.

(a1, a2, …, an) = (b1, b2, …, bm)

если n = m & a1 = b1 & a2 = b2 & … & an = bm

Проекцией вектора v на i-ю ось называется его i-ая компонента:
прi v = ai.

Пример. пр2 (а, 2) = 2

Проекцией множества векторов V на i-ю ось называется множество проекций всех векторов из V на i-ю ось.

Пример. V = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}

V = {v1, v2, v3, v4, v5, v6};

пр2 v1 = 1; пр2 v1 = 2; пр2 v1 = 3; пр2 v1 = 1; пр2 v1 = 2; пр2 v1 = 3;

пр2 V = {1, 2, 3}.

Контрольные вопросы

1. Пусть отношение R задано на M = {1, 2, 3, 4, 5, 6}. Выписать все элементы R, если R = {(x, y) | x + y ³ 4 & x, y ΠM}

2. Пусть M = {1, 3, 5, 7} и отношение R Í M ´ M. Задать списком отношение R и обратное отношение R–1, если R = {(a, b) ½ (2a + b) Î M}

3. Пусть A = {(b, a), (c, e), (d, i), ( f, o), (g, u)} и B = {(v, a), (w, e), (x, i), (y, o), (z, u)}. Опишите отношение B ○ A-1.

4. Пусть R, S и T определены следующим образом:

R = {(1, 7), (4, 6), (5, 6), (2, 8)};

S = {(6, 10), (6, 11), (7, 10), (8, 13)};

T = {(11, ∆), (10, ∆), (13, *), (12, ™), (13, Ο)}.

Определите отношения:

а) R ○ S;

б) S ○ T;

в) (R ○ S) ○ T;

г) R ○ (S ○ T).

5. Пусть V = {(a, b, d), (c, b, d), (d, b, b)}. Чему равна проекция V на 2-ю ось?

3. Соответствия

 

Соответствием между множествами A и B называется подмножество G прямого произведения этих множеств. G Í A ´ B. Если (a, b) Î G, то говорят, что «b соответствует a при соответствии G». Можно считать, что соответствие между множествами A и B и бинарное отношение из А в В – это эквивалентные понятия.

Область определения соответствия G – множество ООG = {a ½ (a, b) Î G}. Область значений соответствия G – множество ОЗG = {b ½ (a, b) Î G}.

Соответствие называется всюду (полностью) определенным, если его ОО = A. В противном случае соответствие называется частично определенным.