Множества. Комбинаторика. Отношения (стр. 2 )

Упражнения для самостоятельного решения.

Докажите свойства множеств:

а) А = (АÇВ)È(АÇ(-В));

б) АÈ((-А)ÇВ) = АÈВ;

в) АÈВ = (АÇВ)È(АÇ( - В))È((-А)ÇВ);

г) АÇ(АÈВ) = А;

2. Докажите свойства булеана:

а) Р(АÇВ) = Р(А)ÇР(В);

б) P(ÇAi) = ÇP(Ai);

в) P(AÈB) = {A1ÈB1: A1ÎP(A), B1ÎB(A)};

г) ÆÎP(A)

д) Р(ÈАi) = {UBi: ВiÎ P(Ai)}.

1.1.3. Декартово произведение

Декартовым (прямым) произведением множеств А1,...,Аn называется множество всех упорядоченных наборов элементов из А1,...,Аn

А1x...xАn= {<a1...an>| a1ÎA1,..., anÎAn},

где <a1...an>=<b1...bn> ó a1=b1...an=bn. Если А1=..=Аn=А, то А1х...хАn называется декартовой степенью множества A и обозначается Аn.

Например: Пусть даны два множества A={1, 2, 3} и B={4, 5}. Тогда декартово произведение АхВ={<1, 4>, <1, 5>, <2, 4>, <2,5>, <3,4>, <3, 5>}, а произведение BxA={<4, 1>, <4, 2>, <4, 3>, <5, 1>, <5, 2>, <5, 3>}.

Из примера видно, что в результате получили разные множества, это означает, что декартово произведение некоммутативно, т. е. сомножители нельзя переставлять местами.

Свойства декартова произведения:

1) $ A, B, что AxB ¹ BxA

2) $ A, B,C, что Ax(BxС)¹ (AxB)xС

3)(AUB)xC = (AxC)U(BxC)

4)(А\В)хС = (АхС)\(ВхС), Ах(В\С) = (АхВ)\(АхС);

5) An-1 x A = An

Примеры:

[а, в]х[с, d] – прямоугольник,

R2 – плоскость (это декартов квадрат множества действительных чисел)

R3 – трехмерное пространство (декартов куб множества действительных чисел).

Подмножество R декартового произведения множеств А1,...,Аn называется п-местным отношением на множествах А1,...,Аn. Если RÍ Xn, то имеем n-местное отношение на X.

1.1.4. Бинарные отношения

Бинарным отношением между элементами множеств А и В называется любое подмножество R множества АхВ. Если RÍ A2, то имеем бинарное отношение на множестве А. Вместо <x, y> Î R часто пишут xRy.

Пример:

А={2,4}, В={2,3,5}, AxB={<2,2>,<2,3>,<2,5>,<4,2>,<4,3>,<4,5>},

R = {<2,2 >,<2,3>, <2,5>}.

Дополнением бинарного отношения R. между множествами А и В называется множество:

–R = (AxB)\R.

Обратным отношением для R называется:

R-1 = {<x, y>: <y, x>ÎR}.

Образом множества Х относительно R называется множество:

R(X) = {y:$xÎX:<y, x>ÎR}.

Здесь RÍ AxB, XÍ A, R(X)Í B.

Прообразом Y относительно R называется R-1(Y).

Композицией бинарных отношений R1Í AxB и R2Í BxC называется множество:

R1oR2 = {<x, z>|$y: <x, y>ÎR1, <y, z>ÎR2}

Свойства бинарных отношений:

1) (R-1)-1 = R,

2) (R1ÈR2)-1 = R1-1 È R2-1

3) (R1ÇR2)-1 = R1-1 Ç R2-1

4) -(R-1) = (-R)-l;

5) R1o(R2oR3) = (R1oR2)oR3

6) (R1oR2)-1 = R1-1oR2-1

7) (RoS)(X) = S(R(X)).

Докажем для примера свойство 1:

Доказательство: Пусть пара <x, y>Î (R-1)-1Þ <y, x>ÎR-1 Þ <x, y>ÎR. Показали включение (R-1)-1 Í R. Включение в обратную сторону доказывается аналогично.

1.1.5. Функции

Областью определения бинарного отношения R называется:

dR = {х|$y:<x, y>ÎR}.

Областью значений бинарного отношения R называется множество:

rR = {y|$x:<x, y>ÎR}.

Бинарное отношение fÎАхВ называется функцией из А в В, если

1)  df = A, rf = B,

2)  "хÎА: (<x, y1> = <х, у2>) Þ (у1 = у2).

Т. е. для каждого элемента х из А найдется не более одного элемента у Î В такого, что <х, у>Îf. Если rf = B, то f – функция из А на В. Вместо <x, y>Îf пишут у = f(x), f: A ® B, при этом х называют аргументом, а у – значением функции у в точке х. Функция f называется инъекцией А в В, если из того, что х1 ¹ х2 следует, что f(х1) ¹ f(х2). Если rf = В, то f называется сюръекцией А на В. Если f – инъекция и сюръекция одновременно, то говорят, что f осуществляет взаимнооднозначное соответствие между А и В (биекция). Подстановкой множества А называется взаимнооднозначное отображение А на себя. Множество всех функций из А в В обозначается ВA. Если в определении функции множество А заменить на декартово произведение А1х...хАn, то получим определение п-местной функции.

Упражнения

Докажите, что:

1)  dR-1 = rR, rR-1 = dR;

2)  dR1o R2 = dR1 Ç dR2;

3)  f(АÈВ) = f(A)Èf(B), f(AÇB)Í f(A)Çf(В) для любой функции f,

4)  f--1(АÈВ) = f--1(A)Èf--1(B), f--1(AÇB) = f--1(A)Çf--1(В).

