Тема 1. Множества. Множества и отношения Тема Множества

• Название: Множества и отношения Тема Множества
• Анкор: Тема 1. Множества.pdf
• Дата: 09.12.2022
• Размер: 0.63 Mb.
• Имя файла: Тема 1. Множества.pdf
• Тип: Глава; #835970

Глава 1. Множества и отношения
Тема 1. Множества
Понятие множества относится к фундаментальным неопределяемым понятиям математики. Это связано с тем, что некоторые понятия в математике должны быть исходными, чтобы служить основой, на базе которой определяются другие понятия и строится общая теория. Такие исходные понятия вводятся через описание наиболее характерных для них свойств, причем иногда приходится апеллировать к интуиции и жизненному опыту.
Математическое понятие множества выделилось как обобщение представлений о совокупности, классе, семействе и т. д. Основоположник теории множеств Г. Кантор (1845
–
1919) под множеством понимал любое
собрание определенных и различимых между собой объектов, мыслимое как
единое целое. Очевидно, что это описание понятия множества нельзя считать математическим определением, так как здесь слово «множество» заменено словом «собрание», а новое математическое определение выражает определяемое понятие через другие уже известные понятия. Понятие же множества не удается свести к известным понятиям, можно только постараться разъяснить его через описание характерных свойств и на примерах. Отметим три важных момента в канторовском понимании понятия множества.
Объекты, входящие во множество, определенные. Это означает, что для каждого объекта можно однозначно сказать, принадлежит ли оно данному множеству или нет.
Объекты, входящие во множество, различимы между собой. Это означает, что во множестве не может быть двух или более одинаковых объектов. Все объекты, входящие во множество, мыслятся как единое целое. Таким образом, все объекты рассматриваются в совокупности, а от свойств отдельных объектов абстрагируются.
1.1. Основные числовые множества и обозначения

Пример 1.1. Примеры множеств:
1. Множество N натуральных чисел 1, 2, 3, …;
2. Множество P простых чисел 2, 3, 5, 7, 11, …;
3. Множество Z целых чисел: … –2, –1, 0, 1, 2, …;
4. Множество R вещественных чисел;
5. Множество M людей, проживающих в данном доме и т. д.
Объекты, входящие во множество, называются
элементами.
Принадлежность элемента

множеству
M
обозначается
M


(«

принадлежит
M
»), непринадлежность –
M


или
M


(«

не принадлежит
M
»).
Обычно множества обозначают прописными буквами латинского алфавита, а элементы множеств – строчными буквами. Множества как объекты могут быть элементами других множеств. Множество, элементами которого являются множества, обычно называется классом или семейством.
Множества, состоящие из конечного числа элементов, называются
конечными, в противном случае – бесконечными.
Множество, не содержащее элементов, называется пустым и обозначается символом

При работе в конкретной предметной области элементы всех множеств берутся из некоторого одного, достаточно широкого множества U (своего для каждого случая), которое называют базовым или универсальным множеством
(или универсумом).
1.2. Способы задания множеств
Чтобы задать множество, нужно указать, какие элементы ему принадлежат.
Основные способы задания множеств:

Перечислением, т. е. списком своих элементов. Списком можно задать только конечные множества. При задании множеств перечислением

обозначения элементов обычно заключают в фигурные скобки и разделяют запятыми.
Пример 1.2.


1, 2, 3, 4, 5, 6, 7, 8, 9
A


Характеристическим предикатом, т. е. описанием характеристических свойств, которыми должны обладать элементы множества; обозначается:


| ( )
M
x P x

или


: ( )
M
x P x

. («Множество
M
состоит из элементов
x
таких, что
x
обладает свойством
P
»).
Пример 1.3. Множество
B
решений уравнения
2 5
6 0
x
x

 
можно задать так:


2
|
5 6
0
B
x x
x


 
Пример 1.4. Множество С всех точек на плоскости, составляющих круг с радиусом единица, можно задать как следующее множество пар вещественных чисел


