Тема 12. Элементы теории множеств. Комбинаторика

Учебные вопросы:

Понятие множества. Подмножества. Пустое множество. Универсальное множество. Диаграммы Эйлера-Венна. Равенство множеств. Пересечение, объединение, разность множеств. Дополнение множества. Отношения на множестве. Бинарные отношения. Рефлективность. Симметричность. Транзитивность. Отношение порядка. Алгебраическая операция.

Понятие комбинаторики. Правила суммы и произведения. Комбинация. Кортеж. Размещения. Перестановки. Сочетания.

Рекомендуемая литература:

1. Баврин, И. И. Высшая математика: Учеб. пособие для студентов хим.-биол. спец. пед. вузов / И. И. Баврин.­– 2-е изд., перераб.– М.: Просвещение, 1993.

2. Дотворский, А. С. Пособия по математике для студентов факультетов начальных классов / А. С. Дотворский, Л. П. Ковригина, В. А. Ситаров, И. В. Шадрина, А. Л. Чепин.– М.: «Прометей»; Изд-во Моск. гос. пед. ин-та им. В. И. Ленина, 1989.

3. Математика: Большой энцикл. словарь / Гл. ред. Ю. В. Прохоров.– 3-е изд.– М.: Большая рос. энцикл., 1998.

Понятие множества. Подмножества

Под множеством понимают объединение в одно целое объектов, связанных между собой неким свойством. Термин «множество» в математике не всегда обозначает большое количество предметов, оно может состоять и из одного элемента и вообще не содержать элементов, тогда его называют пустым и обозначают Æ.

Множество B называют подмножеством множества А, если любой элемент множества В является элементом множества А. Обозначается В Ì А (рис.1).

 

 

Свойства включения множеств:

1. Пустое множество является подмножеством любого множества: Æ Ì А.

2. Любое множество является подмножеством самого себя, т. е. для любого множества А справедливо включение А Ì А.

3. Если А – подмножество множества В, а В – подмножество множества С, то А – подмножество множества С. (рис.2)

Универсальное множество – это самое большее множество, содержащее в себе все множества, рассматриваемые в данной задаче.

На диаграмме Эйлера – Венна универсальное множество обозначают в виде прямоугольника и буквы U:

Операции над множествами

Равными называются множества, состоящие из одних и тех же элементов.

Два множества равны,если каждое из них является подмножеством другого (A = B Û(A Ì B и В Ì А)).

Множества не равны,если хотя бы в одном множестве существует хотя бы один элемент, не принадлежащий другому множеству.

Объединением множеств А и В называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств А или В. Обозначается A B.

Отметим разницу в употреблении союза «или» в математике и в обыденной речи. В обыденной речи союз «или» употребляется чаще в разделительном смысле – «либо… либо», тогда как в математике – в объединительном. 

Свойства объединения множеств:

1.

2.

3.

4.

5.

6.

Пересечением множеств А и В называется множество, состоящее из всех элементов, принадлежащих обоим множествам А и В. Обозначается А Ç В.

АÇВ = Æ   АÇВ

Свойства пересечения множеств:

1.

2.

3.

4.

5.

6.

Разностьюмножеств А и В называется множество элементов, принадлежащих множеству А, которые не принадлежат множеству В. Обозначается А \ В.

 

Свойства разности множеств:

1. Если  то А \ В = А.

2. Если А Ì В, то А \ В = Æ.

3. А \ В = А \ (А   В).

Разность между универсальным множеством U и множеством А называется дополнением множества А. Обозначается = U \ A.

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

1. 2. 3.   4. 5. 6. 7.

8.  если . 9. . 10. . 11. ,  если 12. .

Отношения на множестве

При задании множества порядок следования элементов не важен, при этом предполагается, что один и тот же элемент не может входить в множество дважды. Часто приходится сталкиваться с последовательностями. Последовательность, первым элементом которой является х ₁, а вторым – х ₂, называется упорядоченной парой, а элементы – координаты; последовательность из трех элементов называется упорядоченной тройкой и т.д.; последовательность из n элементов – упорядоченной n- кой элементов, или кортежем.

Пусть задан набор множеств А ₁, А ₂,..., А _n. Декартовым произведением множеств А ₁, А ₂,..., А _n (обозначается как А ₁´ А ₂´...´ А _n) называется множество кортежей (х ₁, х ₂,..., х _n) длины n, таких что, х ₁ Î А ₁, х ₂ Î А ₂,..., х _n Î А _n.

Отношением называется некоторое подмножество декартового произведения одного или более множеств.

Бинарным отношением на множестве A называется упорядоченная пара (A, S)множеств A и S, где S есть часть множества А ´ А. Множество S бинарного отношения (A, S) называется графиком этого отношения.

Обычно бинарное отношение обозначают какой-либо буквой, например R, а принадлежность кортежа (а, b) отношению R – aRb.

Отношение называется симметричным, если одновременно с каждым кортежем (а, b) ему принадлежит также и кортеж (b, а). Например, отношение параллельности – симметрично, а отношение < – несимметрично, отношение ³ – антисимметрично, т.к. это отношение x ³ y является симметричным только при x = y.

Отношение называется рефлексивным, если ему принадлежат все кортежи вида (а, а). Например, отношение параллельности – рефлексивно, а отношение перпендикулярности – нерефлексивно.

Отношение называется транзитивным, если вместе с кортежами (а, b) и (b, с) ему принадлежат также и кортеж (а, с).

Симметричное, рефлексивное и транзитивное отношение называется отношением эквивалентности.

Примеры отношений эквивалентности:

1. Равенство в произвольной системе множества.

2. Отношения подобия треугольников в евклидовой плоскости.

3. Отношение параллельности прямых в евклидовой плоскости.

Бинарное отношение называется отношением порядка, если оно обладает следующими свойствами:

1) отношение транзитивно;

2) никакие 2 различных кортежа (а, b) и (b, а), не принадлежат одновременно этому отношению;

3) никакой кортеж вида (а, а) не принадлежит этому отношению;

4) один из двух различных кортежей (а, b) и (b, а) всегда принадлежат этому отношению.

Существуют 2 вида отношений порядка:

Отношение строгого порядка – нерефлексивно, несимметрично, транзитивно.

Отношение нестрогого порядка – рефлексивно, антисимметрично, транзитивно.

Отображением (функцией) называют тройку множеств (A, B, S), где S есть множество кортежей из A ´ B таких, что всякий элемент из А является первым элементом в точности одного кортежа из S.

Множество А называют областью определения отображения, множество В – областью значений, S – графиком.

Функция * называется бинарной алгебраической операцией  на множестве А, если область определения является А ´ А, а область значения А.

Пусть на множестве M определена алгебраическая операция *:

1. Операция * называется коммутативной, если для всех а, b ÎM выполняется: а * b= b * а.

2. Операция * называется ассоциативной, если для всех а, b, с Î M выполняется: а *(b * с) = (а * b)* с.

3. На множестве M определена обратная операция, если однозначно разрешимы уравнения а * x= b и y * а= b для всех а, b Î M. В том случае, когда операция * коммутативна, эти решения совпадают.

4. Элемент е Î M называется нейтральным, если а * е = е * а = а, для всех а Î M.

5. Элемент а’ называется симметричным элементу  а Î M, если а * а’ = a’ * а = е.