ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ. ПОНЯТИЕ УПОРЯДОЧЕННОГО МНОЖЕСТВАПусть Xи Y– некоторые непустые множества, где x ÎX, yÎY.Рассмотрим двухэлементное множество, состоящее из пар x и y. Пара (или двойка) { x, y } называется неупорядоченной. Здесь порядок записи элементов не важен, поэтому { x, y } = { y, x }. Пара (x, y) называется упорядоченной. Здесь порядок записи существенен, поэтому (x, y) ¹ (y, x). Множество, для которого имеет значение порядок записи его элементов, называется упорядоченным. В противном случае – неупорядоченным. Декартовым (или прямым) произведением множеств X и Y называется множество всех упорядоченных пар, где первый элемент принадлежит множеству X, а второй – Y. X´Y = {(x, y) ç; x ÎX, y ÎY} Аналогично определяется декартово произведение любого конечного числа n множеств: X1 ´X2 ´…´ X n = {(x 1, x 2, …, xn) ç; x 1ÎX1, x 2ÎX2,…, xn ÎX n } Упорядоченные элементы этого произведения (x 1, x 2, …, xn) называются векторами, последовательностями, кортежами или просто «энками». Если декартово произведение выполняется на одном и том же множестве, то его называют декартовой степенью этого множества. X1 ´X2 ´… ´X n = X п Правило произведения (лежащее в основе многих комбинаторных вычислений и оценок). Для конечных множеств Х1, Х2,… Х п: | X1 ´X2 ´… ´X n | = | X1| × | X2| × … ×| X n | Декартово произведение обладает следующими свойствами: 1) некоммутативность: А´В ¹ В´А,если А ¹ В; 2) неассоциативность: (А´В) ´С ¹ А ´(В ´ С); 3) дистрибутивность относительно операций: (А È В)´ С = (А ´ С)È(В ´ С), (А Ç В)´ С = (А ´ С)Ç(В ´ С), (А \ В)´ С = (А ´ С) \ (В ´ С), (А È В)´ С = (А ´ С)È(В ´ С), (А¸ В)´С = (А´С) ¸(В´С). Для случая двух множеств декартово произведение можно иллюстрировать с помощью диаграммы Венна. Пусть А = { a 1, a 2,…, an }; B = { b 1, b 2,…, bm }.
Рассмотрим прямое произведение множества R действительных чисел самое на себя. Множество R ´ R или R2 состоит из всех упорядоченных пар вещественных чисел (х, у). Их можно трактовать как координаты точек плоскости XOY, то есть декартовой плоскости. Часто в дискретной математике множество вещественных чисел обозначают D (вместо R). Смысл этого обозначения станет понятным из дальнейшего изложения.
Задача 4.3.1. Найти декартово произведение А´В и В´А на множествах А ={1, 2} и B ={ a, b, c }. Решение. А´В = {1, 2}´ { a, b, c } = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}; B´A = { a, b, c } ´ {1, 2} = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}.
Задача 4.3.2. Найти декартовы степени А 2, А 3, В 2, А ={1, 2} и B ={ a, b, c }. Решение. А2 = А´А = {1, 2}´{1, 2} = {(1,1), (1,2), (2,1), (2,2)}; A3 = A´A´A = A2 ´A = {1, 2}´{1, 2}´{1, 2} = {(1,1), (1,2), (2,1), (2,2)}´{1, 2}= = {(1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2)}; B2 = B´B = { a, b, c }´{ a, b, c } = = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}.
Задача 4.3.3. Найти геометрическую интерпретацию множеств: 1) [1, 4] ´ [2,3]; 2) [1, 2]2; 3) [1, 2]3. Решение. 1. Пусть А ={ x ô1£ x £4}, B = { у ô2£ у £3}. Отложим на оси ОХ множество А, а множество В – на оси OY. Совершенно ясно, что множества А и В содержат бесконечное множество элементов. Их произведение А´В={(x, y)ô x ÎA, y ÎB} есть множество точек прямоугольника с вершинами в точках (1,2), (1,3), (4,2) и (4,3).
2. Множество [1,2]2 = [1,2] ´ [1,2] – это множество точек квадрата с вершинами в точках (1,1), (1,2), (2,1), (2,2). 3. Множество [1, 2]3 – это множество точек куба с вершинами в точках (1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2). Задача 4.3.4. Проверить справедливость равенства С´(В\А)=(С´В)¸(С´(АÇВ)) для множеств А ={ a, d }, B ={ b, d }, C ={ c }. Решение. Найдём множество в левой части равенства: В\А = {b, d}\{a, d} = {b}; C´(B\A) = {c}´{b} = {(c, b)}; Аналогично находим множество в правой части равенства: С´В = {c}´{b, d} = {(c, b), (c, d)}; AÇB = {a, d} Ç {b, d} = {d}; C´(AÇB) = {c}´{d} = {(c, d)}; (С´В)¸(С´(АÇВ)) = = {(c, b), (c, d)}¸ {(c, d)} = {(c, b)}; В левой и правой части равенства имеем одно и то же множество. Следовательно, для данных множеств равенство справедливо.
Задача 4.3.5. Доказать, что (А È В)´ С = (А ´ С)È(В ´ С). Решение. Воспользуемся определением равенства множеств. Ясно, что мы имеем дело с множествами, состоящими из упорядоченных пар. Пусть элемент (х, у)Î(АÈВ)´С, откуда имеем, что х Î(АÈВ), у ÎС. Значит х ÎА или х ÎВ, а тогда (х, у)ÎА´С или (х, у)ÎВ´С. Мы показали, что всякий элемент, принадлежащий множеству слева, принадлежит также и множеству справа, то есть (АÈВ)´С Í(А´С)È(В´С). Пусть теперь (х, у) Î (А´С)È(В´С). Отсюда вытекает, что (х, у)Î(А´С) или что (х, у)Î(В´С). В первом случае х ÎА, у ÎС, во втором – х ÎВ, у ÎС. Следовательно, х ÎАÈВ, а (х, у)Î(АÈВ)´С. Итак, (А´С)È(В´С) Í(АÈВ)´С. Что и доказывает наше равенство.
Задачи для самостоятельного решения. 1. Найти декартово произведение А´В и В´А на множествах а) А ={2, 4} и B ={3, 5, 7}; б) A ={ k, m } и B ={ m, n, l }. 2. Найти декартовы степени А 2, А 3, если А ={ a, b, c }. 3. Проверить справедливость равенства С ´(A È B)=(С ´ A)È(С ´(B \ A)) для множеств А ={1, 2}, B ={2, 3}, C ={1, 3}. 4. Доказать, что a) если В Ì А и С Ì А, то (В ´ С)Ì(А ´ А); b) A´;(B Ç C) = (A ´ B)Ç(A ´ C).
|
