Книги по разным темам Pages:     | 1 | 2 | 3 | 4 |   ...   | 12 |

1. A = A 2. A B = B A I I законы коммутативности 3.A B = B A U U 4.(A B) C = A (B C) I I I I законы ассоциативности 5.(A B) C = A (B C) U U U U 6. A (B C) = (A B) (A C) I U I U I законы дистрибутивности 7. A (B C) = (A B) (A C) U I U I U 8.A B = A B I U законы дополнения 9. A B = A B U I 10. A A = A I законы идемпотентности 11. A A = A U 12. A E = A I 13. A = A U 14. A A = E U 15. A A = I Все данные равенства могут быть доказаны по единой схеме, использующей определение равенства двух множеств А и B:

A = B A B и B A.

В качестве примера приведем доказательство равенства 7.

Пусть x А (B C). Тогда либо x А, либо x B C. Если x А, то U I I x A B и x А C, следовательно, x (A B) (A C). Если x B C, то U U U I U I X B и x C, значит x A B и x A C. Отсюда, x (A B) (A C). Таким U U U I U образом, установлено включение A (B C) (A B) (A C) (а) U I U I U Пусть теперь x (A B) (A C). Тогда x A B и x А C. Если x A, то U I U U U x A (B C). Если x A, то тогда должно быть x B и x C. Отсюда следует, что U I x B Cи, следовательно, x A (B C) I U I Таким образом, установлено включение (A B) (A C) A (B C) (в) U I U U I Доказанные включения (а) и (в) равносильны равенству 7.

Доказательства остальных равенств 1 - 15 предлагается проделать самостоятельно.

Мы будем считать допустимыми следующие способы образования множеств:

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

2. Если имеется совокупность множеств, то можно получить новое множество, являющееся объединением множеств этой совокупности.

3. Для каждого конечного множества можно образовать множество всех его подмножеств.

4. Для любой пары множеств можно образовать новое множество, являющееся их прямым произведением.

Известно, что неограниченное использование средств при построении множеств приводит к логическим парадоксам (парадокс Рассела, парадокс Кантора и др.).

В данном курсе будут применяться только конструкции конечного типа над конечными множествами.

Упражнения 1. Пусть A1, Е, An, B - подмножества некоторого фиксированного множества E.

Доказать равенства:

n n а) ( Ai ) B = (Ai B) U I U I i=1 i=n n в) ( Ai ) B = (Ai B) I U I U i=1 i=n n c) Ai = Ai U I i=1 i=n n d) Ai = Ai I U i=1 i=2. Для произвольных множеств А и B положим A B = (A B) (A B) I U I Доказать равенства:

a) A B = B A b) (A B) C = A (B C) c) A = A d) A A = e) A (B C) = (A B) (A C) I I I f) A = B A B = 3. Доказать равенства:

a) (A B) C = (A C) (B C) U U b) (A B) C = (A C) (B C) I I c) (A B) (C D) = (A C) (B D) I I I 4. Установить биективное соответствие между множеством всех отображений множества А в двухэлементное множество {0, 1} и булеаном множества А.

5. Пусть F: X Y, A X, B X Доказать:

