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

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

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

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

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

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

2) Пусть задано произвольное число q, такое, что 2  q  s. И пусть задано число осей 1  i₁  i₂  ...  i_q  s. Тогда проекцией кортежа  на оси с номерами i₁, i₂, ..., i_q называется кортеж < a_i1, a_i2, ..., a_iq >, который обозначается следующим образом: пр_i1,i2,...,iq  = < a_i1, a_i2, ..., a_iq >.

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

Например, задан кортеж  = < 12, 15, 6, 7, 8 >, пр_i1 = < 12 >, пр_i2 = < 15 >, пр_i3 = < 6 >, пр_i4  = < 7 >, пр_i5  = < 8 >, пр_i1,i2  = < 12, 15 >, пр_i1,i5  = < 12, 8 >, пр_i6,i8  = < >.

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

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

Пусть задано множество кортежей М длины 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 проекция пр_iM^s = M

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

x, y  A  x  пр₁A  y  пр₂А,

x  пр₁A  y  пр₂А  x, y  A.

Приведем основные свойства операции проектирования:

Пусть A  X × Y, B  X × Y, тогда для любых x  X и y Y(x  X  y  Y) истинно:

• ,

• пр₁X²  пр₂X²  X,

• ,

• ,

• ,

• ,

• x  пр₁A  y  пр₂A  (w  Y)(z  X)(x, w  A  z, y  A).

В то же время в общем случае ложными являются следующие высказывания:

• ,

• x  пр₁A  y  пр₂A  x, y  A,

• ,

• (пр₁A  пр₁B)  (пр₂A  пр₂B)  A = B.

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

Рассмотрим операции над кортежами. Известны две основные операции: инверсия кортежа и композиция кортежа.

1) Инверсия.

Инверсия кортежа определяется следующим образом. Пара <c, d> называется инверсией пары <a, b>, если c = b & d = a. Инверсия пары  обозначается ^-1.

Например,  = <a, b>, тогда ^-1 = <b, a>. (^-1)^-1 = , ((^-1)^-1)^-1 = ^-1. Тогда  ^-n =  и ^{- (n - 1)} = ^-1, при n – четном.

2) Композиция.

Кортеж  = <x, y> называется композицией двух кортежей  = <x, z> и  = <z, y> и записывается  =  • . Операция композиции справедлива, когда вторая компонента кортежа  совпадает с первой компонентой кортежа . Здесь как бы происходит “склеивание” двух кортежей по компоненте z.