kontrolnye / Дискретка / Конспект лекций / sets

Тема ¹1. Множества и операции над ними

Содержание

Способы задания множеств	2
Операции над множествами	4
Предметный указатель	8

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель

Одним из основных, исходных понятий математики является понятие множества и его элементов. Интуитивное определение Кантора: множество — это объединение в одно общее объектов, хорошо

различаемых нашей интуицией или нашей мыслью .

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

m M ( — стилизация первой буквы греческого слова быть). N — множество натуральных чисел (0,1,2 . . . )

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

A и B равны, если их элементы совпадают , т.е. A B и A B.

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

Множества могут быть конечными (т.е. состоять из конечного числа элементов) и бесконечными. Число элементов в конечном множестве M называется мощностью M и обозначается |M|.

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

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

Множество может быть задано перечислением (списком элементов) или указанием их свойств (порождающей процедурой). Списком можно задать лишь конечные множества M = 0, 1, . . . , 9.

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

Пример.

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель

1.M4 — множество всех чисел вида π2 ± πk, где k N. Исходные объекты — натуральные числа, а порождающая процедура — формула.

2.M2n = 1, 2, 4, 8, 16 . . . Порождающая процедура определяется двумя правилами:

•1 M2n;

•если m M2n, то 2m M2n. (Правила, описанные таким образом, называются индуктивными или рекурсивными).

3.Mπ. Пусть имеется процедура вычисления цифр разложения числа π в бесконечную десятичную дробь:

π= 3, 1415926536

По мере вычислений будем образовывать из последовательно стоящих цифр трехразрядные числа 314,159,265 и т.д.

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

спомощью операций над множествами.

Вслучае, когда свойство элементов M может быть описано коротким выражением P (x), M задается при помощи обозначения M = {x|P (x)}.

Пример.

1.M2n = {x|x = 2k, где k N}

2.M4 = {x|x = π2 ± πk, где k N}

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

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель

свойством, и следовательно является элементом данного множества или нет. Например, для M2n разрешающей процедурой может быть любой метод разложения целых чисел на простые множители. В этом примере разрешающая процедура не является порождающей. Однако ее легко сделать таковой: берем последовательно все натуральные числа и раскладываем на простые множители, те числа, которые не содержат множители6= 2, включаем в M2n. С другой стороны, порождающая процедура может не быть разрешающей.

Пример.

MG — футбольная команда Спартак. К какому виду принадлежит его задание? (ни к какому). Можно описать MG — это множество лиц с удостоверением. Разрешающая процедура для такого

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

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

1.Объединением множеств A и B(A B) называется множество, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств A, B. Символически это можно записать так:

A B = {x|x A или x B}.

A B = {x|x A или x B}.

Для проведения доказательств в алгебре множеств применяют диаграммы Эйлера. Множество A B изобразится заштрихованной областью:

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель

i=1

S Φi —

18

	U
A	B

Аналогично определяется объединение произвольной (в том числе бесконечной) системы множеств. Если система содержит небольшое количество множеств, то их объединение описывает-

ся явно: A B C D и т.д. В общем случае используются обозначения	k
	Ai или	A, где
∞	S	S
	i=1	A S

S = {A1, A2, . . . , Ak}, S Ai, если S — бесконечная система и ее множества занумерованы подряд

i=1

натуральными числами, S Ai — когда совокупность индексов множества задана множеством I.

i=I

Пример.

1. A = {a, b, d}, B = {b, d, e, h}, A B = {a, b, d, e, h}.

2. Обозначим футбольные команды высшей лиги через Φi: M7 = {Φ1, Φ2, . . . , Φ18}, тогда множество всех футболистов высшей лиги. Всегда A (A B), но неверно A (A B).

2. Пересечением множеств A и B(A ∩ B) называется множество A ∩ B = {x|x Aиx B}.

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель

	U
A	B

Пример.

1. A = {a, b, d}, B = {b, d, e, h}, A ∩ B = {b, d}.

18

2. T Φi = , более того, для любых i и j Φi ∩ Φj =

i=1

Заметим, что в общем случае, если A = {a, b}, B = {b, c}, C = {c, d}, то A∩B∩C = , однако все попарные пересечения пусты. Система множеств, в которых все попарные пересечения множеств , называется разбиением множества V всех элементов этих множеств, а множесства такой системы называются классами разбиения. Всякий элемент V входит в один и только один класс разбиения. Например, M7 является разбиением множества всех футболистов высшей лиги; классы этого разбиения – команды.

3.Разностью множеств A и B(A\B) называется множество всех тех и только тех элементов A, которые не содержатся в B.

A\B = {x|x A и x / B}.

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель

U

AB

Вотличии от двух предыдущих операций разность, во-первых, строго двуместна, а во-вторых, некоммутативна: A\B 6= B\A Если A\B = , то A B.

Пример.

1.A = {a, b, d}, B = {b, d, e, h}, A\B = {a}, B\A = e, h.

2.M7\M6 — множество всех команд высшей лиги, за исключением ”Спартака”. Более правильная

18

запись M7\M6 или T Φi\M6.

i=1

4.Дополнением множества A называется множество всех элементов, не принадлежащих A (но принадлежащих V ), A = V \A. Множество V должно быть задано.

U

A

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

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель

Предметный указатель

множество, 2 бесконечное, 2 дополнение, 7 конечное, 2 мощность, 2 объединение, 4 пересечение, 5 пустое, 2 равенство, 2 разность, 6 элемент, 2

перечисление, 2 подмножество, 2 процедура

порождающая, 2 разрешающая, 3 распознающая, 3

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель