DM_Mnozhestva (1)

Пример решения задания 1.5.
Доказать,	что для любых множеств А, В, С выполнение включения А \ В С влечёт выполне-
ние включения С А А В С .
Решение.	Возьмем множества А, В, С находящиеся		в общем положении:	А 1, 2, 4, 5 ,
B 4, 5, 6, 7 ,	C 2, 3, 5, 7 . В нашем случае,	как и при решении предыдущих заданий, цифры
обозначают соответствующие списки переменных.
Тогда А \ В 1, 2 из включения A \ B C следует, что список 1 пуст, A 2, 4, 5 . Рассмот-
рим C A и	A B C 2, 3, 4, 5, 7 .	Так как	3, 4, 7 2, 3, 4, 5, 7 ,	то включение

C A A B C доказано в предположении, что выполнено включение А \ В С .

Задание 1.6. Для произвольных множеств А, В, Н проверить, является ли выполнение включения α необходимым и достаточным условием выполнения равенства β .

11

Пример решения задания 1.6.

Для произвольных множеств А, В, Н проверить, является ли выполнение включения

А В Н необходимым и достаточным условием выполнения равенства А	Н В \ А Н \ А .
Решение. Рассмотрим множества А, В, Н : А 1, 2, 4, 5 , B 4, 5, 6,	7 , H 2, 3, 5, 7 . В

нашем случае, как и при решении предыдущих заданий, цифры обозначают соответствующие списки переменных.

12

1. (Достаточность) Посмотрим, какие множества мы получим, если потребуем выполнения
условия А В Н . Имеем А В 1, 2, 4, 5, 6, 7 и, чтобы было выполнено включение		А В Н ,
списки 1, 4, 6 должны быть пусты, и множества А, В, Н будут таковы: А 2, 5 ,		B 5, 7 ,
H 2, 3, 5, 7 . Тогда B \ A H \ A 7 3, 7 3, 7 , A H B \ A H \ A выполнено.
2. (Необходимость) Посмотрим, какой вид примут множества А 1, 2, 4, 5 ,	B 4, 5, 6, 7 ,
H 2, 3, 5, 7 , чтобы выполнялось равенство А Н В \ А Н \ А .

А Н 1, 3, 4, 7 , В \ А Н \ А 6, 7 3, 7 3, 6, 7 .

Для выполнения равенства А Н В \ А Н \ А нужно, чтобы списки 1, 4 и 6 были пусты, и мы приходим к тем же множествам, что и в п.1, т.е. А 2, 5 , B 5, 7 , H 2, 3, 5, 7 .

Видим, что в этом случае А В 2, 5, 7 H .

Значит, доказано, что для любых множеств А, В, Н выполнение включения А В Н является необходимым и достаточным условием выполнения равенства А Н В \ А Н \ А .

Задание 1.7. Решить систему соотношений относительно множества Х и указать условия совместности системы.

13

Пример решения задания 1.7.
Решить задание 1.7 для системы						2
					1		4	В
В С Х А				А
						3
	Х \ С А В
						С
С А В.						7	8
						6
Решение.						5
I.	Построим множества	общего	положения			9	Х
А, В, Х и множество С (рис. 3) такие, что С А В и
множества С , Х находятся в общем положении.						Рис. 3
Символом 1 обозначим список элементов множества А , не попавших ни в одно из множеств
В , С, X ,	символом 7 – список элементов, попавших в каждое из множеств						А, В, С, Х и т.д. Будем
иметь: А 1, 2,3,5, 6, 7 , B 2, 3, 4, 6, 7,8 ,			C 3, 7 ,	X 5, 6, 7,8,9 .
1.	B C 2, 4, 6,8 , X A 5, 6, 7 . Эти множества равны в силу первого уравнения систе-
мы, значит, списки элементов 2,		4, 5, 7 и 8 пусты. Получили: А 1, 3, 6 ,					B 3, 6 ,	C 3 ,

X6, 9 .

2.X \ C 6,9 , A B 3, 6 . Данные множества равны в силу второго уравнения системы, следовательно, списки элементов 3 и 9 пусты, и наши множества примут вид:

А 1, 6 ,	B 6 ,	С ,	Х 6 .
	14

Видим, что Х В , В А, С .

II. Проверим, что множество Х В является решением исходной системы.

Если С и В А , то	С А В и можно записать: В b ,	A a, b , где a, b – списки
элементов.
Пусть X B b , тогда: B C B \ C b , X \ C X b ,		X A A B b .

Видим, что все соотношения системы удовлетворяются, т.е. множество Х В является решением исходной системы при выполнении условий В А, С .

Ответ: Х В , В А , С .

Задание 1.8. Решить систему уравнений относительно множества Х и указать условия совместности системы или доказать её несовместность.

15

Пример решения задания 1.8.

	А Х В \ С
Решить задание 1.8 для системы
	С Х А Х .
	В \ Х А \ Х

Решение. Построим множества общего положения А, В, С, Х , являющиеся подмножествами универсального множества U . Для этого выпишем все 16 различных двоичных наборов размерности 4. Пусть разряды этих наборов слева направо соответствуют множествам А, В, С, Х (табл. 1). Симво-

