yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->1.3  Операции над множествами

Дискретная математика

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

 

1.Объединение множеств: A U B = { а ¦ а ї A или а ї B}.

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

D = A U B = { x ¦, x ї А или x ї В }

Операция  "объединение"  n-арная  (т.е.  применима  к  n  множествам), коммутативная (при перестановке  объединяемых  множеств результат не изменяется).

 

Пример: A = {a,ab,ac,c}; B = {ac,ba,b,c}; C = {b,f}

D = A U B U C =  C U B U A = {a,ab,ac,c,ba,b,f}.

 

2.Пересечение множеств:

Пересечением множеств называется множество, состоящее из  всех элементов, принадлежащих  одновременно  каждому  из  объединяемых множеств.

A П B = { x ¦ x ї A  и  x ї B }

Операция  "пересечение"  n-арная  (т.е.  применима  к  n  мно-

жествам), коммутативная (при перестановке  пересекаемых  множеств

результат не изменяется).

 

Пример:   A = {a,b,c,f};  B = {b,c,n};   C = {d,f,n};

D = A П B = {b,c};  B П C = { n };

Е = A П B П C = B П C П A = { }.

- 6 -

3.Разность множеств:

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

A \ B = { а ¦ а ї A  и  а не ї В }.

Операция "разность"  бинарная  (т.е.  применима  к  двум  множествам), некоммутативная (при перестановке  вычитаемых  множеств результат изменяется):  A \ B  не равно  B \ A.

 

Пример:   A = {a,c,d,e,f};  B = {a,d,m};

D = A \ B = {c,e,f}; C = B \ A = { m }.

 

4.Дополнение множества:

Дополнением множества А (до универсального множества W ) называется множество, состоящее из всех элементов множества W,  которые не входят в множество А.

_

А = { a ¦ a ї W  и  не ї A }.

Операция "дополнение" унарная (т.е. применима  к  одному  множеству или части формулы, которую можно трактовать как одно  множество).                                                        _

Операцию "разность" в формулах можно заменить: A \ B = A  П  B.

_

Пример: W = {a,c,d,e,f,k};  B = {a,d,k}; B = {c,e,f}; A = {a,c};

_             _

В U B = W;    В П B = { } (пусто);

_

D = A \ B = A П B = { c }.

 

Используя множества, операции 1-4 и скобки, которые меняют порядок выполнения операций, можно составлять  формулы  (наибольший приоритет при выполнении имеет операция "дополнение", затем "разность" и затем две операции одного приоритета -  "объединение"  и"пересечение"; операции одного приоритета выполняются  в  формуле попорядку слева направо; если в формуле есть скобки,  то  сначала выполняются операции в скобках в соответствии с  их  приоритетом; если знак дополнения стоит над частью формулы,  то  считают,  что эта часть взята в скобки (хотя скобки на самом деле отсутствуют))В задачах контрольных работ в формулах используются только три подмножества: А, В, С или P, Q, R универсального множества W).

Очень удобным является наглядное представление таких формул  с помощью диаграмм  Венна.  Диаграмма  в  общем  виде  -  это  прямоугольник, представляющий универсальное множество W с тремя  пересекающимися окружностями внутри; область, заключенная в  каждой окружности, представляет соответственно множества А, В, С.  В результате таких построений площадь прямоугольника  разбивается  (в самом общем случае) на восемь связных областей, каждая из которых или произвольная их комбинация  может  быть  описана  бесконечным множеством формул.

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

 

5.Прямое произведение множеств:

Прямым или декартовым произведением множеств называется  множество, элементами которого  являются  векторы,  составленные  из элементов перемножаемых множеств: первые  компоненты  векторов элементы первого множества, вторые - второго и т.д. Для двух множеств процедура имеет вид:A х В = {(а,b)¦a ї A и b ї B}.

Пример:  A = {a,b,c,.....,h}; B = {1,2,3,.....,8};

D = A х B = {(a,1); (a,2); (a,3);... (h,8)}.

Допускается запись  D = A х B = {a1; a2; a3;... h8}.

Вектор - упорядоченный набор  элементов.  Элементы  образующие вектор называются координатами или  компонентами  вектора.  Число координат называется длиной или размерностью вектора.  В  отличие от элементов множества координаты вектора могут быть одинаковыми. Пример:  B = (0,3,5,3) - вектор размерности 4;

С = (0,3,3,5) - вектор размерности 4.

Векторы В и С различны, т.к. порядок следования координат разный.

Операция 5 также многоместна (перемножить можно несколько множеств). В качестве сомножителей может выступать одно и то же множество, т.е. множество можно возводить в n-ю степень.В качестве примера рассмотрим случай,  когда  элементами  множества являются символы, например V =  {a,b,c}.  Такое  множество будем называть алфавитом.  При возведении этого множества в квадрат получим новое множество, состоящее из двухсимвольных  цепочек или слов (элементы - векторы записываются  без  скобок  и  разделяющих запятых) V^2 = V x V = {aa, ab, ac, ba,..., cc}.  При возведении алфавита в куб (последнее множество умножаем на V)  получаем трехсимвольные слова-цепочки и т.д. Алфавит в нулевой степени представляет собой множество, состоящее из одного  элемента - 8 -пустой цепочки (обозначение @ - эпсилон): V^0 = { @ } Длина цепочки равна количеству элементов, образующих эту цепочку. Пустую цепочку @ - можно вставлять в любое место других цепчек не изменяя этих цепочек.

¦ а ¦ = 1; ¦ aba ¦ = 3; ¦ ab@a ¦ = 3;  ¦ @ ¦ = 0.

 

 

6