Множество - состоит из элементов. Принадлежность элемента а множеству М обозначается а М (“а принадлежит М”), непринадлежность - а М или а М.
Множество А называется подмножеством множества В (обозначается А В), если всякий элемент из А является элементом В (рис 1.1). Если А В и А В, то А называется строгим (собственным) подмножеством (обозначается А В).
Содержательные примеры множеств и ихвозможные обозначения:
А - множество сотрудников фирмы “Элегант”;
М1- множество всех операций (работ) по сборке компьютера;
М2- множество видов услуг, предоставляемых фирмой “Силуэт”;
N-множество натуральных чисел 1,2,3,...;
N1-множество натуральных чисел, не превосходящих 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) M2n;..:в) п ≤ 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 проиллюстрировано свойство дистрибутивности слева операции пересечения относительно операции объединения . Подтвердить справедливость свойства дистрибутивности справа пересечения относительно объединениям , а также слева и справа и относительно , т.е.:
а) - справа относительно и ;
б) - слева относительно ;
в) - справа относительно .