лом 1 обозначим список элементов универсального множества U , не попавших ни в одно из множеств А, В,С, Х (соответствующая строка состоит из нулей), а символом 4 – список элементов, не по-

павших ни в А , ни в В , но попавших в С и Х (в четвёртой строке нули относятся к столбцам А и В, единицы к столбцам С и Х ) и т.д.

Таблица 1

№	А	В	С	Х	№	А	В	С	Х
1	0	0	0	0	9	1	0	0	0
2	0	0	0	1	10	1	0	0	1
3	0	0	1	0	11	1	0	1	0
4	0	0	1	1	12	1	0	1	1
5	0	1	0	0	13	1	1	0	0
6	0	1	0	1	14	1	1	0	1
7	0	1	1	0	15	1	1	1	0
8	0	1	1	1	16	1	1	1	1

Имеем следующие списки:

16

U 1, 2, 3, 4, 5, 6, 7,8, 9,10,11,12,13,14,15,16 , A 9,10,11,12,13,14,15,16 ,

В {5, 6, 7,8,13,14,15,16}, C 3, 4, 7,8,11,12,15,16 ,				X {2, 4, 6,8,10,12,14,16} .
1.	А Х 2, 4, 6,8,9,11,13,15 ,	B \ C 5, 6,13,14 .		Эти множества	равны в силу первого
уравнения	системы, значит, списки	элементов 2,	4, 5,	8, 9, 11, 14 и	15 пусты. Получили:
А 10,12,13,16 , B 6, 7,12,16 , C 3, 7,12,16 ,			X 6,10,12,16 .

2. C X 12,16 , A X 6,10,12,13,16 . Данные множества равны в силу второго урав-

нения системы, следовательно, списки элементов 6, 10, 13 пусты и наши множества примут вид
А 12,16 ,	B 7,16 ,	X 12,16	, C 3, 7,12,16 .
3. B \ X 7 , A \ X , в силу третьего уравнения системы получаем, что список 7 пуст, и
C 3,12,16 , B 16 ,		А 12,16 X , U 1, 3,12,16 .
Видим, что X A ,		B A C U
II. Проверим, что множество X A является решением исходной системы.
Если	выполнены	включения	B A C U , то можно записать:	B b ,	A a, b ,
C a, b, c ,	U a, b, c, u , где a, b, c, u списки элементов.

Пусть X A a, b , тогда A X B \ C , B \ X A \ X , C X a, b A X .

Видим, что все уравнения системы удовлетворяются, т.е. множество X A является решением исходной системы при выполнении включений B A C U .

Ответ: X A , B A C U .

2. Бинарные отношения двух множеств (Графики)

Декартовым (прямым) произведением множеств А1, A2 ,..., An называется множество

A1 A2 ... An a1, a2 ,..., an a1 A1, ..., an An .

Проекцией вектора a1, a2 ,..., an на ось i называется координата (компонента) ai . Проекцией множества A векторов (упорядоченных наборов из n элементов) на ось i будем называть множество проекций векторов из A на эту ось и обозначать прi A .

Графиком Р или бинарным отношением Р на множествах А и В будем называть подмноже-

ство декартова произведения этих множеств, т.е.

Р A B .

Инверсией графика Р будем называть график Р 1 а,b b, a P . Композицией графиков P и Q называется график (рис. 4)

P Q a,b a A, b B, c C : a, c P, c,b Q .

17

A		C		B
a	P	c	Q	•b

P◦Q

Рис. 4

Задание 2.1.
1.	Проверить справедливость равенства α для множеств А 1,	2 ,	B 2, 3 , C 1, 3 .
2.	Выяснить, верно ли равенство α для произвольных A, B, C .

18

Пример решения задания 2.1.

1. Проверить	справедливость равенства С В \ А С В С А В для множеств
А 1, 2 , B 2, 3 , C 1, 3 .
2. Выяснить,	верно ли равенство С В \ А С В С А В для произвольных мно-
жеств A, B, C .

Решение.

1.Для нашего случая

СВ \ А 1, 3 2, 3 \ 1, 2 1, 3 3 1, 3 , 3, 3 .

CA B 1, 3 1, 2 2, 3 1, 3 2 1, 2 , 3, 2 .

СВ 1,3 2,3 1,3 , 1, 2 , 3, 2 , 3,3 .

C B C A B 1,3 , 1, 2 , 3, 2 , 3,3 1, 2 , 3, 2 1,3 , 3,3 .

Итак, мы убедились, что в нашем примере равенство выполнено. Проверим это для общего случая.

2. Пусть А а, d , B b, d , C c , где a, b, c, d списки элементов.

19

Тогда C B \ A c b c, b , где c, b множество пар элементов, первая компонента входит в список c , а вторая – в список b .

A B d , C B C A B c,b , c, d c, d c,b .

Видим, что множества C B \ A и C B C A B состоят из пар одинакового вида, следовательно, равенство C B \ A C B C A B верно для произвольных A, B, C .

Задание 2.2. Для данного графика P найти: P 1, P P, P 1 P , пр2 Р 1 Р пр1 P P .

20