Общие понятия о множествах. Объединение пересечение, диаграммы Венна
Множеством - называется совокупность определенных вполне различаемых объектов, рассматриваемых как единое \целое.
Отдельные объекты, из которых состоит множество, называются элементами множества.
Множества принято обозначать большими буквами латинского алфавита, а элементы этих множеств — маленькими буквами латинского алфавита. Множества записываются в фигурных скобках { }.
Множества бывают конечные и бесконечные. Множества называются конечным, если число его элементов конечно, т.е. если существует натуральное число n, являющееся числом элементов множества. А={a1, a2,a 3,..., an}. Множество называется бесконечным, если оно содержит бесконечное число элементов. B={b1,b2,b3,...}. Например, множество букв русского алфавита — конечное множество. Множество натуральных чисел — бесконечное множество.
Билет
Теоремы сложения и умножения
Теорема 1 (принцип сложения). Пусть A 
B = 
. Тогда n(A 
B) = n(A) + n(B).
Следствие 2. Пусть A1, A2 …. Al – система попарно непересекающихся конечных множеств.
Тогда n(A1 A2 … Al) = n(A1)+n(A2)+…+n(Al).
Доказательство. При l=2 мы ссылаемся на теорему 1:
n(A1 A2) = n(A1) + n(A2).
Допустим, что утверждение верно при l = k, то есть
n(A1 A2 … Ak) = n(A1) + n(A2) + … + n(Ak).
Докажем утверждение при l = k+1. В этом случае
n(A1 A2 … Ak Ak+1) = n((A1 A2 … Ak) Ak+1) = n(A1 A2 … Ak) + n(Ak+1). Здесь мы воспользовались базисом индукции и, применяя индуктивное предположение, получим:
n(A1 A2 … Ak) + n(Ak+1) = n(A1) + … + n(Ak) + n(Ak+1).
Следствие доказано.
Иногда принцип сложения, применительно к задачам комбинаторики, можно встретить в таком виде: если объект x можно получить m способами, а объект y можно получить l способами, причем множества этих способов не пересекаются, то объект x или объект y можно получить m + l способами. Таким образом, необходимо помнить, что в комбинаторике союз “или” ассоциирован с операцией сложения.
Теорема 3 (принцип умножения). Если множество A состоит из m элементов, а множество B состоит из l элементов, то n(A 
B) =ml.
Доказательство. Будем доказывать методом математической индукции по l. При l=1 множество B состоит из одного элемента: B={b1}. Поэтому множество A B={(ai, b1)|i =1, 2,…, m} состоит из m элементов, то есть n(A B)=m · 1=m · l. Базис индукции проверен.
Допустим, утверждение верно при l = k, то есть, если n(A) = m, n(B) = k, то n(A B) = m · k. Докажем утверждение при l = k + 1. Пусть B = {b1, b2 ,…, bk, bk+1} или B = B' {bk+1}, где множество B' = {b1, b2 ,…, bk} состоит из k элементов. По индуктивному предположению n(A B') = n(A) · n(B') = m · k. С другой стороны
B = B' {bk+1}, поэтому (A B) = A B' A {bk+1}, причем
A B' A {bk+1} = , так как B' {bk+1} = . По теореме 1 n(A B) = n(A B' A {bk+1}) = n(A B') + n(A {bk+1})= =m · k + m · 1 = m(k + 1) = m · l. Теорема доказана.
В комбинаторном изложении принцип умножения часто формулируют так: если объект x можно сконструировать m способами, объект y можно сконструировать l способами, то объект (x, y) или (x и y) можно сконструировать m · l способами. То есть союз “и” в комбинаторики ассоциирован с операцией умножения.
Билет
