1.1 Задание множеств


Множество - это совокупность объектов, называемых элементами множества: запись аА обозначает принадлежность элемента а множеству А, запись bA обозначает, что элемент b не принадлежит A. Множество Ø, не содержащее ни одного элемента, называется пустым. Равенство множеств A и B (запись A=B) означает, что А и В состоят из одних и тех же элементов. Если каждый элемент множества А принадлежит множеству В, то говорят, что А есть подмножество В, или А входит в В (запись А В). Среди подмножеств любого множества В - пустое множество Ø и само В. Множества А и В равны, когда выполнены оба вхождения: А В и В А.

Множество считается заданным, если каким-либо образом указано некоторое свойство, которым обладают все его элементы и не обладают никакие другие объекты. В таком случае задание множества выглядит так: {X:<условие P>} и читается: "множество элементов X, для которых выполнено условие P" (здесь X - обозначение элемента).

В ряде случаев целесообразно рассматривать несколько множеств в качестве подмножеств универсального множества U. Множество элементов U, которые не принадлежат некоторому множеству A U, называется дополнением множества А (обозначение -A ).

Если А, В - два множества, то с помощью теоретико-множественных операций могут быть получены другие множества.
- Объединение С (обозначение С=АВ) - это множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств А, В.
- Пересечение С (обозначение С=А В) - это множество элементов, принадлежащих обоим множествам А и В.
- Разность С множеств А и В (обозначение С=А\В) - это множество элементов множества А, не принадлежащих множеству В.

Множества, обозначаемые теми же прописными латинскими буквами с подстрочным знаком "+" или
"-", например Z+ или R - суть подмножества множеств Z и R, состоящие из чисел соответствующего знака.

Подмножества упомянутых числовых множеств, состоящие из чисел, находящихся между двумя числами a,b, называются промежутками:

- интервал (открытый промежуток) {X: a<X<b} обозначается (a,b);

- отрезок (замкнутый промежуток) {X: a ≤ X ≤ b} обозначается [a,b]; a и b называются концами промежутка: отрезок содержит оба своих конца, интервал не содержит ни одного. Полуинтервалы (a,b] и [a,b), содержащие один конец промежутка, определяются анологично. Бесконечные промежутки (a,+),[a,+),(-,b),(-,b] суть множества чисел, удовлетворяющих соответственно соотношениям X>a, Xa, X<b, X ≤ b.

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

Из простых высказываний p,q строятся сложные с помощью следующих основных логических операций:

Обозначая истинность 1, а ложность - 0, можно задать упомянутые операции таблицами 1 и 2.

 

Таблица 1
p ┐p
0 1
1 0

Таблица 2
p q p q p q pq pq
0 0 0 0 1 1
0 1 0 1 1 0
1 0 0 1 0 0
1 1 1 1 1 1

 

Неопределенному высказыванию P(X), содержащему переменную X, можно сопоставить высказывания "для всех X P(X) истинно", обозначаемое X: P(X), и "существует X такое, что P(X) истинно", обозначаемое X: P(X). Такие операции называются кванторами: квантором общности и квантором существования .

X: P(X) - высказывание истинное, если для всякого (каждого, любого) X выполнено P(X) и ложное, если, напротив, существует X0, для которого P(X0) ложно. X: P(X) - высказывание истинное, если хотя бы для одного X0 высказывание P(X0) истинно, и ложное, если напротив, такого X0 нет, т.е. для всех X
P(x) ложно.

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

Определить, обладает ли тот или иной объект заданным свойством и тем более найти все такие объекты, может быть сложной задачей. Например, найти множество корней уравнения означает решить уравнение. Решение вопроса о том, существует ли процедура распознавания тех или иных свойств математических объектов, относится к проблемам теории алгоритмов. Перечислим основные свойства этих операций. Пусть U -универсальное множество, A, B, C, - его подмножества, Ø - пустое множество. Равенства 1-10, 15-18 относятся к операциям объединения и пересечения; равенства 11-14 и 19-21 - к операции дополнения.

 

Таблица 3
1 AB = BA 2 AB = BA
3 (AB)C = A(BC) 4 (AB)C = A(BC)
5 (AB)C = (AC)(AB) 6 (AB)C = (AC)(AB)
7 AA = A 8 AA = A
9 A(AB) = A 10 A(AB) = A
11 ┐(AB)=┐A┐B 12 ┐(AB) = ┐A┐B
13 A┐A = U 14 A┐A
15 AØ = A 16 AØ = Ø
17 AU = U 18 AU = A
19 ┐U = Ø 20 ┐Ø = U
21┐(┐A) = A  

 