,
x y :


2 2
( , ) |
1
C
x y
x
y




Порождающей процедурой, которая описывает способ получения элементов множества из уже полученных элементов либо других объектов. В этом случае элементами множества являются все объекты, которые могут быть построены с помощью такой процедуры. Например, множество D всех целых чисел, являющихся степенями двойки, может быть представлено порождающей процедурой, заданной двумя правилами: а)
1
D

; б) если m
D

, то 2m D


Характеристическим вектором.
1.3. Сравнение множеств
Множество
A
содержится во множестве
B
или множество
B
включает множество
A
, если каждый элемент из множества
A
является элементом множества
B
(обозначается
A
B

). В этом случае множество
A
называется

подмножеством
B
, а
B
– надмножеством
A
. Если A
B

и
A
B

, то
A
называется строгим (собственным) подмножеством
B
(обозначается
A
B

).
Если
A
не является подмножеством
B
, то это записывается как A
B

Таким образом, A
B

, если существует элемент
a
такой, что a
A

и
a
B

Пример 1.5.

 

1, 2, 3 1, 2, 3, 4

, но

 

1, 2, 5 1, 2, 3, 4

Множества
A
и
B
равны (обозначается
A
B

), если они являются подмножествами друг друга, то есть если A
B

и
B
A

Таким образом, доказательство равенства множеств
A
и
B
состоит из двух этапов:
1) Доказать, что
A
есть подмножество
B
2) Доказать, что
B
есть подмножество
A
Отметим, что из определения следует, что для любого множества
A
выполняются соотношения:
1)
A
A

;
2)
A
 
Мощность множества
A
обозначается как
A . Для конечных множеств мощность множества – это количество его элементов. Если A
B

, то множества
A
и
B
называются равномощными.
1.4. Операции над множествами
Рассмотренные ниже операции над множествами позволяют строить новые множества, используя уже существующие.
Объединением множеств
A
и
B
называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств
A
или
B
. Объединение множеств
A
и
B
обозначается
A
B

Сформулированное выше определение можно записать так:

A
B
x
x
A
 

или

x
B

Пример 1.6. Если


1, 2, 6, 7
A

, а


2, 5, 7
B

, то


1, 2, 5, 6, 7
A
B
 

Пересечением множеств
A
и
B
называется множество, состоящее из всех тех и только тех элементов, которые принадлежат и
A
, и
B
. Пересечение множеств
A
и
B
обозначается
A
B

. Это определение равносильно следующему:

A
B
x
x
A
 

и

x
B

Если A B
  
, то множества
A
и
B
называются непересекающимися.
Пример 1.7. Если


1, 2, 3, 4
A

,


2, 4, 6, 8
B

, то
 
2, 4
A
B
 
Разностью множеств
A
и
B
(обозначается
\
A B ) называется множество всех тех и только тех элементов
A
, которые не содержатся во множестве
B
Или, что то же самое,

\
A B
x
x
A


и

x
B

Пример 1.8. Если


1, 2, 3, 4, 5
A

,


2, 4, 6, 8
B

то


\
1, 3, 5
A B

Дополнение множества
A
, обозначаемое A , – это множество элементов универсума, которые не принадлежат
A
. Следовательно,

\
A U A
x
x U



и

x
A

Пример 1.9. Если U – множество положительных целых чисел, а


2, 4, 6, 8 ...
A

– множество всех чѐтных положительных чисел, то


1, 3, 5, 7, ...
A

– множество всех нечетных положительных чисел.
Симметрической разностью множеств
A
и
B
(обозначается
A B

или
A
B

), называется множество

 

\
\
A B
A B
B A
 

Пример 1.10. Если


1, 2, 3, 4
A

,
 
4, 5
B

, то


1, 2, 3, 5
A B
 
