ДМ_Конспект

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

M1 – множество всех решений уравнения sin x = 1, то есть

M1 = x | sin x =1 ;

A множество прямых, проходящих через заданную точку.

Пример. В качестве признака принадлежности объекта некоторой совокупности (множеству) могут быть следующие свойства (признаки): «быть цифрой», «быть буквой», «быть числом», «быть словом», «быть служебным символом», «быть идентификатором данного», «быть кодом операции» и т.п.

Для обозначения конкретных множеств в общем виде используются

различные	заглавные буквы		A, M, S,...		или заглавные буквы		с	индексами,
например,	A1 , A2 ,..., An . Для обозначения элементов множеств в общем виде
используются различные		строчные буквы a, m, s, ...				или строчные буквы с
индексами a1 , a2 ,..., an .
Утверждение, что		множество		A	состоит из	различных		элементов
a1 , a2 ,..., an	(и только	из	этих	элементов),		условно	записывается

A = a1 , a2 , ..., an , т.е. множество обозначается скобками {…}, внутри которых либо просто перечисляются элементы, либо описываются их свойства.

Пример.	M = 1, 2, 3, 4, 5, 6, 7, 8 ; D4		{ , , , , }.
Элементами множеств могут быть другие множества, тогда эти элементы
обозначаются заглавными буквами.
Пример.	D {A, B,C},	где	A={1, 3, 5, 7},	B {a,b, c, d, e},
C ={Иванов, Петров, Сидоров}.
E {{a, b, c, d, e}, {b, d}, a}.		Множество E состоит из трех элементов:

{a, b, c, d, e}, {b, d}, a .

Определение. Множество, элементами которого являются множества, обычно называются классом или семейством.

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

Если a есть один из объектов множества A , то говорим, что a есть элемент A , или a принадлежит A . Принадлежность элемента a множеству A записывается как a A. Если a не является элементом A , это записывается как a A . Символ называется символом принадлежности.

11

Пример. 3 {1, 2, 3, 4}, но 5{1, 2, 3, 4}.

Поскольку множество однозначно определяется только элементами, которые оно содержит, порядок перечисления элементов между фигурными

скобками	произвольный,	т.е. {a, b, c, d, e} {c, a, e, b, d}, но многократная
запись	одного и того	же элемента – не желательна, т. е.
{a, a, a, a, b, b, c, c, d} {a, b, c, d}.

Определение. При многократной записи одного и того же элемента множество называют мультимножеством и применяют особые методы анализа.

С точки зрения теории множеств, множество и его мультимножество – это один и тот же объект, и они могут между собой не различаться. Однако часто, особенно когда речь идет о представлении множества в памяти вычислительной машины, возникает потребность отличать мультимножество от множества.

Определение. Множество, в котором важны не только его элементы, но и порядок их следования во множестве, называется упорядоченным.

Определение. Конечное множество называется упорядоченным, если его элементы пронумерованы.

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

Определение. Кортеж (вектор) это упорядоченный набор элементов A (a1 , a2 , ...,an ) . Элементы, образующие кортеж, называются координатами или компонентами. Координаты нумеруются слева направо.

Определение. Число координат кортежа (вектора) называется длиной или размерностью кортежа (вектора).

Пример.

A (1, 2, 3, 4) упорядоченное множество, состоящее из 4-х элементов

(кортеж длины 4);

B b1 , b2 , ...,bn , где n N.

Пример. Пусть A (x, y) множество географических координат долготы x и широты y . Если поменять местами долготу и широту, то в результате можно попасть в другую точку света.

1.3 Конечные, бесконечные, счетные множества

Множество может содержать любое число элементов – конечное или бесконечное.

12

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

Пример. Множество действительных решений квадратичного неравенства x2 + px + q 0 конечно, если D 0, и бесконечно, если D > 0 .

Примеры конечных множеств:

множество цифр 0, 1, 2, 3, ...,9;

множество страниц в книге.

Примеры бесконечных множеств:

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

множество окружностей на плоскости.

Определение. Множество A называется счетным, если его объекты можно пересчитывать (каждому объекту множества присвоить натуральное число, которое было бы номером лишь одного элемента множества).

Пример. Множество цифр счетно и конечно, а множество целых чисел – счетно, но не конечно.

1.4 Пустое и универсальное множества

В теории множеств используются понятия «пустого множества» и «универсального множества».

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

Пример. Пусть A – множество действительных решений квадратного уравнения x2 + px + q 0 . Множество A конечно, | A | 2 Если дискриминант D = p2 4q отрицателен, множество A пусто.

Пример. Множество выигрышей в следующем тираже спортлото на купленные билеты может оказаться пустым.

Пример. Неизвестно, является ли пустым или нет множество всех решений в целых числах уравнения x3 + y3 + z3 = 30 .

Пустое множество введено в математике для удобства и единообразия языка. Роль пустого множества аналогична роли числа нуль. Если исследуется множество объектов, обладающих каким-либо свойством, и впоследствии выясняется, что таких объектов не существует, то гораздо удобнее сказать, что исследуемое множество пусто, чем объявлять его несуществующим. Понятие пустого множества может быть использовано для

