1. Лабораторная работа № 1 Операции над множествами

   1. Цель работы: Изучить основные операции над множествами: объединение, пересечение, разность, дополнение.

   2. Теоретические сведения

В математике понятие “множество” является исходным и не подлежит точному определению. Поэтому набор или совокупность каких-либо объектов, обладающих общими свойствами, на интуитивном уровне, называют множеством. Например, в математике такими множествами являются множество целых чисел Z (INTEGER), множество вещественных чисел R (REAL) и др. “Нематематические” объекты также формируют множества. Объекты, включаемые в множество, называют его элементами

Общим обозначением множества служит пара фигурных скобок {, }, между которыми перечисляют все элементы множества или указывают свойства, которыми должны обладать элементы формируемого множества. Для обозначения множества в тексте используют прописные буквы латинского алфавита A, B, C, ...X, Y, Z. Для обозначения элементов множества в тексте используют строчные буквы латинского алфавита a, b, c,...x, y, z.

Для обозначения принадлежности элемента x множеству X используют знак ““ - знакпринадлежности, т.е. xX. Если элемент х не принадлежит множеству Х, то используют знак ““, т.е. хХ.

Число элементов счетного конечного множества Х называют его мощностьюи обозначают так: |X|=n.

Если всякий элемент множества Х является также элементом другого множества Y, то множествоXназываютподмножествоммножества Y. Для обозначения этого в тексте используют знак ““ - знак включения, т.е. ХY. Если множество Х не включено в множество Y, т.е. не все его элементы принадлежат Y, то используют знак ““ - знак невключения, т.е. XY.

Если XY и YX, то X=Y.

Если XYи XY, то множество Х называютсобственным подмножествоммножества Y. Для указания в тексте этого факта используют знак строгого включения - ““, т.е. XY.

Множество, не содержащее ни одного элемента, называют пустыммножеством и обозначают знаком, т.е.={ }. Пустое множество может быть подмножеством любого множества.

Множество, содержащее все элементы всех подмножеств, принимающих участие в решении какой-либо задачи, называют основным или универсальныммножеством и обозначают символомU, т.е. если в решении какой-либо задачи принимают участие множества А={a} и B={b,c}, тоU={a,b,c}.

Максимально возможное число подмножеств универсального множества называют семейством подмножеств универсального множества. Это семейство включает пустое подмножество, само универсальное множество и множества, сформированные по одному, два, три и т.д., элементов универсального множества. Семейство подмножеств универсального множества обозначают символомB(U) и называютбулеаноммножестваU.

Например, если U={a,b,c},B(U)={, {a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c}}.

Легко видеть, что число элементов булеана B(U) зависит от числа элементов универсального множестваU по формуле: |B(U)|=2^|U|.

Задание множества может быть выполнено перечислением элементов внутри фигурных скобок, либо описанием его характеристических свойств.

При задании множества описанием его характеристических свойств между фигурными скобками после указания текущего значения элемента множества Х, т.е. хХ, ставится знак ““, вслед за которым указывают характеристическое свойство элементов множества, т.е. Р(х). При подстановке конкретного значения х=а выражение Р(а) принимает значение “истина” или “ложь”, т.е. Р(х) есть логическая функция, которую иначе называют-“предикат”.

Множество значений х=а1, х=а2, х=а3 и т.д., для которых Р(х=а_i)=“истина” формирует множество Х={а1, а2, а3,...}.

Множество может быть задано характеристическим вектором – вектором, размерность которого равна количеству элементов в универсальном множестве. Каждый компонент характеристического вектора множества А равен либо 1 (если соответствующий элемент универсального множесва содержится в А), либо 0 (если соответствующий элемент универсального множесва не содержится в А).

Над множествами определены ряд операций. Для наглядного изображения исполнения операций прямоугольником обозначают универсальное множество, а внутри него кругами изображают подмножества, принадлежащие универсальному множеству, которые называют кругами Эйлера. Заштрихованная область представляет собой результат исполнения операции. Иначе, такое изображение называют диаграммой Венна.

Объединениедвух множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному множеству А или В, т.е. (АВ)={x|xA или xB}.

На рис. 1а) приведено графическое представление операции объединения двух множеств А и В.

Если В=, то АВ=А=А. Если B=U, то АВ=АU=U. Если АС и ВС, то АВС.

Операцию объединения можно распространить на произвольное число подмножеств универсального множества U. Например, если А1;А2;...;АnU, то А1А2...Аn=АiU.

Пересечениедвух множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат множеству А и принадлежат множеству В, т.е. (АВ)={x|xA и xB}.

На рис. 1б) приведено графическое представление операции пересечения двух множеств А и В.

Если В=, то АВ=А=. Если B=U, то АВ=АU=А. Если СА и СВ, то САВ. Если Аи В, то при АВ=множества А и В не пересекаются и не имеют общих элементов.

Операцию пересечения можно распространить на произвольное число подмножеств универсального множества. Например, если А1;А2;...;АnU, то А1А2...Аn=АiU.

Дополнениемножества А до универсального множества U есть множество, состоящее из всех тех элементов, которые принадлежат универсальному множеству U и не принадлежат множеству А, т.е.А={x|xU и xA}. На рис.1в) приведено графическое представление операции дополнения для множества А. Если существуетА, то справедливы следующие соотношения: АА=, АА=U и(А)=А.

Операции дополнения, пересечения и объединения определяют две дополнительные операции: разности и симметрической разности.

Разностьмножеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат множеству А и не принадлежат множеству В, т.е. (А\В)= {x|xА и xВ}, т.е. (А\В)=(А(В)).

На рис. 6г) приведено графическое представление разности двух множеств А и В.

Рис. 6. Графическое изображение алгебраических операций над множествами А и В.

Симметрическая разность множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат разности (А\В) или (В\А), т.е. (АВ)=(АВ)(ВА)= {x|x(A\В) или x(B\А)}. На рис. 6д) приведено графическое изображение симметрической разности двух множеств А и В.

Если (АВ)=(АВ)(ВА)=, то А=В.

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

Для облегчения исполнения преобразований формул представим основные законы и правила в таблице 1.

Таблица 1.

наименование закона, правила	эквивалентные формулы
1. коммутативности	(AB)=(BA); (AB)=(BA);
2. ассоциативности	A(BC)=(AB)C; A(BC)=(AB)C;
3. дистрибутивности	3. A(BC)=(AB)(AC); A(BC)=(AB)(AC);
4. идемпотентности	4. AA=A; AA=A;
5. поглощения	5. A(AB)=A и A(AB)=A;
6. противоречия	6. А(А)=0; А(А)=U;
7. де Моргана	7. (АВ)=А(В);(АВ)=А(В);
8. свойство универсального множества	8. АU=U; AU=A;
9. свойство пустого множества	9. А=А; А=;
10.двойного отрицания	10.(А)=А.

Рассмотрим преобразование на примере, содержащем четыре подмножества А, В, С и D универсального множества U:

Пусть F=(ABCD)(AC)(BC)(CD);

1) выполним преобразование формулы, используя закон коммутативности

F=(CABD)(CA)(CB)(CD);

2) выполним преобразование формулы, используя закон дистрибутивности

F=(CABD)(CA)(C(BD));

3) повторим использование закона дистрибутивности

F=(CABD)(C(ABD));

4) используем еще раз закон дистрибутивности

F=C((ABD)(ABD));

5) применим закон де Моргана

F=C((ABD)(ABD));

6) используем закон противоречия

F=(CU);

7) применим известные свойства универсального множества

F=C;

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