a) A B F(A) F(B) b) FA B) = FA) FB) ( ( ( U U c) FA B) FA) FB) ( ( ( I I причем возможно и строгое включение.

d) FA B) = FA) FB) для любых подмножеств А и B тогда и только тогда, ( ( ( I I когда F - инъективно.

з 2. Принципы перечисления и примеры.

Элементарные тождества.

При решении перечисленных задач теории множеств широко используются следующие правила для подсчета.

1. Правило равенства. Если A и B - конечные множества и существует биективное отображение F: A B, то A = B 2. Правило суммы. Если A1, Е, An - конечные, попарно непересекающиеся множества, то A1... An = A1 +...+ An U U 3. Правило произведения. Если A1, Е, An - конечные множества, то A...A = A... A.

1 n 1 n Применим данные принципы для решения перечисленных задач, связанных с введенными объектами.

1. Число отображения n-множества в m-множество. Пусть A = {a1, Е, an } и B = {b1, Е, bm}. Тогда любое отображение F: A B можно задать набором длины n вида (F(a1), Е, F(an)) элементов из множества B. При этом разные наборы такого вида определяют разные отображения, и разные отображения дают разные наборы. Значит, имеется биективное отображение между множеством всех отображений F: A B и множеством B Е B(n раз). Следовательно, число отображений F: A B дается формулой A n B = m Если нас интересует число частичных отображений из A в B, то нетрудно заметить, что оно дается формулой A (1 + B) = (1 + m)n 2. Число инъективных отображений n-множества в m-множество. Любое инъективное отображение F: A B однозначно задается набором длины n из элементов множества B вида (F(a1), Е, F(an)), где F(ai) F(aj) при i j. Элемент F(a1) может принимать B значений, при фиксированном F(a1) элемент F(a2) может принимать B - 1 значений и т.д. Следовательно, число инъективных отображений F: A B равно B( B -1) ( B - A +1) = m(m -1) (m - n +1) Следствие. Число подстановок n-множества А равно n! = n(n-1) Е 21.

3. Число k-элементных подмножеств n-множества. Пусть А = {a1, Е, an} и требуется найти число подмножеств B A с условием B = k, где 0 k n. Обозначим чеn рез - искомое число, и пусть B1, Е, B n - все k-элементные подмножества А. Каж k k дому Bi можно поставить в соответствие k! (по числу биекций Bi на себя) инъективных 1 2 k отображений F: Nk A, положив F:, где Nk = {1, 2, Е, k}, a ai2 aik in Bi = {ai,...,ai }. Таким образом, всем k-элементным подмножествам А будет по 1 k k n ставлено в соответствие * k! инъективных отображений. Ясно, что различные под k множества Bi дают попарно различные инъективные отображения F: Nk A, и каждое инъективное отображение F: Nk A может быть получено указанным образом. Значит, n число инъективных отображений F: Nk A равно числу * k!, т.е.

k n n(n-1) Е(n-k+1) = * k! k Отсюда n n(n -1) (n - k +1) n! = = (*) k k! k!(n - k)! n Условимся считать 0! = 1 и тогда = 1.

n n Кроме того, полагаем = 0 при k > n. Тогда функция fn,k = будет определена для k k n всех целых неотрицательных чисел. Числа называются биномиальными коэффици k ентами.

Учитывая важность формулы (*), приведем еще одно доказательство ее. Будем доказывать формулу (*) индукцией по n + k. Для n + k = 1 имеем очевидное утверждение. Пусть даны n, k и пусть формула (*) верна при всех n, k, таких, что n + k < n + k.

Фиксируем элемент a A, где A = n. Разобьем все k-подмножества множества А на два класса:

1. Те, которые содержат элемент a 2. Те, которые не содержат элемента a.

n -В случае 1. имеем подмножеств, и по предположению индукции выполнено k -n - (n -1)! = k -1 (k -1)!(n - k)! n - В случае 2. имеем подмножеств и по предположению индукции выполнено k n - (n -1)! = k (k!)(n - k -1)! Таким образом, общее число k-подмножеств (по правилу суммы) равно n -1 n - (n -1)! (n -1)! (n -1)! 1 + = + = n + = k +1 k (k -1)!(n - k)! k!(n - k -1)! (k -1)!(n - k -1)! - k k n n! = k!(n - k)! k т.е. формула (*) справедлива и для n + k.

4. Число всех подмножеств n-множества. Пусть А - множество из n элементов и B(A) - булеан множества А. Нас интересует число BA). Рассмотрим множество {0,1} и ( установим биективное соответствие между множеством B(A) и множеством всех отображений F: A {0,1}.

Для произвольного подмножества A1 A определим FA : A {0,1}, полагая 1, ес лиa A FA (a) = 0, ес лиa A Ясно, что если A1 A2, то FA FA2 и любому отображению F: A {0,1}соответствует A1 A, где A1 = {a a A и F(a) = 1}. Значит, нужное биективное соответствие установлено и, согласно предыдущему, имеется 2n отображений F: A {0,1}. Отсюда, BA) = 2n.

( Следствие. Справедливо тождество n = 2n n k= k 5. Мультимножества. В ряде случаев приходится рассматривать объекты, в которых элементы множества повторяются. Известный пример - корни алгебраического уравнения. Определим мультимножество над множеством А как пару (A,r) множества А и отображения r: A N0 = {0, 1, Е }, задающего кратность элементов из множества А.

Мощностью мультимножества (A,r) называется число r(a).

aA 1. Число мультимножеств мощности m над n-множеством.

Пусть А = {a1, Е, an}. Тогда число мультимножеств мощности m равно числу отображений r: A N0 с условием r(a1) + r(a2) + Е + r(an) = m Каждому такому отображению r поставим в соответствие набор из элементов 0, 1 вида 12 n r = (0r(a ) 10r(a ) 110r(a )), i где 0r(a ) означает 0, повторенный r(ai) раз. Набор r имеет длину m + n - 1и содержит m нулей и n - 1 единиц. Ясно, что разным отображениям r1 : A N0, r2 : A N0 соответствуют разные наборы r1, r2. Далее, произвольный набор из элементов 0, 1 длины m + n -1, содержащий n - 1единиц определяет отображение r: A N0 с условием r(a) = m, aA если положить r(a1) равным числу нулей до первой единицы слева, r(a2) равным числу нулей между первой и второй единицами слева и т.д. Следовательно, число интересующих отображений r: A N0 равно числу наборов из 0, 1 длины m+ n -1, содержащих n - 1 единиц. Поскольку каждый такой набор однозначно определяется множеством номеров координат, принимающих значение единица, то интересующее нас число равно числу (n-1)-подмножеств (m+n-1)-множества, которое, согласно предыдущему, равно m + n - n -Если нас интересует число невырожденных мультимножеств (A,r) мощности m над nмножеством А, т.е. таких, у которых r(a) > 0 для всех a A, то оно равно m - n -Предоставляется этот факт доказать самостоятельно.

1 2 n Следствие. Число одночленов x1 x2 x полной степени m из кольца многоn членов K[x1, Е, xn] равно m + n - n -2. Число перестановок мультимножеств мощности m. Пусть дано мультимножество (A,r), где А = {a1, Е, an} и r: A N0, причем r(a) = m. Перестановкой мульaA тимножества (A,r) будем называть отображение F: {1, Е, m} A, такое, что F-1(a) = r(a), a A.

Ясно, что любая перестановка F мультимножества однозначно определяется выбором r(ai) элементов из {1, Е, m}, переходящих в ai. Это можно сделать числом способом, равным m m - r(a1) m - r(a1) - - r(an-1) m! = r(a1) r(a2) r(an ) r(a1)! r(an )! 6. Свойства биномиальных коэффициентов и связанные с ними тождества.

В комбинаторных расчетах биномиальные коэффициенты играют важную роль.

Для оперирования с ними полезны следующие формулы.

n n 1. = - свойство симметрии k n - k n n -1 n -2. = + - свойство сложения k k k -n n n -3. = - свойство понижения индексов k k -k n m n n - k 4. = - свойство замены индексов m k k m - k Данные формулы проверяются непосредственной выкладкой.

r r +1 r + n r + n + 5. + + Е + = 0 1 n n Докажем индукцией по n. При n = 1 тождество верно. Пусть оно верно при n.

Тогда для n + 1 имеем r r +1 r + n r + n +1 r + n +1 r + n +1 r + n + + + Е + + = + = 0 1 n n +1 n n +1 n + 0 1 n n + 6. + + Е + = m m m m + Запишем последовательность равенств n n n + + = m +1 m m + n -1 n -1 n + = m +1 m m + Е 0 0 + = m +1 m m + Теперь складываем данные равенства, получаем нужное тождество.

n n n 7. max = k 0kn Рассматриваем отношение n n - k +k = n k k -n n замечаем, что оно больше 1 при k и меньше 1 при k >.

2 8. Пусть p - простое число. Тогда p а) 0(mod p) при 1 k p - k p -б) (-1)k (mod p) при 0 k p - k p p! Число = целое, числа k! и (p - k)! взаимно просты с p, поэтому они сокра k k!(p - k)! щаются с (p - 1)!. Отсюда следует а).

