Множества. Основные понятия. Операции над множествами

Множество - состоит из элементов. Принадлежность эле­мента а множеству М обозначается а М (“а принадлежит М”), непринадлежность - а М или а М.

Множество А называется подмноже­ством множества В (обозначается А В), если всякий элемент из А является элемен­том В (рис 1.1). Если А  В и А В, то А называется строгим (собственным) под­множеством (обозначается А В).

Содержательные примеры множеств и ихвозможные обозначения:  

А - множество сотрудников фирмы “Элегант”;       

 М₁- множество всех операций (работ) по сборке компью­тера;

М₂- множество видов услуг, предоставляемых фирмой “Силуэт”;

N-множество натуральных чисел 1,2,3,...;

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

R-множество всех действительных чисел и т.д.

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

1. Множества А и В равны (А = В), если их элементы со­впадают.

2. Множества Аи В равны, если А ВиВ А.

Множество, состоящее из конечного числа элементов, на­зывается конечным, в противном случае - бесконечным (на­пример, множества N, R- бесконечные множества). Число элементов в конечном множестве Mназывается его мощнос­тью и обозначается \М\.

Множество мощности 0, т.е. не содержащее элементов, называется пустым (обозначается ): = 0. Принято считать, что пустое множество является подмножеством любого множества.

Способы задания множеств.

Перечислением, т.е. списком своих элементов. Спис­ком можно задать лишь конечные множества. Обозначение списка-в фигурных скобках. Например, множество А уст­ройств домашнего компьютера, состоящего из процессор­ного блока а, а также периферийных устройств В (монито­ра b, клавиатуры с и принтера d),может быть представлено списком:

 (Задание типа N = 1,2,3,... - не список, но лишь допусти­мое условное обозначение.)

Порождающей процедурой, которая описывает способ получения элементов множества из уже полученных элемен­тов либо других объектов. В таком случае элементами мно­жества являются все объекты, которые Могут быть построены с помощью такой процедуры. Например, множество всех целых чисел, являющихся степенями двойки М_2n,n N,где N- множество натуральных чисел, (допустимое обозначение М_2n = 1,2,4,8,16,...) может быть представлено порождающей процедурой, заданной двумя правилами, называемыми рекур­сивными, или индуктивными

а)    ; б)

• Описанием характеристических свойств, которыми должны обладать его элементы; обозначается:

.

(“Множество Мсостоит из элементов х таких, что х обла­дает свойством Р”) Например, множество А периферийных устройств персонального компьютера PCможет быть опре­делено:

А = {х: х - периферийное устройство персонального компьютера PC}.

Если свойство элементов множества М может быть опи­сано коротким выражением, это упрощает его символьное представление. Например, множество всех натуральных чет­ных чисел может быть представлено:

Надежным способом точно описать свойство элементов данного множества является задание распознающей (раз­решающей) процедуры. Она должна устанавливать для лю­бого объектах, обладает ли он данным свойством Р (и, сле­довательно, принадлежит множеству) или нет. Например, распознающей процедурой для множества А всех сотруд­ников фирмы “Квант”, имеющих удостоверение фирмы, является проверка его наличия. Тогда множество А может быть представлено более точно: “А - множество всех со­трудников фирмы «Квант», имеющих соответствующее удо­стоверение фирмы”.

Еще пример: для описания характеристического свой­ства элементов множества М_2n всех целых чисел, являющих­ся степенями двойки (“быть степенью двойки”), разреша­ющей процедурой может служить любой метод разложе­ния целых, чисел на простые множители. Тогда а  М _2n, если 1или если а=2х2х ... х2 = 2^п, п N..

Пример 1. Задать различными способами множество Nвсех натуральных чисел: 1, 2, 3..

 Списком множество Nзадать нельзя, ввиду его бес­конечности.

Порождающая процедура содержит два правила:

а) 1 N;б) если n N,то п +1 N

Описание характеристического свойства элементов множества N

N={х: x - целое положительное число}.

Пример 2. Задать различными способами множество М всех четных чисел 2,4,6,..., не превышающих 100.

а) ; б) если n N,то (n+2) M_2n;.._:в) п ≤ 98.

М_2n= {n: п - целое положительное число, не превыша­ющее 100} или = {п: п Nи п/2 т N,n≤100}.

Пример 3, Пусть U= {а, b, с}. Определить в явном виде (перечислением своих элементов) булеанβ(U)- множество всех подмножеств, состоящих из элементов множества U.Ка­кова мощность множества β(U)

Пример 4. Какие из приведенных определений множеств А, В,С, Dявляются корректными:

Принадлежит ли число 1 множеству D?

а) Определение множества A = {1,2,3} списком своих элементов формально корректно.

б) При перечислении элементов множества не следует ука­зывать один и тот же элемент несколько раз. Корректное оп­ределение В = {5,6,7}..

в) Определение множества С = {х:х А} заданием харак­теристического свойства его элементов “принадлежать мно­жеству А” корректно, А = {1,2,3}.

г) Определение списком множества D= {А, С} коррект­но: элементами множества Dявляются множества А и С. Однако 1 не принадлежит Д, 1  Д так как элемент 1 не перечислен в списке.

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

Объединением множеств А и В (обо­значается А В) называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В (рис 1.2):

Пересечением множеств А и В (обозна­чается А В) называется множество, со­стоящее из всех тех и только тех элемен­тов, которые принадлежат и А, и В (рис 1.3):

 

Объединение и пересечение произвольной совокупности множеств определяются аналогично. Символическая запись, например, для объединения: А и В и С и D;

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

Разность - операция строго двухместная и некоммутатив­ная: в общем случае А\В≠В\А.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 3. Осуществить операции над множествами А = {а, b, с, d)и В = {с, d, e,f, g, h).

А  В - {a, b, с, d, e,f g, h)', A B = {c, d).

Универсальное множество Uне определено, поэтому, стро­го говоря, операции дополнения над множествами А и Вне могут быть выполнены. Дополним условие. Пусть U ={а, Ъ, с, d, e,f g, h},тогда  = U\A = {e f g, h},  ={a, b}. A\B= {a, b};B\A = {e,fg,h}.

Пример 4. пусть U={1,2,3,4},A = {1,3,4},B={2,3}, С = {1,4}. Найти:

а) в) г) (B\A) .

Решение. a)

Диаграммы Венна.

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

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

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

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

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

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

Построим теперь диаграммы Венна. Левая часть равен­ства представлена на рис. 1.7,а, правая - на рис. 1.7,6. Из диаграммочевидно равенство левой и правой частей иллю­стрируемого соотношения.

В примере 1 проиллюстрировано свойство дистрибутив­ности слева операции пересечения  относительно операции объединения . Подтвердить справедливость свойства дист­рибутивности справа пересечения  относительно объедине­ниям , а также слева и справа и относительно , т.е.:

а) - справа  относитель­но и ;

б) - слева  относительно ;

в) - справа относитель­но .