13

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

Пример. Множество действительных корней уравнения x2 +1= 0 является пустым множеством.

Введем понятие универсального множества.

Определение. Универсальное множество (или универсум), которое обозначают символом U , есть множество, содержащее все элементы, принимающие участие в решении определенного класса задач.

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

Примеры. Так, множество слонов следует искать среди млекопитающихся, а не среди рыб.

Если речь идет о множестве чисел, делящихся на 3, то ясно, что оно является множеством целых чисел.

Втеории чисел универсум обычно совпадает с множеством всех целых или натуральных чисел.

Вматематическом анализе универсум может быть множеством всех действительных чисел или множеством всех точек n -мерного пространства.

Универсумом зоологии является мир животных; универсумом лингвистики – слова и т.д.

1.5 Мощность множества

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

Определение. Мощность конечного счѐтного множества A есть число его элементов n , которое обозначают как | A | n .

Пример. Мощность множества цифр десятичной системы счисления равна 10.

Мощность множества строчных букв латинского алфавита – 26. Мощность пустого множества равна нулю (| | 0 ), а мощность

множества { } равна 1, т.е. |{ }|=1.

14

Определение. Если | A | | B |, то множества A и B называются

равномощными.

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

Чтобы задать множество, нужно указать, какие элементы ему принадлежат.

Существует несколько основных способов задания (описания) множеств:

словесное (вербальное) описание элементов множеств и их основных характеристик;

простое перечисление элементов множества;

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

Рассмотрим каждый из перечисленных способов.

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

итехнической документации и т.п.).

Пример. Спецификация задает множество деталей изделия. Каталог – множество книг в библиотеке.

Простое перечисление элементов множества (неупорядоченного) между фигурными скобками используется, в основном, для описания конечных множеств.

Пример.

A {1, 2, 3, 4} есть множество, содержащее натуральные числа 1, 2, 3 и 4.

D {хлебобулочные_ изделия, кондитерские _ изделия, молочные_ продукты, напитки, фрукты}

есть множество продуктов питания.

Множество гласных букв можно представить как

{а, е, ѐ, и, о, у, ы, э, ю, я}.

B {2, 3} – множество решений уравнения x2 5x + 6 = 0.

C {0,1, 2, 3, 4, 5, 6} – множество остатков при делении целых чисел на 7.

15

Иногда перечислением элементов задают и бесконечное множество. Это делают в тех случаях, когда ясен алгоритм последовательного порождения элементов.

Пример. Множество положительных целых чисел можно обозначить как

{1, 2, 3, 4, ...}.
Множество	первых n положительных	целых	чисел обозначается
{1, 2, 3, ..., n}, где точками показано продолжение перечисления элементов.
S {1, 4, 9, ...,n2 } описывает множество квадратов всех положительных
чисел, которые меньше или равны n .
C {1, 8, 27,	..., k3} описывает множество	кубов	всех положительных

чисел.

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

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

Пример. Используя способы перечисления не так легко описать, например, множество граждан Украины и совершенно немыслимо описать множество действительных чисел.

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

указания характерных свойств элементов множества или характеристической функции множества (характеристическим предикатом);

заданием порождающей процедуры.

При заданном характеристическом (определяющем) свойстве P и

заданном классе элементов		K	(универсальном		множестве для	решаемой
задачи) множество A определяется				как множество, которое содержит все
элементы из K , обладающие свойством P . Для определения						по	схеме
свертывания	используется			следующая		запись
A {x | x обладает свойством Р}.
Пример.	Множество	четных		чисел A	можно определить		как
A {x | x четное целое число}			или	как A {x Z | x четно}, где через Z

обозначено множество целых чисел.

16

X {x | x гражданин Украины} – множество граждан Украины.

X {x | x есть животное с хоботом} – множество слонов.

Свойства, которыми должны обладать элементы формируемого множества A , можно описать характеристической функцией (характеристическим предикатом) P(x) . Обычно P(x) – это высказывание, в котором что-то утверждается об x , или некоторая функция переменной x . Тогда множество можно представить как A {x | P(x)}. Если класс K указан явно, то в этом случае используется запись A {x K | P(x)}. Если при замене x на a высказывание P(a) становится истинным или функция в заданной области определения удовлетворяется, то a есть элемент данного множества. Таким образом a {x | P(x)}, если P(a) истинно.

Пример.

а) X ={x | x2 = 2} – множество чисел, квадрат которых равен двум;

б) X ={x | x2 +1> 0} – множество чисел, квадрат которых плюс единица больше нуля.

Множество может быть также задано при помощи порождающей процедуры (рекурсивно) A={x | x := f }.

Определение.

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

Пример. Множество нечетных чисел можно задать порождающей

процедурой A {x | x : (2n 1),		где n 1, 2, 3, ...}.
Множество	можно	задать	рекурсивной	процедурой