Приведем также ряд свойств операции разности множеств.

  1. A\B=A┐B;
  2. A\A=Ø
  3. A\Ø=A
  4. A\U=Ø

Еще один способ задания множества связан с понятием порождающей процедуры.

Простейший пример - задание последовательности элементов множества формулой, содержащей параметр:

A={Xk=3+2(k2+1)}, k=0,1,2, ...

Задавая различные значения параметра k, мы можем вычислять элементы множества A: X0=5, X1=7, X2=13 и т.д. Подобное задание может быть явным, как в данном примере, или неявным, требующим разрешения. В частности, используются возвратные, или рекурентные соотношения. Например, числа Фибоначчи задаются условиями:

a1=1, a2=2, an=an-1+an-2 для n>2.

Последняя формула позволяет последовательно вычислять значения
a3=a2 + a1=2+1=3;
a4=a3 + a2=3+2=5;
a5=a4 + a3=5+3=8 и т.д.

Возможность выразить общий n-й член этой последовательности как явную функцию параметра n для того, чтобы можно было определить, например, значение a100, не вычисляя всех предыдущих, будет рассмотрена в разделе "Элементы комбинаторики"

Рассмотрим другой пример задания числового множества M порождающей процедурой:

  1. 5M;
  2. если aM, то 1/a M;
  3. если aM, то (1-a)M.

Убедимся, что множество M конечно и состоит из 6 элементов, а именно

M ={5, 1/5, -4, -1/4, 4/5, 5/4}.

В самом деле, для каждого a, начиная со значения a=5, есть две возможности порождения новых элементов: операциями (2) и (3). При этом могут получаться и элементы, порожденные ранее. Так, из числа 5 операцией (2) получается 1/5, операцией (3) - число (-4), а из числа 1/5 операцией (2) - снова число 5.

Рассмотрим схему порождения (рисунок 1), где операция (2) изображена одинарной стрелкой, а операция (3) - двойной. Схема показывает, что никаких других чисел процедуры (2) и (3) не дают.

Если же в правиле (3) заменить (1-а) на (2-а), то порождаемое множество будет бесконечным: из числа 5 чередующейся последовательностью операций (2) и (3) порождается последовательность чисел


5 1/5 9/5 5/9 13/9 9/13 17/13 13/17 ...
       
1+4(k+1) 1+4k 1+4(k+2)  :       :(k =0,1,2, ...)
  1+4k   1+4(k+1)  1+4(k+1)

Рисунок 1
Рисунок 1

Введем еще одно понятие.

Разбиение множества U - система непустых подмножеств {Aa} множества U такая, что их объединение равно U (полнота разбиения), а все попарные пересечения - пусты (чистота разбиения). Сами Aa называются классами, или блоками разбиения. Система курсов данного факультета есть разбиение множества его студентов; система групп есть другое разбиение того же множества.

Другой пример: множество всех автомобилей может быть разными способами разбито на классы в зависимости от марки, объема двигателя, компании-производителя, года выпуска, стоимости и др.

При анкетировании или классификации объекты распределяются по группам; не входящие в ту или иную конкретную группу могут составлять группировку "прочие" - для полноты разбиения.

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

Множество квартир дома разбивается на подмножества квартир, расположенных на одном этаже; другое разбиение - на подмножества квартир из одного подъезда.

Если А и В - два подмножества универсального множества U, то 4 подмножества

D0=┐A┐B, D1=┐AB, D2=A┐B, D3=AB

образуют разбиение множества U (рисунок 2). Аналогично, для 3 множеств А, В, С разбиение универсального множества U на 8 подмножеств М0 - М7 изображено на рисунке 3. Сами множества А, В, С могут быть представлены как объединения:
А = М4 М5 М6 М7,
В = М2 М3 М6 М7,
С = М1 М3 М5 М7.

Рисунок 2 Рисунок 3
Рисунок 2 Рисунок 3

Каждый элемент может входить в множество в единственном экземпляре, без повторений, в отличие, например, от выборки в математической статистике. Конечная последовательность любых объектов, среди которых могут быть и повторяющиеся, называется кортежем (или вектором). Сами объекты называются компонентами кортежа. Вектором обычно называется кортеж, состоящий из чисел. Кортеж обозначается так же, как вектор: а = (а1,а2, ..., а3); n называется длиной кортежа. Примером кортежа могут служить кортеж чисел, кортеж цифр в записи целого числа, кортеж букв в слове, кортеж слов во фразе.

