Дискретка / 1 - Множества

1. Множества

Основные понятия

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

Под множеством Г. Кантор понимал «вообще всё многое, которое возможно мыслить как единое, т.е. такую совокупность определённых элементов, которая посредством одного закона может быть соединена в одно целое». Мы же будем понимать под множеством некую совокупность объектов, объединённую некоторым свойством (признаком). Объекты, составляющие множество, принято называть его элементами. Множества обозначают прописными, а их элементы – строчными латинскими буквами, при необходимости, используя индексы:

множества: A, B3, Xβ, …; элементы: a, bn, x5….

Принадлежность элемента a множеству A, обозначается символом (от греч. εστι –

«есть», «быть»):

a A и читается: «a принадлежит A» или «элемент a из множества A».

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

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

множества A называется его мощностью и обозначается через

A . Общеизвестными

примерами бесконечных множеств являются множества натуральных, целых, рациональных и действительных чисел, имеющих стандартные обозначения: N, Z, Q, R. Мощность множества натуральных чисел, называется счётной мощностью, а множества, имеющие такую же мощность (равномощные множеству N), называются счётными.

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

Множество может быть заданоперечислением его элементов:

A= {a1, a2, a3, a4};

через другие уже известные множества, например с помощью, так называемых, индексных множеств:

X xi

: i I ,

где I – индексное множество, элементами которого помечены элементы множества X. Индексное множество может быть любым. Но поскольку одному элементу индексного множества ставится в соответствие один элемент определяемого с помощью него множества, их мощности будут одинаковы. Например, конечное индексное множество

1

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

следующим образом:

X xi

: i 1, n .

I N n 1

1,2, , n

1,

n

, множество X задаётся

заданием определяющего свойства (признака), задаваемого предикатом.

Предикат – повествовательное предложение об элементах заданного множества, которое при фиксировании переменных превращается в высказывание (становится истинным либо ложным). Записывается предикат: P(x), где x – переменная из некоторого множества. При некоторых значениях x P(x) принимает значение И, при других – Л. Так, множество может быть задано с помощью предиката следующим образом:

A x :

P x

.

Иногда при предикате ставится нижний индекс, в котором записывается определяемое с помощью него множество: PA(x). Например, PA(x) – определенный на множестве целых чисел предикат, означающий: x – целое число, тогда A = {x: x – чётное число} состоит только из чётных чисел, или же, поскольку известно, на каком множестве определён предикат, может быть записано

M

x Z : P x

или

M

x : x Z

&

P x

.

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

Например, так может быть заданы числа Фибоначчи:

M = {ak: ak+2 = ak + ak+1, a1 = a2 = 1, k ≥ 1}.

Если каждый элемент множества A принадлежит также и множеству B, то говорят, что множество A является подмножеством множества B, A включается (содержится) в B

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

A B a : a A a B. Два множества называются равными, если они состоят из одинаковых элементов,

или, то же самое, если каждое из них содержится в другом: A B A B & B A .

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

Исходя из определения подмножества, можно заключить, что само множество B является подмножеством самого себя, т.е. можно записать, что B B . Чтобы подчеркнуть тот факт, что рассматриваемое подмножество A множества B может совпадать с множеством B, отношение «быть подмножеством» записывают также A B или B A.

Отношения и называют отношениями включения, а и – обратного включения.

В каждой конкретной задаче все рассматриваемые объекты принято считать принадлежащими, так называемому, универсальному множеству (универсуму), которое будем обозначать через . Таким образом, a : a и A : A . Кроме того, в некоторых задачах необходимо использование так называемого пустого множества, обозначаемого через , которое не содержит ни одного элемента, т.е. a : a , но

A : A .

2

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

обозначается через

2

. Таким образом,

A : A 2

.

Булеан может быть построен

любого множества, например, если A = {a, b, c}, его булеан будет следующим:

2

A

, a , b , c , a,b , a, c , b, c , a,b, c .

Множества

принято

наглядно

изображать

диаграммами

B

Эйлера-Венна,

на

которых прямоугольником

обозначается

A

универсум, а внутри него – кругами Эйлера – рассматриваемые

множества. Так,

случай,

когда A

является

собственным

Рис. 1

подмножеством множества B, изображён на рис. 1.

При рассмотрении произвольных множеств, когда отношения

между множествами не оговариваются, рассматривается такое их

A

B

расположение, когда ни одно из множеств не является

подмножеством другого, и все они, как попарно, так и несколько, и

С

все множества имеют некоторые общие элементы. Т.е. если

рассматриваются произвольные множества A, B

и C, они

Рис. 2

изображаются на диаграмме Эйлера-Венна, как это показано на рис. 2.

и

для

Ω

Ω

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

Все операции над множествами сводятся к действиям над определяющими их предикатами, т.е. к логическим операциям.

Основными операциями алгебры множеств являются:

1) пересечение, порождающее из множеств A и B новое множество, обозначаемое как A B , содержащее только те элементы, которые принадлежат и A, и B одновременно: A B x : x A & x B ; 2) объединение, с помощью которого из множеств A и B получаем новое множество