F = {xi | xi := 2xi 2 + xi 1 , x0 =1, x1 = 3}.

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

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

17

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

Пример. Множество всех хороших фильмов 2011 года разные люди зададут разными списками (может быть пустыми). Сами критерии, по которым производится отбор, при этом будут различны. Такое множество нельзя считать строго заданным.

Неограниченное применение схемы свертывания, некорректность задания множества, свободное использование понятий интуитивного теоретико-множественного универсума иногда ведет к противоречиям, которые называются логическими парадоксами (парадокс Рассела, парадокс Кантора, парадокс Банаха-Тарского) и изучаются в математической логике.

Пример.

Можно получить «множество всех множеств» M {x | x множество}. Если считать M множеством, то получаем M M .

1.7 Множество и подмножество

Определение. Множество A , все элементы которого принадлежат и множеству B , называется подмножеством (частью) множества B . При этом говорят, что B содержит или покрывает A .

Это отношение между множествами называют включением и обозначают символом , т.е. A B ( A включено в B ) или B A ( B включает A ).

Если A не является подмножеством B , это записывается как A B . Таким образом, A B , если существует элемент A , не принадлежащий B .

Пример:

а) множество конденсаторов электронной цепи является подмножеством всех еѐ компонентов;

б) множество положительных чисел – это подмножество множества действительных чисел.

в) {1, 2, 3} {1, 2, 3, 4}; г) {1, 2, 5} {1, 2, 3, 4}.

Пример. Книга из множества книг в шкафу может рассматриваться как множество страниц. Следует обратить внимание на то, что речь идет об

18

элементах множества, а не о подмножествах, т.к. никакая совокупность страниц не может рассматриваться как подмножество множества книг.

Множества A и B равны ( A= B) , если их элементы совпадают. Иначе говоря, A = B тогда и только тогда, когда A B и B A.

Пример. Если A есть множество {2, 4, 6}, а B есть множество

{x | x есть положительное четное целое число, которое меньше 7}, тогда A

и B – равные множества.

Определение.

Если A B и A B , то A часто называется собственным, строгим или истинным подмножеством B .Записывается данное отношение как A B , где знак строгого включения.

Пример. Пусть A {x | x человеческое существо мужского пола};

B {x | x человеческое существо}, тогда ясно, что A B и A – собственное (истинное) подмножество B .

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

Эти подмножества называются несобственными, а все другие подмножества A называются собственными. Если требуется различать собственные и несобственные подмножества, то для обозначения включения собственных подмножеств используется знак ( ), а для несобственных –

( ).

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

Пример: A {1, 2, 3}; A1 {1};			A2 {2}; A3 {3}; A4		{1, 2};	A5	{1, 3};
A6 {2, 3}. Ai A , где i =1, 6 .
Определение. Множество всех подмножеств множества A ,						или булеан
множества A , обозначаемый ( A) (или 2A ), есть множество, состоящее из
всех подмножеств множества A .			Множество	( A)	называется		также
множеством-степенью.
Пример. Так, для трѐхэлементного множества				A={a, b, c} булеан имеет

вид (A) 2A { , {a},{b},{c},{a, b},{a, c},{b, c},{a, b, c}}.

19

В случае конечного множества A , состоящего из n элементов, множество подмножеств ( A) содержит 2A элементов, т.е. | ( A) | | 2A | 2|A| 2n .

Пустое множество имеет только одно подмножество – само пустое множество, поэтому ( ) = 2 ={ }.

1.8. Контрольные вопросы и задания

1.Что такое множество? Приведите примеры различных множеств.

2.Какие способы задания множеств Вы знаете?

3.Что такое пустое множество? Обоснуйте необходимость использования пустого множества.

4.Что такое универсальное множество? Приведите примеры универсального множества.

5.Дайте определение конечного и бесконечного множества.

6.Дайте определение счетного множества.

7.Что такое мощность множества?

8.Дайте определение подмножества. Приведите примеры подмножеств.

9.Какое отношение между множествами называют строгим включением?

10.Чем отличается понятие включения ( или ) от понятия принадлежности ( )?

11.В каких случаях можно говорить, что множества A , B и C равны?

12.Поясните понятие «булеан множества A ». Приведите примеры

булеана.

ЛЕКЦИЯ 2 АЛГЕБРА МНОЖЕСТВ

2.1 Геометрическая интерпретация множеств. Круги Эйлера и диаграммы

Венна

Для наглядного представления отношений между подмножествами универсального множества U используются диаграммы Венна и круги Эйлера.

Построение диаграммы Венна заключается в разбиении плоскости на 2n ячеек с помощью n фигур, каждая из которых представляет на диаграмме отдельное множество, а n – число изображаемых множеств.

Плоскость, на которой изображаются фигуры, представляет универсальное множество. Чаще всего универсальное множество при этом изображают в виде прямоугольника, а его подмножества изображают в виде кругов (кругов Эйлера), находящихся внутри прямоугольника.

20