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

Лабораторная работа №1

Решение уравнений в алгебре множеств

Цель работы: изучение методов решения уравнений исистем уравнений в алгебре множеств.

Теоретическая часть

Основные понятия теории множеств

Под множеством понимается объединение объектов в единое целое. Объекты, составляющие множество, называются его элементами и обозначаются обычно строчными буквами, а соответствующее множество – заглавной буквой. Принадлежность элемента множеству обозначается так: a Î A; если же a не является элементом множества A, то записывается a Ï A.

Множество полностью определяется своими элементами. Два множества считаются равными только в том случае, когда они состоят из одних и тех же элементов. Равенство множеств A и B обозначается как A=B, а неравенство A¹B.

Множество A называется подмножеством B, если его элементы являются элементами и множества B, т.е., если из a Î A следует a Î B. Принадлежность множества A множеству B обозначается так: A Ì B.

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

Множество, состоящее из одного элемента, называется одноэлементным и обозначается {a}. Множество, не содержащее элементов, называется пустым и обозначается Ф.

Наиболее просто множество может быть задано перечислением его элементов или списком A={a₁, a₂, a₃,... a_k}. Списком можно задавать только конечные множества.

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

где исходными объектами для построения являются натуральные числа, а порождающей процедурой – вычисление по формуле p/2 ± kn.

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

Более общим является задание множества описанием свойств его элементов. Например: «A – множество всех целых чисел, являющихся степенями двойки». В том случае, когда свойства элементов A могут быть описаны коротким выражением P(a) (означающим «a обладает свойством P»), A задается таким обозначением A={a | P(a)}, т.е. A – это множество элементов, обладающих свойством P. Например, A={x | x=2^k, где k Î N }.

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

В этом разделе приведены основные соотношения алгебры множеств, используемые для решения задач теории множеств.

1a) AUB = BUA 1b) A*B = B*A

2a) AU(BUC) = (AUB)UC 2b) A*(B*C) = (A*B)*C

3a) AUB*C = (AUB)*(AUC) 3b) A*(BUC) = ABUAC

4a) AUФ = A 4b) A*E = A

5a) 5b)

6a) AUE = E 6b) A*Ф = Ф

7a) 7b)

8a) AUA = A 8b) A*A = A

9a) AUAB = A 9b) A*(AUB) = A

10a) 10b)

11)Если AUB = E и AB = Ф, то

12)

13)

14)

15)

16) A+B = B+A

17) (A+B)+C = A+(B+C)

18) A+Ф = Ф +A = A

19)

20) AB+AC = A(B+C)

21) A Ì B, если только AB=A, либо AUB=A, либо

22) A=B, если и только если A+B = Ф

23)

24)

25)

26)

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

Тождества (1а)-(3а) выражают коммутативный, ассоциативный и дистрибутивный законы для объединения, а (1b)-(3b) – те же законы для пересечения. Соотношения (4а)-(7а) определяют свойства пустого множества Ф и универсума Е относительно объединения, а (4b)-(7b) – относительно пересечения.

Выражения (8а) и (8b), называемые законами идемпотентности, позволяют записывать формулы с множествами без коэффициентов и показателей степени.

Формулы (9а) и (9b) и (24) – это законы поглощения, (10а) и (10b) – законы де Моргана, а (23) – закон склеивания.

Соотношения (11)-(22) отражают свойства дополнения, разности, дизъюнктивной суммы, включения и равенства.