Lt;y1, y2>ÏA×B ® y1ÏA Ú y2Ï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 >}.

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

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

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

А₁ × А₂ × А₃ ×... × А_n = Æ ® А₁ = Æ Ú А₂ = Æ Ú А₃ = Æ Ú … Ú А_n = Æ.

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

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

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

M^S = M × M × M ×... × M

S – раз

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

Если М содержит n элементов и S ³ 2, то число элементов множества М^S равно n ^S, где n – число элементов множества М. Например, М = {a, b}, M⁰ = < >, M¹ = M, М² = {<a, a>, <a, a>, <b, a>, <b, b>}, M³ = {<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 ₁, a ₂,..., a _s > длины s, s > 0.

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

2) Пусть задано произвольное число q, такое, что 2 £ q £ s. И пусть задано число осей 1 £ i ₁ £ i ₂ £... £ i _q £ s. Тогда проекцией кортежа a на оси с номерами i ₁, i ₂,..., 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 ₁ £ i ₂ £... £ i _q £ s. Тогда проекцией множества М на оси с номерами i ₁, i ₂,..., i _q называется множество проекций кортежей из М на оси с номерами i ₁, i ₂,..., 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, 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 M^s = M

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

< x, y > Î A ® x Î пр₁A & y Î пр₂А,

Дата добавления: 2015-10-26