1.1.6. Эквивалентность

Бинарное отношение iA ={<x, x>| хÎА} называется диагональю. Бинарное отношение R на А называется рефлексивным, если "хÎА:<x, x>ÎR; иррефлексивным, если "хÎА:<x, x>ÏR; симметричным, если <x, y>ÎR Þ <y, x>ÎR; антисимметричным, если (<x, y>ÎR,<y, x>ÎR) Þ (х = у); транзитивным, если (<x, y>ÎR,<y, z>ÎR) Þ (<x, z>ÎR). Рефлексивное, симметричное, транзитивное бинарное отношение на А называется эквивалентным. Классом эквивалентности элемента х по эквивалентности R называется х/R = {у|<x, y>ÎR}.

Пример: М = {1; 2; 3; 4; 5}, R = {(1; 1), (1; 2), (2; 1), (2; 2), (3; 3), (4; 4), (5; 5)}. Является ли бинарное отношение R рефлексивным, симметричным, транзитивным, иррефлексивным, антисимметричным?

u Все пары (1;1), (2;2), (3;3), (4;4), (5;5) принадлежат R, поэтому R рефлексивно. Пары (1;2) и (2;1) входят в R, все остальные пары симметричны. Это означает, что R симметрично. Все тройки пар, в которых третья получается “склеиванием” первых двух входят в R одновременно. Это такие тройки пар: {(1;1), (1;2), (1;2)}, {(1;2), (2;1), (1;1)}, {(1;2), (2;2), (1;2)}. Следовательно, R транзитивно. Пара (1;1) принадлежит R, поэтому R неиррефлескивно. Для двух разных элементов 1 и 2 обе пары (1;2) и (2;1) входят в R, т. е. R неантисимметрично.

ТЕОРЕМА. Множество А распадается на классы эквивалентности элементов множества А по эквивалентности R.

Доказательство. (zÎx/R) Þ (x/R = z/R). Действительно, по условию <х, z>ÎR. Если tÎz/R, то <z, t>ÎR. Отсюда,<x, t>ÎR Þ tÎx/R Þ z/R Í x/R. Если tÎx/R и zÎx/R, то <x, t>ÎR, <x, z>ÎR Þ <z, t>ÎR Þ tÎz/R Þ x/RÎz/R. Из включений z/R Í x/R Í z/R и следует искомое равенство.

Пусть zÎx/R Ç y/R. Тогда zÎx/R, zÎy/R Þ x/R = z/R = y/R Þ x/R = y/R. Итак, два класса эквивалентности либо не пересекаются, либо совпадают. Так как <x, x>ÎR, то хÎх/R и, следовательно, каждый элемент множества А попадает в один из классов эквивалентности. Тем самым доказано, что множество А – это объединение непересекающихся классов эквивалентности. ■

Множество классов эквивалентности множества А по эквивалентности R называется фактор-множеством А по R и обозначается A/R.

Упражнения

Докажите, что:

1) если R рефлексивно (иррефлексивно, симметрично, антисимметрично), то R-1 тоже рефлексивно (иррефлексивно, симметрично, антисимметрично);

2) если R1 и R2 рефлексивны, то R1oR2, R1 ÈR2, R1ÇR2 тоже рефлексивны;

3) если два слова А и В в некотором алфавите принадлежат бинарному отношению R тогда и только тогда, когда АВ = ВА, то R эквивалентно.

1.1.7. Частичный порядок

Бинарное отношение называется предпорядком на А, если оно рефлексивно и транзитивно. Рефлексивное, транзитивное и антисимметричное отношение на множестве А называется частичным порядком на А. Частичный порядок часто обозначается символом £.

Будем писать х < у, если х £ у и х ¹ у. Частичный порядок £ на множестве А называется линейным, если для любых элементов х и у из А или х £ у или у £ х. Множество с заданным на нем частичным порядком (линейным) называется частично (линейно) упорядоченным. Примерами бесконечных линейно упорядоченных множеств являются N0, Q, R относительно "естественного порядка". Важно заметить, что одно и то же множество можно упорядочить различными способами. Например, натуральные числа можно упорядочить "естественным образом", а можно упорядочить по возрастанию отдельно все нечетные числа и отдельно все четные, считая нечетное число предшествующим всякому четному.

Примером частично, но не линейно упорядоченного множества может служить множество всех пар натуральных чисел N2 со следующим порядком: <х, у> £ <х`,у`> ó х £ х`, у £ у`. Примером частично упорядоченного множества является множество всех подмножеств данного множества X, упорядоченное по включению М £ М¢, если

М Í М¢ где М, М¢Î Р(Х).

Элемент a – частично упорядоченного множества А называется максимальным, если а £ х ó a = x и минимальным, если x £ a ó a = x. Элемент a из А называется наибольшим элементом, если "хÎА: х £ а и наименьшим, если "х Î А: а £ х. Всякий наибольший элемент является максимальным, а всякий наименьший элемент – минимальным. Обратное, вообще говоря, места не имеет. Например, в тривиальном частично упорядоченном множестве (т. е. в котором a £ b ó a = b) всякий элемент является как максимальным, так и минимальным, но не наибольшим и, соответственно, не наименьшим. Верхней (нижней) гранью подмножества В частично упорядоченного множества А называется любой элемент a из А такой, что b £ a (a £ b) для любого bÎВ. Точной верхней (нижней) гранью подмножества ВÍ А называется наименьшая верхняя (наибольшая нижняя) грань В. Точная верхняя, грань множества В обозначается sup B (супремум), а точная нижняя грань – inf В (инфинум). Линейный порядок на множестве А называется полным, если каждое непустое подмножество множества А имеет наименьший элемент. В этом случае множество А называется вполне упорядоченным.