p (p -1 -1)! Рассмотрим теперь =. Ясно, что справедливы соотношения k k!(p -1- k)! p -1 p - 2 p - k -1(mod p), откуда следует б) при k 1. При k = 0 утверждение 1 2 k б) очевидно.

9. Пусть x - некоторое переменное из множества действительных чисел, n - натуральное число. Тогда справедливо n (1 + x)n = xk n k= k Полагая x = 1 и, x = -1, получаем тождества n 9а. = 2n n k= k n 9б. (-1)k = n k= k Рассматривая очевидное тождество (1 + x)n(1 + x)m = (1 + x)n+m (n, m - натуральные числа) и подсчитывая справа и слева коэффициент при xk, 0 k n+m получим тождество Вандермонда:

n m n + m k 10. = i= i k - i k Используя тождества 4, 9а, 9б легко доказываются тождества n n n n -1 n n- p n + +L+ = 2p 11а. 0 p 1 p -1 p 0 p n n n n -1 n n - p p +L+ = 11б. - (-1) 0 p 1 p p -1 n 1 (-1)i-12. = 1 + +L+ n i=2 n i i Рассмотрим тождество n (1 - x)n = (-1)i xi n i= i Перенесем влево член при i = 0 и разделим обе части равенства на x.

n (1- x) -1 n n - = (-1)i xi- i=1 i (1- x) -Это равносильно тождеству n n - [1 + (1 - x) + (1 - x)2 + Е + (1 - x)n-1] = (-1)i xi- i=1 i проинтегрируем обе части по x и получим (1- x)2 (1- x)n n (1 - x) + +L+ + C =n (-1)i i=1 i i xi 2 n Полагая x = 0, находим постоянную интегрирования С:

