Теоремы сложения и умножения

Общие понятия о множествах. Объединение пересечение, диаграммы Венна

Множеством - называется совокупность определенных вполне различаемых объектов, рассматриваемых как единое \целое.
Отдельные объекты, из которых состоит множество, называются элементами множества.
Множества принято обозначать большими буквами латинского алфавита, а элементы этих множеств — маленькими буквами латинского алфавита. Множества записываются в фигурных скобках { }.
Множества бывают конечные и бесконечные. Множества называются конечным, если число его элементов конечно, т.е. если существует натуральное число 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 способами. То есть союз “и” в комбинаторики ассоциирован с операцией умножения.

 

Билет