Симметричная разность множеств

Множество всех элементов, принадлежащих либо только множеству А, либо только множеству В называется симметричной разностью множеств А и В Операция симметричной разности обозначается знаком «Å ».

На рисунке 4.5. изображено множество С, являющееся симметричной разностью множеств А и В.  

С=А Å B : (х Î A Å B ) « (( х Î A ) & ( х Ï B )) V (( x Ï A ) & ( x Î B ))

Пример: {1,2,3} Å {2,3,4}={1,4}

Рис. 4.5 С=А Å B

 

3.3. Включения. Подмножество. Пустое множество

Множество А называется подмножеством множества В, если любой элемент из А является элементом множества В. Факт, что А является подмножеством В записывается с помощью « Ì » – знак включения.

Запись A Ì B можно прочитать как «А - подмножество В» или «В включает А» или «В содержит А».

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

Введем понятие строгого включения множества (символ «Í»).

Множество A строго включается во множество В (А является строгим подмножеством В), если любой элемент из А является элементом множества В, и во множестве В содержится по крайней мере один элемент, не принадлежащий А. На рис. 4.6 изображено строгое включение множества А в В.

 

Рис.4.6.

Введем понятие множества всех подмножеств в некотором множестве Х, по-другому называемом множеством-степенью:

P(Х)={U½U Ì C}.

Из основных принципов теории множеств следует существование единственного множества, не имеющего элементов – “Æ” – пустое множество.

Æ={ }

Пустое множество по определению является подмножеством любого множества, причем строгим.

Пример. Дано множество A={a,b,c}. Построить P(А) – множество-степень для множества А.

    P (A)={Æ, {a}, {b}, {c}, {a, b}, {b, c}, {a,c}, {a,b,c}}

Если некоторое множество содержит n элементов, то его степень множества будет содержать 2n  элементов.

3.4. Универсум. Дополнение.

Обычно все множества, с которыми имеют дело в том или ином рассуждении, являются подмножествами некоторого фиксированного множества U. Например, множества рыб, моллюсков, планктона, крабообразных являются подмножествами объемлющего их множества фауны. Это общее множество назовем универсумом.

Универсумили универсальное множество (U) – множество, которое состоит из всех элементов, а также подмножеств множества исследуемых объектов исследуемой области, т.е. универсум должен удовлетворять следующим условиям:

- если А Î U, то А Í U;

- если А Î U, то P(А) Î U, где P(А) – множество всех подмножеств множества А;

- если А Î U и     В Î U, то и {A , B}Î U ;

- если F=(F _i ) _{i Î I}, где F _i Î U и I Î U, то È Fi Î U.

В системе диаграмм Эйлера, универсальное множество U изображается в виде прямоугольника, а множества, являющиеся его подмножествами, - в виде кругов, находящихся внутри прямоугольника U.

Множество Ā= U \ A называют дополнением множества А.

На рис. 4.7 приведено изображение универсального подмножества, множества А и дополнения множества  Ā.

 

 

Рис.4.7

Анализируя рис. 4.7. можно сделать следующие выводы:

A È U=U

A Ç U=A

Ā È A=U

Ā Ç A= Æ                           

_____

 (Ā)=A

                                                                      

AÈÆ=A

AÇÆ=Æ    

3.5. Свойства операций над множествами

Приоритет операций над множествами определяется следующим образом: наивысший приоритет имеет дополнение ( ¯ ), далее в порядке убывания приоритета следуют операция Ç, далее - È. Порядок выполнения операций может быть изменен скобками.

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

Далее приведены основные тождества алгебры множеств:

 

 

Законы де Моргана:

 

 

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

3.6. Декартово произведение множеств

Декартовым (прямым) произведением множеств Х и Y называется множество С, состоящее из упорядоченных пар элементов х и у, (принятое обозначение <х, у>), причем первый элемент принадлежит Х (х Î C ), а второй множеству Y (у Î U ). Формальная запись декартова произведения множеств выглядит следующим образом:

С =Х ´ У      или

С ={<х,у> ½ х Î C & у Î U }

Порядок следования пар в множестве С может быть любым, но расположение элементов в паре строго задано и определяется порядком следования перемножаемых множеств.

Рассмотрим пример формирования элементов множества С, являющегося декартовым произведением множеств Х={a,b,c,d} и Y={a,b}.

C={<a,a>,<a,b >,<b,a>,<b,b>,<c,a>,<c,b>,<d,a>,<d,b>}

 

Декартово произведение для n множеств задается следующим образом:

3.7. Бинарные отношения

Всякое подмножество R декартова произведения множеств X ´ Y, называют отношением, определенным на паре множеств Х и Y. Когда пара (x , y) ÎR, то говорят, что элемент х находится в отношении R к элементу у.

Отношение R может быть задано перечислением всех пар элементов <x , y>, входящих в данное отношение, или некоторым свойством, выражаемом в виде формулы исчисления предикатов с двумя свободными переменными х и у.

R={<x,y>½F(x,y)}.

Например, определим на множестве натуральных чисел N отношение «больше».

R= {<n1 Î N, n2 Î N>½n1>n2}.

При этом пара чисел (5, 3) удовлетворяет отношению R, а пара (3, 5) не удовлетворяет отношению R.

B теории бинарных отношений часто используются другие формальные способы записи того же самого:

х R y     (5 «больше» 3)

 «Больше» Ì <числовое множество>´<числовое множество> .

 

Способы задания отношений

1) Табличный способ задания отношения

R Ì x * y, x R y

Если < x _i, y i>ÎR, то на пересечении x _i и y _i  ставится некоторый символ.

 

         

	у1	у2	у3	у4	у5
х1	Ÿ
х2			Ÿ	Ÿ
х3		Ÿ
х4				Ÿ
х5		Ÿ	Ÿ
х6
х7		Ÿ

 

2) Матричный способ задания отношения

Отношение R Ì x * y, x _i R y _i задается матрицей М, строки которой задаются элементами множества X, а столбцы – элементами множества Y.

M=êêm ij êêm ´ n – матрица отношения

 

Например, зададим матричным способом отношение, заданное выше табличным способом:

 

3) Графический способ задания отношения

Если пара < x i, y i>ÎR, то вершина x i соединяется стрелкой с y i . Такая картинка называется граф-отношение. Это двудольный ориентированный граф.

 

4) Способ задания отношения с помощью сечений

Рассмотрим отношение R Ì x * y. Если x i Î X, то сечением отношения R по элементу x i называется множество элементов y Î Y таких, что < x i, y i>ÎR.

 

R(x i )= {y i / y i Î Y & < x i , y i > Î R}

 

Множество сечений отношения R по всем элементам х из множества X называется фактор - множеством множестваY по отношению R и обозначают Y/ R. Оно полностью определяет отношение R.

Форма записи фактор - множества:

        

Принят следующий факт: если для некоторого элемента xp сечение множества R ( x p ) =Æ, то x p и R ( x p ) в Y по R не включают.

Пример. На множествах X = { x ₁ , x ₂ , x ₃ , x ₄ , x ₅ } и Y = { y ₁ , y ₂ , y ₃ , y ₄ } задано отношение:

R = { < x 1, y 1 > , < x 1, y 3 > , < x 2, y 1 > , < x 2, y 3 > , < x 2, y 4 > , < x 3, y 1 > , < x 3, y 2 > , < x 3, y 4 > , < x 4, y 3 > , < x 5, y 2 > , < x 5, y 4 > , }

Определить фактор-множествоY / R.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: