Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ. ПОНЯТИЕ УПОРЯДОЧЕННОГО МНОЖЕСТВА




Пусть 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 ´…´ Xn = {(x1, x2, …, xn) ç x1ÎX1, x2ÎX2,…, xnÎXn}

Упорядоченные элементы этого произведения (x1, x2, …, xn) называются векторами, последовательностями, кортежами или просто «энками».

Если декартово произведение выполняется на одном и том же множестве, то его называют декартовой степенью этого множества.

X1 ´X2 ´… ´Xn = Xп

Правило произведения(лежащее в основе многих комбинаторных вычислений и оценок). Для конечных множеств Х1, Х2,…Хп :

| X1 ´X2 ´… ´Xn | = | X1| × | X2| × … ×| Xn|

Декартово произведение обладает следующими свойствами:

1) некоммутативность: А´В¹ В´А,если А ¹ В;

2) неассоциативность: (А´В)´С¹ А´(В´С);

3) дистрибутивность относительно операций :

(АÈВС = (А´С)È(В´С),

(АÇВС = (А´С)Ç(В´С),

(А\ ВС = (А´С) \ (В´С),

(АÈВС = (А´С)È(В´С),

(А¸ В)´С = (А´С) ¸(В´С).

Для случая двух множеств декартово произведение можно иллюстрировать с помощью диаграммы Венна. Пусть А= {a1, a2,…, an};

B = {b1, b2,…, 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,yxÎ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) (BÇC) = (A´B)Ç(A´C).







Дата добавления: 2015-09-18; просмотров: 847. Нарушение авторских прав; Мы поможем в написании вашей работы!


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2021 год . (0.006 сек.) русская версия | украинская версия