1.5. Диаграммы Венна
Диаграммы Венна – геометрический способ представления множеств.
Множества в диаграммах Венна изображаются внутренними частями кругов, их пересечениями, объединениями и т. д. Эти круги помещаются в прямоугольник, изображающий универсальное множество U . Точки, лежащие внутри

различных областей диаграммы, могут рассматриваться как элементы соответствующих множеств. Имея построенную диаграмму, можно заштриховать определенные области для обозначения вновь образованных множеств.
Диаграммы Венна иногда называют также диаграммами Эйлера или диаграммами Эйлера – Венна.
Приведенные на рис. 1.1–1.4 диаграммы Венна являются иллюстрациями операций объединения, пересечения, разности и симметрической разности множеств. Закрашенные области изображают множества
A
B

,
A
B

,
\
A B ,
A B

. На рис. 1.5–1.6 закрашенные области изображают множества A B C
 
и


A
C
B


. Используя диаграммы Венна, можно устанавливать равенство двух множеств.
Рис. 1.1.
A
B

Рис. 1.2.
A
B

Рис. 1.3. \
A B

Рис. 1.4.
A B

Рис. 1.5. A B C
 
Рис. 1.6.


A
C
B


Пример 1.11. Покажем, что


A
B
A
B

 
. Множество A
B

– дополнение множества
A
B

, представленного диаграммой на рис. 1.1.
Поэтому его изображает закрашенная область, показанная на рис. 1.7.
Множеству A соответствует закрашенная область на рис. 1.8., а множеству B – закрашенная область на рис. 1.9. Множеству A
B

соответствуют области, закрашенные на обеих предыдущих диаграммах. Поэтому на рис. 1.10. оно изображено более темной областью.

Получили, что и A
B

и A
B

одинаково изображаются на диаграмме
Венна, поэтому


A
B
A
B

 
Рис. 1.7. A
B

Рис.1.8. A
Рис. 1.9. B
Рис. 1.10.
A
B

1.6. Булеан

Для всякого множества
M
может быть образовано множество всех подмножеств для множества
M
. Его называют булеаном множества
M
и обозначают
2
M
:
2
{
:
}
M
X X
M


Пример 1.12. Булеан множества
 
,
a b состоит из четырех множеств:
 
,
2
{ , { }, { }, { , }}
a b
a
b
a b
 
Теорема 1.1. Для конечного множества
M
:
2 2
M
M

Доказательство. Индукция по M . Базис индукции: если
0
M

, то
M
 
и
 
2

 
. Следовательно,
 
0 2
1 2
2


   

Индукционный переход. Пусть равенство
2 2
M
M

выполняется для любого множества
M
при
M
n

Рассмотрим множество


1 1
, ...,
,
1
n
M
a
a
M
n


 
Положим




1 1
2 1
2 :
,
2 :
M
n
M
n
A
X
a
X
A
X
a
X








Имеем
1 2
2
M
A
A


, а их пересечение – пусто. Поэтому
1 2
2
M
A
A


. По построению множества
1
A
2
A
имеем
1 2
A
A

и


1
, ...,
1 2
n
a
a
A

. По индукционному предположению
1 2
n
A

Так как
2 1
A
A

, то
1 1
2 2
2 2 2
2
M
M
n
n
A

 
 


Теорема доказана.
Пусть задан конечный универсум U ,
1
U
n
 
. Пронумеруем элементы универсума:


1
, ...,
n
U
u
u

. Тогда любое подмножество
A
универсума можно задать его характеристическим вектором


1
, ...,
A
n
C
c
c

, где
1, если
,
0, если
i
i
i
u
A
c
u
A


 



Мы получили еще один способ задания множеств. Характеристический вектор называют также кодом множества или битовой шкалой. Пересечение, объединение и разность подмножеств универсума U являются подмножествами U . Код пересечения множеств
A
и
B
есть поразрядное логическое произведение их кодов. Код объединения множеств
A
и
B
есть поразрядная логическая сумма кода множества
A
и кода множества
B
. Код дополнения множества
A
есть инверсия кода множества
A
. В большинстве
ЭВМ для этих операций есть соответствующие машинные команды и поэтому операции над небольшими множествами выполняются весьма эффективно.
Пример 1.13. Пусть