A B , состоящее из элементов, принадлежащих хотя бы одному из множеств A или B: A B x : x A x B ; 3) разность, в результате которой из множеств A и B получается множество A \ B тех

элементов A, которые не принадлежат при этом множеству B:

A \ B x : x A & x B .

Иначе разность A \ B называется дополнением множества B во множестве A.

Множества,

пересечение

которых

пусто

( A B ),

называются

непересекающимися.

Из приведённых определений следуют, в частности, следующие соотношения:

A B A,	A B B,	A A B, B A B,		A B A B,
	A A A,		A A A,

A B A B A & A B B .

Каждое из условий A B A , A B B достаточно для включения A B , т.е.

а) A B A A B ,

б) A B B A B.

Действительно, от противного:

A B x x A & x B x x A & x A B A A B,

что противоречит условию A B A , т.е. утверждение а) – верно.

3

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

A B A B A	и	A B A B B,
а значит
A B A A B B.

Разность

\ A

называется дополнением множества A и обозначается символом A : A \ A x : x A .

Кроме того, существует операция симметрической разности множеств, обозначаемая через A B, которая содержит только те элементы, которые принадлежат лишь одному из множеств A и B, но не обоим одновременно, т.е.

A B x : x A & x B x A & x B .

Симметрическую разность также называют суммой по модулю

2 и

обозначают

A B .

Ω

Ω

На рисунке 3 представлены диаграммы

A

B

A

B

Эйлера-Венна для введённых операций над

множествами.

Множество 2

с операциями

,

и

a) пересечение

б) объединение

образуют алгебру множеств 2

;

, , .

Ω

Ω

Основные законы алгебры множеств

A

B

A

(свойства главных операций):

1) инволюнтность (дополнения):

в) разность

г) дополнение

A A;

и :

Ω

коммутативность

2)

A B B A,

A

B

3)

A B B A;

ассоциативность и

:

д) симметрическая

4)

A B C A

B C

A B C ,

разность

A B C A B C A B C ;

5)

Рис. 3

дистрибутивность

к и

к :

6)

A B C A B A C ,

7)A B C A B A C ;

законы де Моргана:

8)

9)

10)

11)

12)

13)

A B A B ,

A B A B ;

идемпотентность и :

A A A,

A A A;

законы дополнения:

A A ,

A A ;

4

14)

15)

16)

17)

18)

19)

существование нуля и единицы (свойства операций с

A A, A , A , A A; поглощение:

A A B A,

A A B A;

и ):

20)закон исключения разности:

A \ B A B .

21)закон исключения симметрической разности (суммы по модулю 2):

A B A B A \ B B \ A A B \ A B .

	свойства суммы по модулю 2:
22)	A B B A,
23)	A B C A B C A B C ,
24)	A B C A B A C ,
25)	A A,
26)	A A ,
27)	A A ,

Способы проверки (доказательства) равенства множеств

Равенство двух множеств может быть проверено одним из следующих способов:

1)	построение диаграмм Эйлера-Венна;
2)	метод двух включений (логический);
3)	метод индикаторных функций;
4)	преобразования в алгебре множеств.
	Рассмотрим применение каждого из способов на примере –
докажем первый закон дистрибутивности, т.е.
	A B C A B A C .	A	B
1)	Диаграммы Эйлера-Венна.
	Построенная для каждой из частей указанного закона диаграмма		С
	Эйлера-Венна представлена на рис. 4. Различается лишь порядок		Рис. 4
	рассуждений при её построении.

Ω

2)Метод двух включений (логический).

Основывается на определениях равенства и включения множеств. С использованием

определений операций над множествами сводится к алгебре логики (высказываний).

A B C x : x A & x B C x : x A & x B x C

x : x A & x B x A & x C x : x A B x A C

A B A C .

3)Метод индикаторных функций.

Индикаторная функция (индикатор или характеристическая функция) множества A –

функция IA(x), такая, что

5

Очевидно, что

A

B

x :x :

I

	1,
I A	x
	0 ,

A	x I	B	x

.

x A , x A.

Поэтому доказательство равенства

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

Действиям над множествами соответствуют действия над их индикаторами. Так

справедливы следующие равенства:

x :

I

n

x I

x ;

A

A

I

x 1;

x 0;

I

I

A

x 1 I

A

x ;

I

A B

x I

A

x I

B

x ;

I

A B

x I

A

x I

B

x I

A

x I

B

x ;

I

A\ B

x I

A

x 1 I

B

x ;

I

x I

x I

x

I

x I

x .

x I

x 2I

2

A B

A

B

A

B

A

B

Итак, докажем, что

I A B C

I A B A C .

I

A B A C

I

A B

I

A C

I

A B

I

A C

I

A

I

B

I

A

I

C

I

A

I

B

I

A

I

C

I

A

I

B

I

C

I

B

I

C

I

A

I

B C

I

A B C

.

4) Преобразования в алгебре множеств.

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

Докажем данным способом закон 27.

A A \ A		\ A A.
(21)	(15,17)

Под знаками равенства в скобках указаны номера применяемых законов. Последнее

равенство цепочки является определением операции дополнения.

6