Федоров В.Н. - Введение в теорию множеств (1023557), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

а пересечение некоторого числа множеств обозначают так

В первом варианте объединяются или пересекаются множества, принадлежащие универсальному множеству U.

Во втором варианте объединяются или пересекаютcя множества A₁, A₂, A₃,…, A_n.

В третьем варианте объединяется или пересекаетcя бесконечное число множеств A₁, A₂, A₃,…

В четвертом варианте объединяются или пересекаютcя множества, индекс которых принадлежит счетному множеству I.

Разностью множеств А и В (обозначается А\В) называется множество всех тех и только тех элементов А, которые не содержатся в В (рис. 1.4):

А\В= {x: и }.

Разность – операция строго двуместная и некоммутативная:

в общем случае А\В В\А.

С
имметрическая разность множеств А и В (обозначается А B) называется множество всех тех элементов А или B , которые не содержатся в A и В одновременно (рис. 1.5):

А В= {x: или , но }.

Рисунок 1.5

Для этой операции можно записать

.

Прямое (декартово) произведение множеств X₁, X₂,…, X_n - это множество элементов вида

( ), где

Обозначается оно так

{( )| }.

Элементы ( ) называются кортежами, (векторами, наборами, словами). Количество множеств n, участвующих в произведении, определяет длину кортежей.

Произведение множеств – операция некоммутативная:

.

Пусть U – универсальное множество такое, что все рассматриваемые множества являются его подмножествами.

Дополнением (до U) множества А (обозначается ) называется множество всех элементов, не принадлежащих A, но принадлежащих U (рис. 1.6):

=U \ A.

Рисунок 1.6

Операции объединения, пересечения, дополнения { } часто называют булевыми операциями над множествами.

Пример 1. Пусть универсальное множество U – множество всех сотрудников некоторой фирмы; А – множество всех сотрудников данной организации старше 35 лет; В – множество сотрудников, имеющих стаж работы более 10 лет; С – множество менеджеров фирмы. Каков содержательный смысл (характеристическое свойство) каждого из следующих множеств:

а) ; б) ; в) ; г) В \ С; д)С \ B?

• а) – множество сотрудников организации, стаж работы которых не превышает 10 лет.

б) – множество менеджеров фирмы не старше 35 лет, имеющих стаж работы более 10 лет.

в) – множество всех сотрудников фирмы старше 35 лет, а также сотрудников, не являющихся менеджерами, стаж работы которых более 10 лет.

г) В \ С – множество сотрудников организации со стажем работы более 10 лет, не работающих менеджерами.

д) С \ В – множество менеджеров со стажем работы не более 10 лет.

Пример 2. Задать множества , , если:

М– множество всех натуральных чисел, не превосходящих 100;

N– множество натуральных чисел.

• – множество всех натуральных чисел, больших 100.

Запись без контекста (т.е. без указания универсального множества U) не ясна:

• то ли это множество всех отрицательных целых чисел;

• то ли это множество положительных дробных чисел;

• то ли это пустое множество натуральных чисел.

Пример 3. Осуществить операции объединения, пересечения, разности и дополнения над множествами

А = {a, b, c, d} и B = {с, d, e, f, g, h}.

• = {a, b, c, d, e, f, g, h};

= {c, d}.

A \ B = {a, b};

B \ A = {e, f, g, h}.

Универсальное множество U не определено, поэтому, строго говоря, операции дополнения над множествами A и В не могут быть выполнены. Дополним условие задачи. Пусть U ={а, b, с, d, e, f, g, h}, тогда

= U \ А = {е, f, g, h}, ={а, b}.

Пример 4. Пусть U = {1, 2, 3, 4}, А = {1, 3, 4}, В = {2, 3}, С ={1, 4}.

Найти:

a) ; б) ; в) ; г) .

• a) = = ({1, 2, 3, 4} \ {1, 3, 4}) ({1,2, 3, 4} \ {2, 3}) = {2} {1, 4}= {1, 2, 4}.

б) = = {1, 2, 3, 4}\({1, 3, 4} {2, 3}) = {1, 2, 3, 4}\{3} =

{1, 2, 4}.

в) = ={l, 3, 4} ({l, 2, 3, 4}\{2, 3}) ={1, 3, 4} {1, 4} = {1, 4}.

г) = ({2, 3}\{1, 3, 4}) ({1, 2, 3, 4}\{1, 4}) ={2} {2, 3} = {2, 3}.

Пример 5. Получить прямое произведение множеств

X = {a, b} и Y = {p, q, r}.

• X Y = {(a, p),(a, q),(a, r),(b, p),(b, q),(b, r)} .

1.3. Диаграммы Эйлера–Венна

Диаграммы Эйлера–Венна — геометрические представления множеств. Построение диаграммы заключается в изображении большого прямоугольника, представляющего универсальное множество U, а внутри его – кругов (или каких–нибудь других замкнутых фигур), представляющих множества. Круги могут пересекаться в случае, требуемом в задаче, и должны быть соответствующим образом обозначены. Точки, лежащие внутри различных областей диаграммы, могут рассматриваться как элементы соответствующих множеств. Имея построенную диаграмму, можно заштриховать определенные области для обозначения вновь образованных множеств.

