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

Для любых множеств A, B, C справедливы следующие тождества:

1. Коммутативность.

а) A È B  = B È A (для объединения); б) A Ç B = B Ç A (для пересечения).

2. Ассоциативность.

а) A È (B È C) = (A È C) È C (для объединения);

б) A Ç (B Ç C) = (A Ç B) Ç C (для пересечения).

3. Дистрибутивность.

а) A È (B Ç C) = (A È B)Ç(A È C) (для объединения относительно пересечения);

б) A Ç(B È C) = (A Ç B)È(A Ç C) (для пересечения относительно объединения).

4. Закон де Моргана.

а) = Ç (дополнение к объединению есть пересечение дополнений);

б)  = È (дополнение к пересечению есть объединение дополнений).

5. Идемпотентность.

а) A È A = A (для объединения);

б) A Ç A = A (для пересечения).

6. Поглощение.

а) A È (A Ç B) = A;

б) A Ç (A È B) = A.

7. Расщепление (склеивание).

а) (A È B) Ç (A È ) = A;

б) (A Ç B) È (A Ç ) = A.

8. Двойное дополнение. = A.

9. Закон исключенного третьего. A È = U.

10. Операции с пустым и универсальным множествами.

а) A È U = U;	г) A Ç Æ = Æ;
б) A È Æ = A;	д) = U;
в) A Ç U = A;	е) = Æ

11. А \ В = A Ç .

 

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

Пример 1.22. Доказать тождество (A È B) \ В = A Ç .

Преобразуем левую часть тождества, используя тождество 11:

(A È B) \ В = (A È B) Ç .

Затем используем закон дистрибутивности (тождество 3б):

(A È B) Ç = A Ç È B Ç .

Используем закон исключенного третьего (тождество 9): B Ç = Æ.

Получим: A Ç È B Ç = A Ç È Æ.

Используем свойство пустого множества (тождество 10б): A Ç È Æ = A Ç .

Тождество доказано.

Доказательство тождеств можно проиллюстрировать с помощью диаграмм Венна.

Пример 1.23. Доказать тождество: A \ (В \ C) = (A \ В)È (A Ç C).

Множества, стоящие в левой и правой частях тождества, изобразим с помощью диаграмм Эйлера – Венна (рис. 1.3).

Рис. 1.3

Рис. 1.3 б) и рис. 1.3 д) иллюстрируют равенство множеств A \ (В \ C) и (A \ В)È(A Ç C).

Примеры тестовых заданий

ЗАДАНИЕ N 1.1 (- выберите один вариант ответа)
Операцией над множествами А и В, результат которой выделен на рисунке,

 

 

является…

ВАРИАНТЫ ОТВЕТОВ:

1)			2)
3)			4)

 

Решение следует из определения пересечения множеств и рис. 1.1 в) Верный ответ: 4)

ЗАДАНИЕ N 1.2 (- выберите один вариант ответа)
Число 2,5 принадлежит множеству…

ВАРИАНТЫ ОТВЕТОВ:

1)			2)
3)			4)

Решение. 2,5ÏZ, 2,5ÏN; 2,5ÎQ, но 2,5>2, поэтому 2,5ÏD. 2,5ÎR, неравенство
-3<2,5<2,6 выполняется, поэтому 2,5ÎС. Верный ответ: 2)

ЗАДАНИЕ N 1.3 (- выберите один вариант ответа)
А и В – множества действительных чисел: , .
Тогда множество равно

ВАРИАНТЫ ОТВЕТОВ:

1)

2)

3)

4)

Решение. Изобразим множества А и В на числовой прямой:

Рис. 1.3

Из определения объединения множеств , рис. 1.1 б) и рис. 1.3 следует, что = (-4; 3). Верный ответ 1).

ЗАДАНИЕ N 1.4 (- выберите один вариант ответа)
Даны множества A ={ b, y } и B ={1,2,3}. Тогда декартовым (прямым) произведением является …

ВАРИАНТЫ ОТВЕТОВ:

