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

Некоторые сведения из теории множеств

КОМБИНАТОРИКА

Множество – любое собрание объектов, определённых и хорошо различимых нашей интуицией или интеллектом, мыслимое как единое целое (Георг Кантор, 1872 г.).

Множества обозначаются большими буквами, элементы множества – малыми.

Принадлежность. Если x принадлежит множеству S (x является элементом S), то это обозначается x Î S. Если x не принадлежит S – x Ï S.

Пример: S ={ a,b,c }, a Î S, b Î S, c Î S, d Ï S.

Подмножество. Отношение включения. Если все элементы множества А принадлежат множеству B, то А – подмножество множества B. Это обозначается так: А Í B (А не строго включается в B). Если при этом в B есть элементы, не принадлежащие А, то это обозначают А Ì B (А строго включается в B; A – собственное подмножество B).

Универсальное множество – множество всех элементов какого-либо определённого типа.

Пустое множество (Æ) – множество, не содержащее ни одного элемента. По определению, пустое множество является подмножеством любого множества. (" S: ÆÍ S).

Мощность множества. Для конечных множеств мощность –количество элементов во множестве. Мощность множества S обозначается | S |. Например, S ={ a, b, c }, | S |=3.

Множества называются равномощными (эквивалентными), если их мощность равны.

Пусть заданы множества A и B.

Объединение множеств A и B – множество А È В ={ x: x Î A или x Î B } (объединение содержит элементы, которые есть или в A, или в B, или в том и другом множестве). (нарисовать с помощью кругов Эйлера). А È В = B È A.

Пересечение множеств A и B – множество А Ç В ={ x: x Î A и x Î B } (пересечение содержит элементы, которые есть одновременно и в A, и в B. (нарисовать). А Ç В = B Ç A.

Дополнение до универсального множества. Если В – универсальное множество, и А Í В, то дополнение ={ x: x Î B и x Ï A }. (нарисовать).

Произведение множеств A и B – множество A x B ={< x, y >: x Î A, y Î B } (множество всех пар, первый элемент которых принадлежит множеству A, второй элемент – множеству B). Мощность произведения A x B равна произведению мощностей A и B (| A x B|=|A|*|B|). Произведение B x A не равно A x B, но их мощности совпадают (B x A ¹ A x B, но | B x A| = |A x B|).

Пример: A ={ a, b, c }, B ={ c, d }, |A|= 3, |B| =2.

А È В ={ a, b, c, d }, А Ç В ={ c }, A x B ={ <a,c>, <a,d>, <b,c>, <b,d>, <c,c>, <c,d> }, B x A ={ <c,a>, <c,b>, <c,c>, <d,a>, <d,b>, <d,c> }, | A x B| =6, | B x A| =6.

Оператор (функция) – правило, определяющее отображение некоторого множества X в некоторое множество Y. Обозначение: F: X ® Y.

Пример: X ={ a, b, c, d }, Y ={▲, ●, ■}. Возможный вариант функции: f (a)=■, f (b)=●, f (c)=■, f(d) =▲.

X Y a ▲ b ● c ■ d

Дискретное множество – множество, состоящее из изолированных точек (т.е. множество, не имеющее предельных точек). Например, множество натуральных чисел – дискретное множество, а множество действительных чисел – непрерывное множество.

Дискретная математика изучает свойства дискретных множеств и определённых на них операторов. Непрерывными множествами занимается математический анализ.

Дата добавления: 2014-01-05