Приведенные на рис. 1.2 – 1.6 иллюстрации операций объединения, пересечения, обычной и симметрической разности двух множеств и дополнения являются диаграммами Эйлера–Венна.

Пример 1. Представить множество диаграммой Эйлера–Венна.

• Начнем с общей диаграммы, показанной на рис. 1.7,а. Прямоугольник – универсальное множество U. Круги – множества A, B, C.

Р
исунок 1.7

Заштрихуем В диагональными линиями в одном направлении, а – в другом (рис. 1.7,б). Площадь с двойной штриховкой представляет собой их пересечение, т.е. множество .

Выделим это множество цветом. На новой копии диаграммы заштрихуем эту область линиями одного направления, a A — другого. Вся заштрихованная на рис. 1.7,в область представляет объединение множеств А и , т.е. множество .

Выделим искомую область цветом.

Пример 2. Проиллюстрировать на конкретных множествах и с помощью диаграммы Эйлера–Венна справедливость соотношения

.

Это свойство дистрибутивности слева операции пересечения относительно объединения .

• Пусть U = {а, b, с, d, e}.

А = {а, b}, В = {а, с, d}, С = {b, с, d, e}.

Тогда левая часть равенства

= {a, b} ({а, с, d} {b, с, d, e}) = {a, b} {а, b, с, d, е}= {а, b};

правая часть равенства

=({a, b} {а, с, d}) ({a, b} {b, с, d, e}) = {a} {b} = {a, b}.

Таким образом, левая и правая части соотношения совпадают, т.е. равенство подтверждено.

Построим теперь диаграммы Эйлера–Венна. Левая часть равенства представлена на рис. 1.8,а, правая – на рис. 1.8,б. Из диаграмм очевидно равенство левой и правой частей иллюстрируемого соотношения.

Р
исунок 1.8

1.4. Законы и тождества алгебры множеств

Коммутативный закон для объединения и пересечения

1) X Y = Y X; 2) X Y = Y X.

Ассоциативный закон для объединения и пересечения

3) (X Y) Z = X (Y Z); 4) (X Y) Z = X (Y Z).

Дистрибутивный закон для объединения и пересечения

1. (X Y) Z = (X Z) ( Y Z);

2. (X Y) Z = (X Z) (Y Z).

Дистрибутивный закон пересечения относительно разности

1. .

Дистрибутивный закон пересечения относительно симметрической разности

1. .

Дистрибутивный закон разности относительно пересечения

9)

Дистрибутивный закон разности относительно объединения

10)

11) X X = X; 12) X X = X;

13) X = X; 14) X = ;

15) = U; 16) = ;

17) X\ = ; 18) \X = ;

19) X U = U; 20) X U = X;

21) X = U; 22) X = ;

23) 24)

25) U\X = 26) X\Y =

27) X\(Y Z) = (X\Y) (X\Z) ; 28) X\(Y Z) = (X\Y) (X\Z);

29) X\(X\Z) = X Z; 30) (X\Y) (X Y) = ;

31) = X; 32) X Y= (X\Y) (Y\X) (X Y).

Определенный интерес представляют и следующие операции:

Склеивание

33)

Поглощение

34)

Все эти равенства доказываются так, как показано в п. 1.6.

1.5. Семейства множеств

Пусть дано множество U (конечное или бесконечное) и из элементов этого множества образована некоторая совокупность множеств X_a., называемая семейством множеств. Для семейства множеств справедливо

Если C = U, то имеем полное семейство.

Если C = U и , то совокупность множеств X_a образует систему классов эквивалентности (см. п. 3.3).

Над множествами, принадлежащими семействам, можно выполнять операции объединения и пересечения по обычным правилам

Здесь Y – некоторое множество, элементы которого принадлежат множеству U.

Операция разности – бинарная, поэтому для семейств множеств она выполняется по следующим правилам

Пусть дано семейство множеств А₁, А₂,…, А_n и пусть требуется определить мощность их объединения А₁ А₂ … А_n.

В первом приближении можно принять за эту мощность сумму мощностей множеств семейства

.

однако, если пересечение, хотя бы для одной пары множеств, не пусто

А_i А_{j ,}

то принадлежащие этому пересечению элементы будут учтены дважды.

Исключение “лишних” элементов производится на основе принципа включений и исключений по формуле

По этой формуле для двух множеств получаем

Для трех множеств будем иметь

1.6. Доказательства

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

Наиболее часто в теории множеств используется доказательство равенства соотношений типа Х = Y.

Собственно доказательство можно проводить путем рассуждений с применением законов и тождеств алгебры множеств, построением диаграмм Эйлера–Венна или на примерах множеств, составленных из алфавитно–цифровых символов (последние два способа приведены в примере 2 п.1.3).

Ниже, в Примерах доказательства соотношений типа X = Y, где Х и Y – множества, основаны на использовании определений I и II равенства двух множеств.

Характеристики

Список файлов книги