Два кортежа называются равными, если у них при одинаковой длине совпадают первые элементы, вторые элементы и т.д. Поэтому, например, кортежи (7, 8, А , +, 8) и (7, 8, +, 8, А) различны, хотя имеют одинаковый состав.

Декартовым (прямым) произведением множеств называется:

  1. для двух множеств А, В: произведение АВ - множество всех пар (a,b), где aA, bB;
  2. для n множеств A1, A2, ..., An произведение A1A2 ... An - множество всех векторов
    (a1,a2, ..., an), где aiAi (a1A1, a2A2, ..., anAn); если все Ai одинаковы и равны А, то произведение
    A1A2 ... An
    n - раз
    обозначается Аn и называется n-ой степенью множества А.

Примеры
  1. Если R - множество точек числовой прямой, то Rn - множество точек n -мерного арифметического пространства; в частности, R2 - множество точек плоскости, R3 - множество точек пространства трех измерений.
  2. Рассматриваемый в физике пространственно-временной континуум, представляющий собой прямое произведение R3T, где R3 - трехмерное пространство, а T - числовая ось времени.
  3. Географические координаты точки земной поверхности: широта и долгота представляют элемент прямого произведения ШД, где Ш = [-90, +90], Д = [-180,+180].
  4. Известно, что прямая в трехмерном пространстве определяется двумя точками в том смысле, что через две различные точки проходит ровно одна прямая. Упорядоченная пара точек (M,N) есть элемент R3R3, которому можно сопоставить 6-мерного пространства R6 - 6 чисел: тройку координат точки M и тройку координат точки N. В этом примере пара (N,M) определяет ту же прямую, что и (M,N), а пара совпадающих элементов (M,M) не определяет прямой.
  5. Возможные исходы при бросании игральной кости составляют множества {1,2,3,4,5,6}, т.е. отрезок [1,6] натурального ряда. Если же игральную кость бросают 4 раза, то пространство элементарных событий представляет собой [1,6]4, т.е. множество всех четверок (а1234), где ai{1,2,3,4,5,6}. В отдельных случаях имеют содержательный смысл не все пары, тройки и т.д. Так, в примере 3 при Ш=900 не имеет смысла значение Д (подобно тому, как в полярных координатах при ρ=0 не определено значение полярного угла φ). Если А и В - два множества А2В2 В)2; равенство достигается только если АВ или ВА (в частности, если А=В).Практической иллюстрацией этого соотношения является следующий пример.
  6. В определении возрастания функции действительной переменной на множестве фигурируют пары точек:
если Х12, то ƒ(Х1)>ƒ(Х2). (*)

Поэтому для функции ƒ возрастающей на множестве А1, выполнено условие (*) для Х1, Х2А1, т.е. (Х1, Х2) 1)2. Аналогично, при возрастании той же функции на множестве А2 условие (*) должно выполняться для (Х1, Х2) 2)2. На рисунке 4 штриховкой показаны оба этих множества, - для наглядности, А1 и А2 - два непересекающихся промежутка А1=[a, b], A2=[c, d]. В то же время, для возрастания функции ƒ на объединении А1А2 необходимо, чтобы условие (*) выполнялось для любой пары (Х1, Х2)1, А2)2. Из рисунка 4 видно, что это множество на координатной плоскости состоит из 4 частей: двух квадратов [a, b]2 и [c, d]2 и двух произведений [a b][c,d] и [c, d][a, b]. В этих частях множества (А1А2)2 условие (*) может выполняться не для всех пар (Х1, Х2). Поэтому из возрастания функции ƒ отдельно на А1 и А2 не следует, вообще говоря, возрастание на их объединении. Рассмотрите, например, функцию Y=tgX в областях (0,π/2) и (π/2,3π/2) - рисунок 5.

Рисунок 4 Рисунок 5
Рисунок 4 Рисунок 5

 

Вопросы для самоконтроля

Задание множеств

  1. Дайте определение понятия множества, подмножества.
    Приведите примеры.
  2. Сформулируйте определения операций над множествами.
  3. Какие промежутки вы знаете?
  4. Приведите примеры высказываний.
  5. Сформулируйте основные логические операции.
  6. Что означают кванторы и ?

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

  1. Перечислите основные свойства операций.
  2. Дайте определение понятию разбиения множества.
  3. Сформулируйте определение картежа.
  4. Дайте определение понятию декартового произведения множеств.
  5. Приведите примеры множеств и их декартовых произведений.

Практические задания

Tест для самоконтроля