8,
(11001100),
10101000
A
B
U
C
C



. Тогда для множеств
,
,
X
A
B Y
A
B Z
A
 
 

имеем:






10001000 ,
11101100 ,
00110011
X
Y
Z
C
C
C



1.7. Свойства операции над множествами
Пусть задан универсум U . Тогда для любых множеств , ,
A B C
U

выполняются следующие свойства.
1. Коммутативность:
A
B
B
A
  
,
A
B
B
A
  
2. Ассоциативность:
,
(
)
(
)
A
B
C
A
B
C





3. Дистрибутивность:
4. Идемпотентность:
A
A
A
 
,
A
A
A
 
5. Свойства поглощения:
(
)
A
B
A
A

 
,
(
)
A
B
A
A

 
6. Свойства нуля:
A
A
 
,
A
  

7. Свойства единицы:
A
U
U
 
,
A
U
A
 
8. Инволютивность:
A
A

9. Законы де Моргана:
A
B
A
B
  
,
A
B
A
B
  
10. Свойства дополнения:
A
A U
 
,
A
A
  
11. Выражение для разности:
\
A B
A
B
 
12. Выражение для симметрической разности:
(
) \ (
)
A B
A
B
A
B
 


В справедливости каждого из перечисленных свойств можно убедиться различными способами. Например, нарисовать диаграммы Венна для левой и правой частей равенства и убедиться, что они совпадают. (Этот способ был нами использован в п. 1.5 для установления равенства A B A B
  
.)
Можно также для установления равенства использовать метод двух включений. Рассмотрим для примера равенство
A
A
A
 
Для доказательства возьмем произвольный элемент
x
, принадлежащий левой части равенства, x A A
 
. По определению операции объединения

имеем: x A

или x
A

. В любом случае x A

. Таким образом, установлено, что A
A
A
 
. Покажем обратное включение A
A
A
 
. Взяв произвольный элемент x A

, по определению операции объединения множеств имеем:
x
A
A
 
. Поэтому A
A
A
 
Таким образом, мы установили, что A
A
A
 
и
A
A
A
 
Следовательно, по определению равенства множеств, имеем
A
A
A
 
Полученные теоретико-множественные тождества можно использовать для доказательства новых тождеств преобразованием левой части к правой или

наоборот. Такой метод доказательства часто называют методом эквивалентных преобразований.
Пример 1.14. Докажем методом эквивалентных преобразований тождество
(
)
A
A
B
A
B


 
Решение. Пользуясь тождествами 1–12, преобразуем левую часть:


(
)
(
)
(
)
(
)
A
A
B
A
A
A
B
U
A
B
A
B
U
A
B





 



  

Установленные нами тождества позволяют упрощать различные сложные выражения, содержащие множества, подобно тому, как тождественные преобразования делаются в алгебре. Рассмотрим примеры.
Пример 1.15.
1.
 




A
B B
A
B
B
A
B
B
A
B
B
A
B

 
       


2.
Согласно свойству ассоциативности два множества
(
)
A
B
C


и
(
)
A
B
C


равны. Условимся это единственное множество обозначать через
A
B
C
 
. Ассоциативный закон утверждает, что не играет роли, как расставить скобки в этом выражении. При помощи математической индукции этот результат можно обобщить следующим образом. Все множества, получаемые с помощью операции объединения из заданных множеств
1 2
,
, ...,
n
A A
A
, взятых в фиксированном порядке, равны друг другу. Множество, получаемое таким образом из
1 2
,
, ...,
n
A A
A
, мы будем обозначать через
1 2
n
A
A
A

 
или через
1
n
i
i
A



Точно так же при рассмотрении пересечений множеств будем использовать записи
1 2
n
A
A
A

 
и
1
n
i
i
A

