Лекции.Орг


Поиск:




Lt; y 1, y 2 > Ï A × B ® y 1 Ï A Ú y 2 Ï B.




Например, заданы множества А = { a, b }, B = { c, d, e }. Тогда декартово произведение этих множеств равно A × B = {<a, c>, <a, d>, <a, e>, <b, c>, <b, d>, <b, e>}.

Кортеж длины 2 <a, b> можно изобразить на координатной плоскости точкой, абсциссой которой является 1-й элемент кортежа, а ординатой — 2-й элемент кортежа.

Например, заданы множества A = {2, 3}, B = {1, 4}. Тогда A × B = {<2, 1>, <2, 4>, <3, 1>, <3, 4> }, B × A = {<1, 2>, <1, 3>, <4, 2>, <4, 3>} (рис. 3.1).

Рис. 3.1. Пример декартова произведения двух множеств (B ´ A – точки ¨; A ´ B – точки ■)

Аналогичным образом определяется декартово произведение трех, четырех и более множеств.

Декартовым произведением трех множеств А, В, С называется множество, состоящее из всех тех кортежей длины 3, 1-й элемент которых принадлежит множеству А, 2-й — множеству В, 3-й — множеству С. Например, если, A = {2, 3}, B = {a, b}, С = { x, y }. Тогда A × B × C = {<2, a, x >, <2, a, y >, <2, b, x >, <2, b, y >, <3, a, x >, <3, a, y >, <3, b, x >, <3, b, y >}.

Из определения декартова произведения следует, что А × В равно Æ, если А = Æ или В = Æ:

А × В = Æ ® А = Æ Ú В = Æ.

По аналогии можно утверждать, что произведение нескольких множеств равно пустому множеству тогда и только тогда, когда хотя бы одно из этих множеств пусто:

А1 × А2 × А3 ×... × Аn = Æ ® А1 = Æ Ú А2 = Æ Ú А3 = Æ Ú … Ú А n = Æ.

Исходя из свойств кортежа, справедливо следующее: А × В ¹ В × А.

Операцию декартова произведения используют для определения степеней множества.

Пусть М — произвольное множество. Назовем S-той степенью множества М и обозначим МS прямое декартово произведение S - одинаковых множеств, равных М. Для S = 2, 3, 4...

MS = M × M × M ×... × M

     S – раз

По определению считают, что M1 = M, M0 = < >. При S ³ 2 множество МS является множеством всех кортежей длины S над множеством М.

Если М содержит n элементов и S ³ 2, то число элементов множества МS равно n S, где n – число элементов множества М. Например, М = {a, b}, M0 = < >, M1 = M, М2 = {<a, a>, <a, a>, <b, a>, <b, b>}, M3 = {<a, a, a>, <a, a, b>, <a, b, a>, <a, b, b>, <b, a, a>, <b, a, b>, <b, b, a>, <b, b, b>}.

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

· X × Y ¹ Y × X                                           - некоммутативность;

· X × (Y × Z) = (X × Y) × Z = X × Y × Z   - ассоциативность;

· - дистрибутивность по объединению;

· - дистрибутивность по пересечению;

·     - дистрибутивность по разности;

· (X × Y) Ç (W × Z) = (X Ç W) × (Y Ç Z).

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

3.3. Операция проектирования множеств

Введем еще одну операцию — операцию проектирования.

Операция проектирования унарна. Она применима не к двум множествам, а к одному множеству. Кроме этого, операция проектирования применима только к множеству кортежей одинаковой длины. Проекция множеств определяется через проекцию кортежей.

Определим понятие проекции кортежей.

Пусть задан кортеж a = < a 1, a 2,..., a s > длины s, s > 0.

1) Пусть 1 £ i £ s. Тогда проекцией кортежа a на i -тую ось называется i -тая компонента кортежа a.

2) Пусть задано произвольное число q, такое, что 2 £ q £ s. И пусть задано число осей 1 £ i 1 £ i 2 £... £ i q £ s. Тогда проекцией кортежа a на оси с номерами i 1, i 2,..., i q называется кортеж < a i 1, a i 2,..., a i q >, который обозначается следующим образом: пр i 1, i 2,..., i q a = < a i 1, a i 2,..., a i q >.

3) Проекцией кортежа a на пустое множество осей называется пустой кортеж. Аналогично проекцией пустого кортежа на пустое множество осей называется пустой кортеж.

Например, задан кортеж a = < 12, 15, 6, 7, 8 >, пр i 1 a = < 12 >, пр i 2 a = < 15 >, пр i 3 a = < 6 >, пр i 4 a = < 7 >, пр i 5 a = < 8 >, пр i 1, i 2 a = < 12, 15 >, пр i 1, i 5 a = < 12, 8 >, пр i 6, i 8 a = < >.

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

Проекция множества М — это множество проекций кортежей из М.

Пусть задано множество кортежей М длины s, s > 0.

1) Пусть 1 £ i £ s, тогда проекцией множества М на i -тую ось называется множество проекций кортежей из М на i -тую ось и обозначается: пр i М.

2) Пусть задано произвольное число q, такое, что 2 £ q £ s, и задано число осей 1 £ i 1 £ i 2 £... £ i q £ s. Тогда проекцией множества М на оси с номерами i 1, i 2,..., i q называется множество проекций кортежей из М на оси с номерами i 1, i 2,..., i q.

3) Проекцией множества М на пустое множество осей называется множество проекций кортежей из М на пустое множество: прÆМ.

Рассмотрим пример. Пусть М = { < 1, 2, 3, 4, 5 >, < 2, 1, 3, 5, 5 >, < 3, 3, 3, 3, 3 >, < 3, 2, 3, 4, 3 >, < a, b, a, 1, a > }. Тогда пр2М = { 2, 1, 3, 2, b }, пр2,4М =    { < 2, 4>, < 1, 5>, < 3, 3>, < 2, 4>, < b, a> }, пр6,7М = Æ.

Пусть М — произвольное множество, длина которого s, s ³ 2. Тогда множество Мs состоит из кортежей длины s и значит, его можно проектировать. Операция проектирования множества основана на описанных правилах построения проекций кортежей и множеств. Для любого натурального числа i, 1 £ i £ s проекция пр i Ms = M

Согласно определению операции проектирования, можно сказать, что для произвольного кортежа <x, y>истинны следующие высказывания:

< x, y > Î A ® x Î пр 1 A & y Î пр 2 А,





Поделиться с друзьями:


Дата добавления: 2018-10-18; Мы поможем в написании ваших работ!; просмотров: 175 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Что разум человека может постигнуть и во что он может поверить, того он способен достичь © Наполеон Хилл
==> читать все изречения...

958 - | 872 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.01 с.