- •Глава 1
- •§1.Множества. Определения.
- •§2 Операции на множествами.
- •§3 Прямое произведение множеств.
- •§4 Отношение. Определения.
- •§5Области определения и значений. График отношения.
- •§6 Основное свойства отношений.
- •§9 Разбиения.
- •§7 Отношение эквивалентности.
- •§8 Классы эквивалентности.
- •§10 Отношение порядка.
- •§11 Наибольший и максимальный, наименьший и минимальный элементы.
- •§12 Граф и отношения.
- •§13 Матрица инцидентности вершин графа. Матрица отношения.
- •§14 Мульти графы и сети.
- •§15 Специальные графы отношение порядка.
- •§16 Функции.
§2 Операции на множествами.
Определим операции, позволяющие из двух подмножеств строить новое.
Объединение (сумма). Обозначается AÈB, соответствует союзу «или» (в неисключающим смысле).
AÈB={x|xÎA или xÎB}
Пересечение (произведение). Обозначается AÇB, соответствует союзу «u».
AÇB={x|xÎA, xÎB}
Разность. Обозначается A\B. Это множество тех элементов множества A, которые не принадлежат множеству B.
A\B={xÎA| xÏB}
Дополнение. Обозначается `A=u\A
Для лучшего понимания этих операций используют диаграммы Эйлера – Венна. Универсальное множество изображается в виде прямоугольника, а подмножества в виде кругов.
AÈB
AÇB
A\B
Теорема. Для любых подмножеств A, B, C универсального множества u справедливы следующие равенства
AÈB = BÈA 1’ AÇB=BÇA
AÈ(BÈC)=(AÈB)ÈC 2¢ AÇ(BÇC)=(AÇB)ÇC
AÈ(BÇC)=(AÈB)Ç(AÈC) 3¢ AÇ(BÈC)=(AÇB)È(AÇC)
AÈ(AÇB)=A 4¢AÇ(AÈB)=A
È
=
Ç
5¢Ç
=
È
AÈA=A 6¢AÇA=A
AÈ =u 7¢AÇ =Æ
AÈu=u 8¢AÇÆ=Æ
AÈÆ=A 9¢AÇu=A
10 =A
Эти равенства носят названия: 1,1¢ - коммутативность сложения и умножения; 2,2¢ - ассоциативность сложение и умножения; 3,3¢ - дистрибутивность 4,4¢-законы поглощения, 5,5¢-законы де Моргана; 6,6¢ идемпотентность; 10 – закон снятия двойного отрицания.
Докажем, например, равенство 5.
Пусть xÎÈ , значит, xÏAÈB, т.е. xÏA и xÏB, xÎ и xÎ , откуда xÎ Ç . Обратно. Пусть xÎ Ç , значит, xÎ и xÎ , т.е. xÏA и xÏB, т.е. xÏAÈB т.е. xÎÈ .
Заметим, что равенства левого столбца получаются из равенства правого столбца заменой символа Ç («крышки») на символ È («чашки») и наоборот. Символ пустого множества Æ заменяется символом универсального множества u и наоборот.
§3 Прямое произведение множеств.
Пусть A, B – два множества. Их прямым (декартовым) произведением называется множество упорядоченных пар AхB=( (x,y)| xÎA, yÎB).При этом, если (x,y)=(u,v) то x=u, y=v. Будем называть x первой координатой, а y- второй координатой упорядоченной пары. Аналогично определяются упорядоченные тройки (x,y,z) и т.д. Вообще, пусть A1,A2,..Ak – множества. Тогда их прямым произведением назовем множество упорядоченных последовательностей (x1,x2,..xk) таких, что xiÎAi, i=1,2…k.
В частности, если A=B, то AхA будем обозначать A2, и аналогично, если Ai=A, то A1хA2.. хAk=Ak.
Замечание 1. Если R – множество действительных чисел, т.е. точек числовой прямой, то R2 и R3–это соответственно множества точек плоскости и пространства.
Замечание 2. Пусть E – множество, состоящие из двух элементов 0 и 1. Тогда En – множество последовательностей из n элементов, каждый из которых 0 либо 1.
Теорема. Пусть A={a1,..an}, B={b1,.. bm}, т.е. |A|=n |B|=m.Тогда прямое произведение AхB содержит nхm элементов. |AхB|=|A||B|
Доказательство. Элементы множества AхB запишем в виде таблицы:
(a1,b1) (a1,b2) (a1,bm)
(a2,b1) (a2,b2) (a2,bm)
……. …….. ………
(an,b1) (an,b2) (an,bm)
Откуда следует утверждение теоремы.
Следствие 1. |A1хA2х..Ak|=|A1|х|A2|..|Ak|
Следствие 2. |En|=2n
Задачи.
В следующих задачах нужно доказать равенство множеств:
A={y=x2| xÎR, x¹0} и R+
Решение. Пусть yÎA, y=x2, x¹0, т.е. yÎR+
Обратно.
Пусть yÎR+,
тогда y=(
)2=x2,
где x=
,
xÎR+,
x¹0,
т.е. yÎA.
A={6n| nÎZ}, B={3m| mÎZ}, C={2k| kÎZ}; A=BÇC
Решение. Пусть xÎA; x=6n, nÎZ. Тогда x=3m, m=2n и xÎB. Аналогично, x=2k, k=3n и xÎC. ИтакA£BÇC. Обратно. Пусть xÎBÇC. Тогда x=3m=2k. 3m делится на 2, и поскольку 3 и 2 взаимно просты, то m=2n. Значит x=3m=3*2n=6n. xÎA
A={2x| xÎQ} и Q
A={2x| xÎR} и R+
A={lgx| xÎR+} и R
A={30n| nÎZ}, B={5m| mÎZ}, C={3l| lÎZ}, D={2k| kÎZ}
A=BÇCÇD
(AÇBÇC)È( ÇBÇC)È È
=u
Решение (AÇBÇC)È( ÇBÇC)=(AÈ )Ç(BÇC)=uÇ(BÇC)=BÇC
(BÇC)È(
È
)=(BÇC)È(Ç
)=u
(AÇBÇX)È(AÇBÇCÇXÇY)È(AÇXÇ )=AÇBÇX
(AÇBÇCÇ
)È(
ÇC)È(
ÇC)È(CÇX)=C[(AÇB)È(AÇC)È( Ç ÇY)]ЗЗЗИЗЗИЗЗ
=
=(AÇB)È( Ç Ç ÇY)
Ç
ÈB=
ÈB
В следующих задачах надо описать указанные множества.
В заданиях 12, 13, 14 универсальным является множествоZ.
Пусть A={2n| nÎZ}, B={2n-1| nÎZ}, C={xÎZ| x<5}
Описать множества , È , , A\ , C\(AÈB)
Решение A – множество четных, а B – нечетных целых чисел. AÈB=Z, значит =B, È =Æ ={xÎZ| x³5}. Тогда A\ – это множество четных чисел меньше 5: и т.к. AÈB=Z, то C\(AÈB)=Æ.
A={xÎZ+| x=2y, yÎZ}, B={xÎZ+| x=2y+1, yÎZ}, C={3y| yÎZ+}
Описать множества AÇB, BÇC, B\C.
Описать множества Ç , AÈ , AÇBÇC из задачи 13.
Доказать каждое из следующих утверждений для произвольных множеств A, B, C:
Если A≤B и B≤C, то A≤C
Если A≤B и B<C, то A<C
Если A<B и B≤C, то A<C
Если A<B и B<C, то A<C
Решение. Докажем, например, b) Рассмотрим случай A=B. т.к. B<C, то существует xÎC и xÏB=A, т.е. A<C. Пусть теперь A<B, значит, существует xÎB и xÏA. Поскольку B<C, то xÎC, т.е. опять A<C.
Какие из следующих утверждений верны для всех множеств A, B, C?
Если AÏB и BÏC, то AÏC
Неверно. Например: A=1, B={0,2,3}, C={1,3,4}
Если A¹B, B¹C, то A¹C. Неверно. Например, если A=C¹B
Если AÎB и неверно, что B≤C, то AÏC
Н
еверно
утверждение как показывает следующий
рисунок
А
A – элемент пересечения BÇC
Если A<C и B≤C, то неверно, что C≤A.
Верное утверждение. На основании 15с A–собственное подмножество C, т.е. существует xÎC и xÏA.
Если A≤B и BÎC, то AÎC. Неверное утверждение. Пусть A={1}, B={1,2}, C={{1,2},3}
Тесты по теме «Множества».
Тест №1.
Задание 1.
ЕслиA=(-¥, -2), B=(-3,+¥), то AÈB:
(-3,-2)
(-3,-2]
(
- ¥,+¥)(
-¥,-3)È(-2,+¥)
П
-3
-2
равильный ответ c):
Задание 2.
Если A – множество четных чисел, B – множество чисел кратных 6, то ÇB есть
Множество A
Множество B
Æ
Множество чисел кратных 12.
Правильный ответ c), поскольку – множество нечетных чисел.
Задание 3.
AÇ( ÈB)=
AÈB
AÇB
Æ
ÈB
Правильный ответ b): AÇ( ÈB)=(AÇ )È(AÇB)=ÆÈ(AÇB)=AÇB
Задание 4.
Если A≤B, то ( несколько ответов).
AÈB=B
AÈB=A
AÇB=A
³
Правильный ответ a),c),d). Проверим d). Пусть xÎ , xÏB, значит, xÏA, т.е. xÎ
Задание 5.
Декартовым произведением AхB множества A={-1,1} и B={1,5} является множество:
(-1,5)
(-1,1),(1,5)
(-1,1), (-1,5), (1,1), (1,5)
(1,-1), (5,-1), (1,1), (5,1)
Правильный ответ c)
Тест №2.
Задание 1.
Если C=(-1,1)È(2,+¥), то
(1,2)
(-¥,-1)È(1,2)
(-¥,-1]È[1,2]
(-¥,+¥)
Правильный ответ c).
Задание 2.
Если A – множество квадратов, B–множество ромбов, то AÇB есть:
Множество A
Множество B
Æ
Множество прямоугольников
Правильный ответ a)
Задание 3.
(A\B)ÈB=
A
B
AÈB
AÇB
Правильный ответ с), т.к. (A\B) ÈB=(AÇ )ÈB=(AÈB) Ç( ÈB)=(AÈB) Çu =AÈB
Задание 4.
Если AÇB=Æ, то ( несколько ответов)
A≤
B≤
AÈB=u
BÈ(AÇB)=B
Правильные ответы: a),b),d)
Покажем для a). ПустьxÎA, т.к. AÇB=Æ, то xÏB, т.е. xÎ
Задание 5.
(AхB)Ç(CхD)=
(AÇC) х (BÇD)
(AхC)È(AхD)È(BхC)È(BхD)
(AхC)Ç(BхD)
(AхC)È(BхD)
Правильный ответ a).
Пусть (x, y)Î(AхB)Ç(CхD), т.е. xÎA и xÎC; yÎB и yÎD т.е. xÎAÇC, yÎ(BÇD).И обратно, если (x, y)Î(AÇC)х(BÇD), то xÎAÇC, yÎBÇD. Значит, (x, y)Î(AхB)Ç(CхD)