1)	{(b, y,1),(b, y,2),(b, y,3)}		2)	{ b, y,1,2,3}
3)	{(1, b),(1, y),(2, b),(2, y),(3, b),(3, y)}		4)	{(b,1),(b,2),(b,3),(y,1),(y,2),(y,3)}

Решение. Из определения декартова произведения двух множеств следует, что оно содержит упорядоченные пары из двух элементов (варианты ответов 1, 2 – неверны), порядок следования элементов тот же, что у множеств в произведении, поэтому верный ответ 4).

ЗАДАНИЕ N 1.5 (- выберите несколько вариантов ответа)
Элементами множества натуральных чисел являются …

ВАРИАНТЫ ОТВЕТОВ:

1)

2)

3)

- 5

4)

5)

Решение. Натуральные числа это целые положительные числа, т.е. 3 и 101. Верный ответ: 4), 5).

ЗАДАНИЕ N 1.6 (- выберите несколько вариантов ответа)
Даны два множества , . Из предложенных высказываний верными являются…

ВАРИАНТЫ ОТВЕТОВ:

1)

2)

3)

4)

Решение. Очевидно, что XÌY; XÇY={2,4,6}=X; Y\X={0, 8}¹Y; YÈX={0,2,4,6,8}=Y¹X. Верный ответ: 1), 2).

Отображения. Отношения

Отображение множеств

Если каждому элементу хÎХ поставлен в соответствие один и только один элемент yÎY, то говорят, что определено отображение f множества X во множество Y. Обозначают y=f(x). Элемент у есть образ элемента х при данном отображении f, х - прообраз элемента у.

Отображение f ^-1, при котором каждому элементу множества Y ставится его прообраз из множества Х, называется обратным отображением для f.

Частным случаем отображения множества X во множество Y является отображение множества X на множество Y.

Отображение f множества X в Y называется сюръективным (отображением множества X на Y), если каждый элемент yÎY имеет хотя бы один прообраз.

Отображение X в Y называется инъективным, если для каждого элемента yÎY существует не более одного прообраза.

Если отображение f сюръективно и инъективно, оно называется биективным (взаимно-однозначным).

Пример 2.1. Пусть Х={а, b, с, d}, Y={2, 4, 6}, Z={m, n, k, q}. Зададим отображения
f₁: Х ® Y; f₂: Х ® Y; f₃: Y ® Z; f₄: X ® Z:

 

f1:	a ® 2	f2:	a ® 6	f3:	2 ® n	f4:	a ® m
	b ® 4		b ® 4		4 ® q		b ® q
	c ® 4		c ® 4		6 ® k		c ® k
	d ® 6		d ® 6				d ® n

 

Отображение f₁ X в Y является сюръективным, но не является инъективным (элемент "4" имеет два прообраза). Отображение f₂ несюръективно (элемент "2" не имеет прообраза) и неинъективно. Отображение f₃ является инъективным, но несюръективно (элемент " m" не имеет прообраза) и неинъективно. Отображение f₄ сюръективно и инъективно, т.е. является биективным.

Обратными для рассматриваемых отображений являются:

 

f1-1:	2® a	f2-1:	2 ® Æ	f3-1:	m ® Æ	f4-1:	m ® a
	4 ® {b, c}		4 ®{b, c}		n ® 2		n ® d
	6® d		6® {a, d}		k ® 6		k ® c
					q ® 4		q ® b

 

Очевидно, биективное отображение между конечными множествами X и Y возможно только в случае, когда число элементов этих множеств совпадает.

Пример 2.2. Биективным отображением для бесконечных множеств может является, например, отображение f, установленное между множеством натурального ряда чисел А={1, 2, 3,... n,...} и множеством четных положительных чисел В={2, 4, 6,...} по типу n «2n.

Пусть f: X ® Y и g: Y ® Z - некоторые отображения. Суперпозицией этихотображений называется отображение f g: X ® Z, определяемое следующим образом: (f g)(x)=g(f(x)), xÎ X.

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