1 C = - [1 + +L+ ] 2 n Теперь полагаем x = 1 и получаем нужное тождество.

Упражнения.

Доказать тождества n n 2n 1.

i = n i=n n 1 2. = (2n+1 -1) k k +1 n +k=n n 1 3. (-1)k = k k +1 n +k=n n n n n 4. 1 - + - +L= 2 cos 2 4 n n n n n n 5. - + - +L= 2 sin 1 3 5 з 3. Бинарные отношения.

1. Определения.

Пусть дано декартово произведение множеств A1LAn. Подмножество R A1LAn называется n-местным отношением на множествах A1, Е An. Говорят, что элементы a1, Е an находятся в отношении R, если (a1, Е an) R.

Наиболее изучены и часто используются в приложениях двухместные или бинарные отношения. Иногда бинарные отношения R на A1 A2 называют соответствиями из A1 в A2. Для бинарных отношений наряду с записью (a1,a2) R пишут также a1Ra2. Если Ai = A, i 1, n, то говорят, что задано n-местное отношение на множестве А. Далее будут рассматриваться только бинарные отношения.

Если R A1 A2 - бинарное отношение, то можно определить проекции пр1R и пр2R как подмножества A1 и A2 соответственно:

nр1R = {a1 (a1,a2 ) R для некоторого a2 A2 } nр2R = {a2 (a1,a2 ) R для некоторого a1 A1 } Если nр1R = A1, то говорят, что отношение R всюду определено. Если nр2R = A2, то говорят, что отношение R сюръективно. Для задания бинарных отношения можно использовать любые способы задания множеств. Наиболее употребительные способы задания бинарного отношения R на конечном множестве А - матричный и графический. Пусть n-множество А состоит из элементов a1, a2, Е an. Тогда для бинарного отношения R на А определим матрицу DR = (rij), i, j 1, n, где 1, если aiRaj rij = 0, в противном случае.

Матрица DR однозначно определяет бинарное отношение R. При графическом задании отношения R строится граф с множеством вершин a1, Е an на плоскости, причем от вершины ai к вершине aj проводится ориентированная дуга в том и только в том случае, если aiRaj. Построенный таким образом граф однозначно характеризует отношение R.

егко видеть, что отображения являются частным случаем бинарных отношений. Бинарное отношение R на множестве A1 A2 определяет отображение F: A1 A2, если справедливо a1Ra2 и a1 Ra2 a1 = a1.

Pages:     | 1 | 2 | 3 | 4 |   ...   | 12 |    Книги по разным темам