Как найти проекцию множества - Avtoru.top - решение различных проблем

Проекцией
кортежа
на i-ю
ось называется i-й
компонент этого кортежа.

Проекцией
кортежа на оси с номерами i₁,
i₂,
…, i_k
(при этом должно соблюдаться условие
i₁
< i₂
< … < i_k)
называется кортеж, состоящий из
компонентов с номерами i₁,
i₂,
…, i_k.

Пример 1.7 – Дан
кортеж x
= (8, 3, 2, 3). Приведем некоторые примеры
его проекций:

проекция
на первую ось: Пр₁x
= 8;
проекция
на третью ось: Пр₃x
= 2;
проекция
на первую и третью оси: Пр_1,3x
= (8, 2);
проекция
на вторую и четвертую оси: Пр_2,4x
= (3, 3).

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

Пример 1.8 – Дано
множество A
= {(2, 5, 6), (7, 3, 9), (4, 5, 2), (8, 5, 6)}. Так как это
множество состоит из кортежей одинаковой
длины (из троек), можно найти его проекции
на первую, вторую или третью оси (или на
комбинации этих осей). Приведем некоторые
примеры его проекций:

проекция
на первую ось: Пр₁A
= {2, 7, 4, 8};
проекция
на вторую ось: Пр₂A
= {5, 3};
проекция
на первую и третью оси: Пр_1,3A
= {(2, 6), (7, 9), (4, 2), (8, 6)};
проекция
на вторую и третью оси: Пр_2,3A
= {(5, 6), (3, 9), (5, 2)}.

Поясним
определение проекции на вторую ось.
Множество A
состоит из четырех кортежей. Проекция
первого, третьего и четвертого кортежей
на вторую ось – число 5, а проекция
второго кортежа – число 3. Проекция
множества на вторую ось (Пр₂A)
представляет собой множество {5, 3} (можно
записать его и как {3, 5}, так как порядок
элементов во множестве безразличен).
Число 5 указано один раз, так как во
множестве один и тот же элемент дважды
не указывается.

1.3 Отношения

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

Отношением
G
на множестве A
называется подмножество декартова
квадрата множества A.
Другими словами, G
– отношение, заданное на множестве A,
если G

A².
При этом, если (a,
b)

G
(где a

A,
b

A),
то говорят, что элемент a
находится в заданном отношении с
элементом b.
Множество A,
на котором задано отношение, называют
областью задания отношения.

Примечание
– Иногда используется несколько другое
определение понятия отношения. Говорят,
что отношение – это пара
множеств
(G,
A),
где G

A².
Множество G
в этом случае называют графиком
отношения, а множество A
– областью задания отношения.

Применяются три
основных способа задания отношений:

перечислением;
описанием
свойств;
матричный.

Пример 1.9 – Дано
множество чисел A
= {1, 3, 4, 7, 8, 9}. Задать на нем отношение
«быть делителем».

Здесь
A
– область задания отношения.

Зададим отношение
перечислением:

G
= {(1, 1), (1, 3), (1, 4), (1, 7), (1, 8), (1, 9), (3, 3), (3, 9),
(4, 4), (4, 8), (7, 7), (8, 8), (9, 9)}.

Здесь,
например, пара (1, 3) указана, так как число
1 – делитель числа 3. Другими словами,
число 1 находится в отношении «быть
делителем» с числом 3. Пара (3, 1)
отсутствует, так как число 3 не является
делителем для числа 1.

Зададим отношение
описанием свойств:

G
= {(a,
b)
| a

A,
b

A,
a
– делитель b},

или

G
= {(a,
b)
| a

A,
b

A,
{b
/ a}
= 0}.

Здесь
{b
/ a}
– обозначение дробной части от деления
b
на a.

Зададим
отношение матричным способом. Для этого
строится матрица (обозначим ее, например,
R)
размерностью n
× n,
где n
– количество элементов в области
задания. Значения элементов матрицы R
определяются следующим образом: R_ij
= 1, если элемент a_i
из области задания находится в заданном
отношении с элементом a_j
из области задания, или, другими словами,
если (a_i, a_j)  G;
R_ij
= 0, если a_i
не находится в заданном отношении с a_j,
т.е. (a_i, a_j)  G.

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

Здесь,
например, R₂₆
= 1, так как второй элемент области задания
(число 3) находится в отношении «быть
делителем» с шестым элементом (числом 9).

Пример 1.10 – Дано
множество стран: S
= {Беларусь, Россия, Китай, Индия}. Задать
на этом множестве отношение «иметь
общую границу».

Зададим отношение
перечислением:

G
= {(Беларусь, Россия), (Россия, Беларусь),
(Россия, Китай), (Китай, Россия), (Китай,
Индия), (Индия, Китай)}.

Зададим отношение
описанием свойств:

G
= {(a,
b)
| a

S,
b

S,
a
имеет границу с b}.

Зададим отношение
матричным способом:

Источник

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

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

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

1) Пусть 1 ≤I≤S. Тогда проекцией кортежа αНа I-тую ось называется I-тая компонента кортежа α.

2) Пусть задано произвольное число q, такое, что 2 ≤Q≤s. И пусть задано число осей 1≤I1≤I2≤…≤Iq≤s. Тогда проекцией кортежа αНа оси с номерами I1,I2,…,Iq называется кортеж <аI1, аI2, …, аIq>, который обозначается следующим образом: ПрI1, I2,…,iqα = < аI1, аI2, …, аIq>.

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

Пример. Пусть задан кортеж α= < 12, 15, 6, 8 >, ПрI1 α= <12>, ПрI2 α= <15>, ПрI3 α= <6>, ПрI4 α= <8>, ПрI1,I2 α= <12,15>, ПрI1,I4 α= <12,8>, ПрI5,I8 α= <>.

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

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

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

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

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

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

Пример. Пусть М = { < 1, 2, 3, 4, 5 >, < 2, 1, 3, 5, 5 >, < 3, 3, 3, 3, 3><3, 2, 3, 4, 3><а, B, а, 1,а>}.Тогда пр2М = { 2, 1,3, 2, b }, пр2,4М = { <2,4>, <1, 5>, <3, 3>, <2, 4>, <B, 1> }, пр67М = Ø.

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

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

<х, у>А XПр1A & YПр2A,

ХПр1A YПр2A <х, у>А.

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

Пусть AX×Y, BX×Y, тогда для любых xX и уY (XX &yY)

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

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

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

1) Инверсия.

Инверсия кортежа определяется следующим образом. Пара <C, D> называется Инверсией пары <A,B>,если C=B&D=A. Инверсия пары α обозначается α-1

Пример.α = <а, B>,Тогда α -1= <B, а>. (α -1)-1= α, ((α -1)-1)-1= α-1. Тогда α-N= α И α-(n-1)=α-1, при четном N.

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

Кортеж α= <х, у>Называется композицией двух кортежей β = <х, Z>И γ = <Z, у>И записывается α = β·γ. Операция композиции справедлива, когда вторая компонента кортежа βСовпадает с первой компонентой кортежа γ. Здесь как бы происходит «склеивание» двух кортежей по компоненте Z.

< Предыдущая		Следующая >

Источник

Методы Оптимизации. Даниил Меркулов. Отделимость. Проекция. Опорная гиперплоскость

Interior

Внутренность множества

Внутренностью множества $S$ называется следующее множество:
$$mathbf{int} (S) = {mathbf{x} in S mid exists varepsilon > 0, B(mathbf{x}, varepsilon) subset S}$$
где $B(mathbf{x}, varepsilon) = mathbf{x} + varepsilon B$ — шар с центром в т.$mathbf{x}$ и радиусом $varepsilon$

Относительная внутренность множества

Относительной внутренностью множества $S$ называется следующее множество:
$$mathbf{relint} (S) = {mathbf{x} in S mid exists varepsilon > 0, B(mathbf{x}, varepsilon) cap mathbf{aff} (S) subseteq S}$$

center

Любое непустое выпуклое множество $S subseteq mathbb{R}^n$ имеет непустую относительную внутренность $mathbf{relint}(S)$

Projection

Расстояние между точкой и множеством

Расстоянием $d$ от точки $mathbf{y} in mathbb{R}^n$ до замкнутого множества $S subset mathbb{R}^n$ является:
$$d(mathbf{y}, S, | cdot |) = inf{|x — y| mid x in S }$$

Проекция точки на множество

Проекцией точки $mathbf{y} in mathbb{R}^n$ на множество $S subseteq mathbb{R}^n$ называется точка $pi_S(mathbf{y}) in S$: $$| pi_S(mathbf{y}) — mathbf{y}| le |mathbf{x} — mathbf{y}|, forall mathbf{x} in S$$

Если множество — открыто, и точка в нем не лежит, то её проекции на это множество не существует
Если точка лежит в множестве, то её проекция — это сама точка
$$pi_S(mathbf{y}) = underset{mathbf{y}}{operatorname{argmin}} |mathbf{x}-mathbf{y}|$$
Пусть $S subseteq mathbb{R}^n$ — выпуклое замкнутое множество. Пусть так же имеются точки $mathbf{y} in mathbb{R}^n$ и $mathbf{pi} in S$. Тогда если для всех $mathbf{x} in S$ справедливо неравенство: $$langle pi -mathbf{y}, mathbf{x} — pirangle ge 0, $$ то $pi$ является проекцией точки $mathbf{y}$ на $S$, т.е. $pi_S (mathbf{y}) = pi$
Пусть $S subseteq mathbb{R}^n$ — афинное множество. Пусть так же имеются точки $mathbf{y} in mathbb{R}^n$ и $mathbf{pi} in S$. Тогда $pi$ является проекцией точки $mathbf{y}$ на $S$, т.е. $pi_S (mathbf{y}) = pi$ тогда и только тогда, когда для всех $mathbf{x} in S$ справедливо равенство: $$langle pi -mathbf{y}, mathbf{x} — pirangle = 0 $$

Пример 1

Найти $pi_S (y) = pi$, если $S = {x in mathbb{R}^n mid |x — x_c| le R }$, $y notin S$

Решение:

Из рисунка строим гипотезу: $pi = x_0 + R cdot frac{y — x_0}{|y — x_0|}$
Проверяем неравенство для выпуклого замкнутого множества: $(pi — y)^T(x — pi) ge 0$

$$left( x_0 — y + R frac{y — x_0}{|y — x_0|} right)^Tleft( x — x_0 — R frac{y — x_0}{|y — x_0|} right) =$$
$$left( frac{(y — x_0)(R — |y — x_0|)}{|y — x_0|} right)^Tleft( frac{(x-x_0)|y-x_0|-R(y — x_0)}{|y — x_0|} right) =$$
$$frac{R — |y — x_0|}{|y — x_0|^2} left(y — x_0 right)^Tleft( left(x-x_0right)|y-x_0|-Rleft(y — x_0right) right) = $$

$$frac{R — |y — x_0|}{|y — x_0|} left( left(y — x_0 right)^Tleft( x-x_0right)-R|y — x_0| right) =$$

$$left(R — |y — x_0| right) left( frac{(y — x_0 )^T( x-x_0)}{|y — x_0|}-R right)$$

Первый сомножитель отрицателен по выбору точки $y$. Второй сомножитель так же отрицателен, если применить к его записи теорему Коши — Буняковского: $$(y — x_0 )^T( x-x_0) le |y — x_0||x-x_0|$$
$$frac{(y — x_0 )^T( x-x_0)}{|y — x_0|} — R le frac{|y — x_0||x-x_0|}{|y — x_0|} — R = |x — x_0| — R le 0$$

Пример 2

Найти $pi_S (y) = pi$, если $S = {x in mathbb{R}^n mid c^T x = b }$, $y notin S$

Решение:

Из рисунка строим гипотезу: $pi = y + alpha c$. Коэффициент $alpha$ подбирается так, чтобы $pi in S$: $c^T pi = b$, т.е.: $$c^T (y + alpha c) = b$$
$$c^Ty + alpha c^T c = b$$
$$c^Ty = b — alpha c^T c$$
Проверяем неравенство для выпуклого замкнутого множества: $(pi — y)^T(x — pi) ge 0$
$$(y + alpha c — y)^T(x — y — alpha c) = $$
$$ alpha c^T(x — y — alpha c) = $$
$$ alpha (c^Tx) — alpha (c^T y) — alpha^2 c^Tc) = $$
$$ alpha b — alpha (b — alpha c^T c) — alpha^2 c^Tc = $$
$$ alpha b — alpha b + alpha^2 c^T c — alpha^2 c^Tc = 0 ge 0$$

Пример 3

Найти $pi_S (y) = pi$, если $S = {x in mathbb{R}^n mid Ax = b, A in mathbb{R}^{m times n}, b in mathbb{R}^{m} }$, $y notin S$

Решение:

Из рисунка строим гипотезу: $pi = y + sumlimits_{i=1}^malpha_i A_i = y + A^T alpha$. Коэффициент $alpha$ подбирается так, чтобы $pi in S$: $A pi = b$, т.е.: $$c^T (y + A^T alpha) = b$$
$$A(y + A^Talpha) = b$$
$$Ay = b — A A^Talpha$$
Проверяем неравенство для выпуклого замкнутого множества: $(pi — y)^T(x — pi) ge 0$
$$(y + A^Talpha — y)^T(x — y — A^Talpha) = $$
$$ alpha^T A(x — y — A^Talpha) = $$
$$ alpha^T (Ax) — alpha^T (A y) — alpha^T AA^T alpha) = $$
$$ alpha^T b — alpha^T (b — A A^Talpha) — alpha^T AA^T alpha = $$
$$ alpha^T b — alpha^T b + alpha^T AA^T alpha — alpha^T AA^T alpha = 0 ge 0$$

Separation

Отделимые множества

Множества $S_1$ и $S_2$ называются отделимыми, если существуют $mathbf{p} neq mathbf{0} in mathbb{R}^n$ и $beta in mathbb{R}$, что:
$$langle mathbf{p}, mathbf{x_1}rangle le beta le langle mathbf{p}, mathbf{x_2}rangle, ;; forall mathbf{x_1} in S_1, ;; forall mathbf{x_2} in S_2$$

center

Собственно отделимые множества

Множества $S_1$ и $S_2$ называются собственно отделимыми, если они отделимы и дополнительно можно указать такие $mathbf{x_1} in S_1, mathbf{x_2} in S_2$
$$langle mathbf{p}, mathbf{x_1}rangle < langle mathbf{p}, mathbf{x_2}rangle$$

center

Строго отделимые множества

Множества $S_1$ и $S_2$ называются строго отделимыми, если существует $mathbf{p} neq mathbf{0} in mathbb{R}^n$, что:
$$langle mathbf{p}, mathbf{x_1}rangle < langle mathbf{p}, mathbf{x_2}rangle, ;; forall mathbf{x_1} in S_1, ;; forall mathbf{x_2} in S_2$$

center

Сильно отделимые множества

Множества $S_1$ и $S_2$ называются сильно отделимыми, если существуют $mathbf{p} neq mathbf{0} in mathbb{R}^n$ и $beta in mathbb{R}$, что:
$$ underset{mathbf{x_1} in S_1}{operatorname{sup}} langle mathbf{p}, mathbf{x_1}rangle < beta < underset{mathbf{x_2} in S_2}{operatorname{inf}}langle mathbf{p}, mathbf{x_2}rangle, ;; forall mathbf{x_1} in S_1, ;; forall mathbf{x_2} in S_2$$

center

Расстояние между множествами

Расстоянием между множествами $S_1$ и $S_2$ называется число:
$$d(S_1, S_2,| cdot |) = underset{mathbf{x_1} in S_1, mathbf{x_2} in S_2}{operatorname{inf}} |mathbf{x_1} — mathbf{x_2}|$$

Если $X$ и $Y$ — непустые выпуклые множества в $mathbb{R}^n$ и $X cap Y = emptyset$, тогда $X$ и $Y$ — отделимы.
Если $X$ — непустое выпуклое замкнутое множество в $mathbb{R}^n$ и $mathbf{y} notin X$, тогда точку $mathbf{y}$ можно строго отделить от множества $X$.

Supporting hyperplane

Опорная гиперплоскость

Гиперплоскость $Gamma_{p,beta} = left{mathbf{x} in mathbb{R}^n : langle p, mathbf{x} rangle > beta right}$ называется опорной к множеству $S$ в граничной точке $mathbf{a} in partial S$, если $$langle p, mathbf{x} rangle ge beta = langle p, mathbf{a} rangle ;; forall mathbf{x} in S$$

Опорная гиперплоскость называется собственно опорной, если, кроме того, можно указать $mathbf{x_0} in S: langle p, mathbf{x_0} rangle > beta$

В любой граничной (относительно граничной) точке выпуклого множества существует опорная (собственно опорная) гиперплоскость.
Касательная плоскость к поверхности $F(x) = 0,$ где $F: mathbb{R}^n rightarrow mathbb{R}^1$ в точке $x_0$ определяется уравнением: $$nabla F(x_0)^T(x-x_0) = 0$$
Касательная плоскость к графику функции $f(x),$ где $f: mathbb{R}^n rightarrow mathbb{R}^1$ в точке $x_0$ определяется уравнением: $$phi(x) = f(x_0) + nabla f(x_0)^T(x-x_0) = 0$$

Пример 4

Построить гиперплоскость, разделяющую $S_1$ и $S_2$:
$$S_1 = left{ x in mathbb{R}^2 mid x_1 x_2 ge 1, x_1 > 0right}, ;;; S_2 = left{ x in mathbb{R}^2 mid x_2 le frac{4}{x_1 — 1} +9right}$$

Решение:

Найдем $partial S_1 cap partial S_2$:
$$
begin{cases}
x_1 x_2 = 1
x_2 = frac{4}{x_1 — 1} +9
end{cases}
$$

$$
begin{cases}
x_1 = frac{1}{3}
x_2 = 3
end{cases}
$$
т.е. множества пересекаются в точке $x_0 = (frac{1}{3}, 3)$

Построим касательные плоскости к обеим поверхностям в точке пересечения:
$$
begin{cases}
nabla F_1(x_0)^T(x-x_0) = 0
nabla F_2(x_0)^T(x-x_0) = 0
end{cases}
$$

$$
begin{cases}
3 x_1 + frac{1}{3}x_2 — 2 = 0 \
-6 x_1 — frac{2}{3}x_2 + 4 = 0
end{cases}
$$

Итого, получаем: $9x_1 + x_2 = 6$, т.е. $p = (9,1), beta = 6$

Пример 5

Построить опорную гиперплоскость для множества $S = left{ x in mathbb{R}^2 mid e^{x_1} le x_2right}$ в граничной точке $x_0 = (0,1)$

Решение:

Имеем поверхность $F(x_1, x_2) = e^{x_1} — x_2, ;;; nabla F = (e^{x_1}, -1), ;;; nabla F(x_0) = (1,-1)$
Тогда $$nabla F(x_0)^T(x-x_0) = 0$$
$$(1,-1)^T (x_1, x_2 — 1) = 0$$
Искомая опорная гиперплоскость: $x_1 — x_2 + 1 = 0$

Пример 6

Построить опорную гиперплоскость для множества $S = left{ x in mathbb{R}^3 mid x_3 ge x_1^2 + x_2^2right}$ так, чтобы она отделяла его от точки $x_0 = left(-frac{5}{4}, frac{5}{16}, frac{15}{16}right)$

Решение:

Заметим, что здесь $x_0 notin partial S$. А значит, таких гиперплоскостей много. Возможный вариант: искать опорную гиперплоскость в точке $pi_S(x_0) = pi in S$. Значит, $Gamma_{p, beta} = left{ x in mathbb{R}^3 mid p^Tx = beta, p^T pi = beta right}$
Будем искать $pi$, решая задачу минимизации:

$$underset{x in partial S}{operatorname{min}}|x — x_0|^2$$
$$underset{x in partial S}{operatorname{min}}(x — x_0)^T(x — x_0)$$

Учитывая структуру множества $partial S = {x in mathbb{R}^3 mid x_3 = x_1^2 + x_2^2}$, можем перейти к задаче безусловной минимизации.

$$ left( x_1 + frac{5}{4} right)^2 + left( x_2 — frac{5}{16} right)^2 + left( x_1^2 + x_2^2 — frac{15}{16} right)^2 rightarrow operatorname{min}$$

Единственным решением которой является точка $pi = left( -1, frac{1}{4}, frac{17}{16}right)$.

Тогда $p = x_0 — pi = left( -frac{1}{4}, frac{1}{16}, -frac{1}{8}right), ;; beta = p^T pi = frac{17}{128}$

Домашнее задание 3

Найти $pi_S (y) = pi$, если $S = {x in mathbb{R}^n mid c^T x ge b }$
Найти $pi_S (y) = pi$, если $S = {x in mathbb{R}^n mid x = x_0 + X alpha, X in mathbb{R}^{n times m}, alpha in mathbb{R}^{m}}$, $y notin S$
Построить гиперплоскость, разделяющую $S_1$ и $S_2$:
$$S_1 = left{ x in mathbb{R}^n mid x_1^2 + x_2^2 + ldots + x_n^2 le 1right}, ;;; S_2 = left{ x in mathbb{R}^n mid x_1^2 + x_2^2 + ldots + x_{n-1}^2 + 1 le x_n right}$$
Построить опорную гиперплоскость для множества $S = left{ x in mathbb{R}^3 mid frac{x_1^2}{4}+frac{x_2^2}{8}+frac{x_3^2}{25} le 1 right}$ в граничной точке $x_0 = left(-1, frac{12}{5}, frac{sqrt{3}}{2}right)$
Пусть $S subset mathbb{R}^n$ — замкнутое выпуклое множество, $mathbf{x} in S$. Найти множество $Y subset mathbb{R}^n$ такое, что $forall mathbf{y} in Y$ выполнено $mathbf{x} = pi_S(mathbf{y})$
Пусть даны $mathbf{x} in mathbb{R}^n$ и выпуклый конус $K subseteq mathbb{R}^n$. Пусть $Y = mathbf{x} + K$, $mathbf{y} in Y$. Найти множество $X subset mathbb{R}^n,$ такое, что $mathbf{x} in X, forall mathbf{y} in Y: x = pi_X(mathbf{y})$

В качестве решения необходимо предоставить либо:

.pdf файл, сверстанный с помощью $ LaTeX $ с решениями задач
.ipynb с оформленным решением

Источник

«Теория систем и системный анализ»

И. Б. Родионов

Лекция 13: Операции над множествами. Упорядоченное множество

1. Объединение множеств

Объединение множеств X и Y — это множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств X или Y, т.е. принадлежат X или принадлежат Y.

Объединение X и Y обозначается через X∪Y

Формально x∈X∪Y ⇔ x∈X или x∈Y

Пример 1. Если X={1,2,3,4,5} и Y={2,4,6,8}, то

X∪Y={1,2,3,4,5,6,7,8}

Пример 2. Если X={x:x — отл.гр.}, и Y={x:x — gib.}, то

X∪Y={x:x — или отл., или gib}.

Пример 3. Если X — множество точек левого круга и Y — множество точек правого круга, то

X∪Y — заштрихованная область, ограниченная обоими кругами.

Понятие объединения можно распространить и на большее число множеств, на систему множеств. Обозначим через М={X₁,X₂, …,X_n} совокупность n множеств X₁,X₂, …,X_n, называемую иногда системой множеств. Объединение этих множеств

∪X_i=∪(X∈M), Х=X₁∪X₂∪…∪X_n

представляет собой множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств данной системы М.

Для объединенных множеств справедливы:

X∪Y = Y∪X — коммутативный закон
(X∪Y)∪Z = X∪(Y∪Z) = X∪Y∪Z — ассоциативный закон,

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

Очевидно, что X∪∅ = X. Отсюда можно видеть, что ∅ играет роль нуля в алгебре множеств.

2. Пересечение множеств

Пересечение множеств X и Y — это множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству X, так и множеству Y.

Пересечение множеств обозначается X∩Y.

Формально x∈X∩Y ⇔ x∈X и x∈Y

Пример 4. X={1,2,3,4,5} Y={2,4,6,8} X∩Y = {2,4}

Пример 5. Если Х — множество точек левого круга, а Y — множество точек правого круга, то X∩Y представляет собой заштрихованную область, являющуюся общей частью обоих кругов.

Множества X и Y называются непересекающимися (дизъюнктными), если они не имеют общих элементов, то есть если X∩Y=∅.

Пример 7. {1,2,3} и {4,5,6}

В отличие от алгебры чисел, где могут быть три возможности: a<b, a=b, b<a между двумя множествами X и Y может быть одно из 5 cотношений:

X=Y; X⊂Y; Y⊂X; X∩Y=∅ и X и Y находятся в общем положении.

Говорят, что множества X и Y находятся в общем положении, если выполняются три условия:

существует элемент множества X, не принадлежащий Y;
существует элемент множества Y, не принадлежащий X;
существует элемент, принадлежащий как X, так и Y.

Аналогично объединению понятие пересечения можно распространить на систему множеств:

∩X=∩X_i=X₁∩X₂∩…∩X_n

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

Для пересечения множеств справедливы:

X∩Y=Y∩X — коммутативный закон
(X∩Y)∩Z = X∩(Y∩Z) = X∩Y∩Z — ассоциативный закон

Заметим также, что имеет место соотношение X∩∅=∅.

Пример 8. A={a,b}, B={b,c}, C={a,c}.

A∩B∩C=∅, хотя A∩B={b}, B∩C={c}

3. Разность множеств

Разность множеств определена только для двух множеств. Разностью множеств X и Y называется множество, состоящее из всех тех и только тех элементов, которые принадлежат X и не принадлежат Y.

Обозначается: XY.

Формально: x∈XY ⇔ x∈X и x∉Y

Пример 9. (см. Пример 1) X={1,2,3,4,5}, Y={2,4,6,8}, XY={1,3,5}, YX={6,8}

Разность множеств не обладает свойством коммутативности.

XY≠YX

Если AB=∅, то A⊂B — поставить ? обратно

при A∩B≠∅

4. Универсальное множество

Роль нуля в алгебре множеств играет пустое множество. А нет ли такого множества, которое играет роль «1», т.е. удовлетворяет условию: X∪I = X, что означает, что пересечение или «общая часть» множества I и множества X для любого множества X совпадает с самим этим множеством. Это возможно лишь в том случае, если множество I содержит все элементы, из которых может состоять множество X, так что любое множество X полностью содержится в множестве I.

Множество I, удовлетворяющее этому условию, называется полным, или универсальным, или единичным.

Если при некотором рассмотрении участвуют только подмножества некоторого фиксированного множества, то это самое большое множество будем считать универсальным и обозначать I.

Пример 12 (Пример 1). I — множество целых чисел

Пример 13 (Пример 2). I — множество студ. гр.

Пример 14 (Пример 3). I — лист бумаги, доска

Универсальное множество обычно обозначают графически в виде множества точек прямоугольника, а отдельные множества в виде отдельных областей внутри этого прямоугольника. Изображение множеств в виде областей в прямоугольнике, представляющем универсальное множество, называется диаграммой Эйлера-Венна.

Универсальное множество обладает интересным свойством, которое не имеет аналогии в обычной алгебре, а именно, для любого множества X справедливо соотношение X∪I = I.

5. Дополнение множества

Множество, определяемое из соотношения X¯ = IX, называется дополнением множества X (до универсального множества I).

На диаграмме множество X¯ представляет собой незаштрихованную область.

Формально: X = {x: x∈I и x∉X}.

Из определения следует, что X и X¯ не имеют общих элементов. Х∩X¯=∅.

Кроме того, не имеется элементов I, которые не принадлежали бы ни X, ни X¯ (его дополнению), так как те элементы, которые не принадлежат X, принадлежат X¯ (его дополнению). Следовательно, Х∪X¯=I.

Из симметрии данной формулы относительно Х и X¯ следует не только то, что X¯ является дополнением Х, но и что Х является дополнением X¯. Но дополнение X¯ есть X¯ ¯. Таким образом, X¯ ¯=X¯.

С помощью операции дополнения представим разность множеств:

XY = {x: x∈X и x∉Y} ={ x: x∈X и x∈Y¯ }, т.е. XY= Х∩Y¯.

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

дополнение;
пересечение;
объединение, разность.

Для изменения порядка используют скобки.

6. Разбиение множества

Одной из наиболее часто встречающихся операций над множествами является операция разбиения множества на систему подмножеств.

Так, система курсов данного факультета является разбиением множества студентов факультета; система групп данного курса является разбиением множества студентов курса.

Пример. Продукция предприятия: — высший сорт, I, II, брак.

Рассмотрим некоторое множество M и систему множеств

М = {X₁, X₂, …, X_n}

Система множеств M называется разбиением множества M, если она удовлетворяет следующим условиям:

Любое множество X из M является подмножеством множества М

∀X∈M: X⊆M;
Любые два множества X и Y из М являются непересекающимися

∀X∈М, ∀Y∈M: X≠Y → X∩Y=∅.
Объединение всех множеств, входящих в разбиение, дает множество M

X₁∪X₂∪…∪ X_n=M.

7. Тождества алгебры множеств

С помощью операций объединения, пересечения и дополнения из множеств можно составлять различные алгебраические выражения.

Если алгебраические выражения V(X,Y,Z) и S(X,Y,Z) представляют собой одно и то же множество, то их можно приравнять друг другу, получая алгебраическое тождество вида V(X,Y,Z) = S(X,Y,Z)

(X∪Y)∩Z = (X∩Z)∪(Y∩Z) (аналогичное дистрибутивному закону (a+b)c=(a+c)(b+c) в обычной алгебре).
(X∩Y)∪Z = (X∪Z)∩(Y∪Z)
Если Y⊆X, то X∩Y=Y, X∪Y=X. Действительно, все элементы множества Y являются в то же время и элементами множества X. Значит пересечение этих множеств, то есть общая множеств Х и Y совпадает с Y. В объединение множеств X и Y множество Y не внесет ни одного элемента, который уже не входил бы в него, будучи элементом множества Х. Следовательно, X∪Y совпадает с X.
Пусть в примере 3 Y=X. Тогда, учитывая, что X⊆X, то X∩Х=Х, X∪Х=X. (идемпотентность).
Докажем тождество (X∪Y)¯=X¯∩Y¯. Предположим, что х∈(X∪Y)¯, то есть х∉X∪Y. Это значит, что х∉X и х∉Y, то есть и x&isinX¯ и x&isinY¯;. Следовательно, x∈X¯∩Y¯. Предположим теперь, что y∈X¯∩Y¯, то есть y∈X¯ и y∈Y¯. Это значит, что y∉X и y∉Y, то есть что y∉X∪Y. Следовательно, y∈(X∪Y)¯.
Тождество (X∩Y)¯=X¯∪Y¯. Обычно тождества 5) и 6) называются тождествами де-Моргана.
(AB)∩C=(A∩C)B=(A∩C)(B∩C)
AB=A(A∩B)
A=(A∩B)∪(AB)

Дополнение к занятию «операции над множествами»

Множество элементов, принадлежащих или A, или B, называют симметричной разностью или дизьюнктивной суммой.

S = A⊕B = (AB)∪(BA) = (A∩B¯)∪(A¯∪B) = (A∪B)∩(A∩B)¯

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

1) A⊕B = B ⊕A — коммутативность,
2) A⊕(B⊕С) = (A⊕B)⊕С — ассоциативность,
3) A⊕∅ = А=∅⊕A — существование нейтрального элемента,
4) A ⊕А = ∅
5) A∩(B⊕С) = (A∩B)⊕(А∩С) — дистрибутивность относительно пересечения.

Упорядоченное множество

Упорядоченным множеством (или кортежем) называется последовательность элементов, то есть совокупность элементов, в которой каждый элемент занимает определенное место. Сами элементы — компоненты кортежа.

Пример 1. Множество людей, стоящих в очереди, множество слов в фразе, алфавит. Во всех этих множествах место каждого элемента является вполне определенным и не может быть произвольно изменено.

Число элементов кортежа называется его длиной. Обозначают кортеж скобками «< >», иногда круглыми «( )». А=<a₁, a₂, …, a_n>. Кортежи длины 2 называются упорядоченными парами, 3 — тройками, n-ками.

Частный случай: кортеж длины 1 — <a>

кортеж длины 0 — < > или ∧ — пустой кортеж.

Отличие кортежа и обыкновенного множества: в кортеже могут быть одинаковые элементы.

Упорядоченные множества, элементами которых являются вещественные числа, будем называть векторами или точками пространства (n-мерного).

Так, кортеж <a₁, a₂> может рассматриваться как точка на плоскости или вектор, проведенный из начала координат в данную точку. Тогда компоненты a₁, a₂ — проекции вектора на оси 1 и 2.

Пр₁ <a₁, a₂> = a₁, Пр₂ <a₁, a₂> = a₂, Пр_i <a₁, a₂, a₃>= a_i, Пр₁2 <a₁, a₂, a₃>= <a₁, a₂> — двухэлементный кортеж. Проекция кортежа на пустое множество осей — пустой кортеж.

Обобщая эти понятия, будем рассматривать упорядоченное n-элементное множество вещественных чисел (a₁, …, a_n) как точку в воображаемом n–мерном пространстве (иногда называемом гиперпространством), или как n-мерный вектор. При этом компоненты n-элементного кортежа а будем рассматривать как проекции этого кортежа на соответствующие оси.

Пр_i a = a_i, i=1,2,…,n

Пр_i,j,…,l a = <a_i, a_j, …, a_l>, i=1,2,…,n

Два вектора равны, если они имеют одинаковую длину и соответствующие координаты их равны.

<a₁, …, a_m> = <b₁, …, b_n> ⇔ m = n и a₁ = b₁, b₁ = b₂, …

Компонентами кортежа (вектора) могут быть также компоненты кортежи (векторы):

Пример. Слова в предложении,

A = < <a₁, a₂>, <a₁, a₃>, <a₂, a₃> >

Прямое произведение множеств

Прямым (декартовым) произведением множеств X и Y называется множество, состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству X, а вторая принадлежит множеству Y.

Формально: X*Y = {<x,y>: x∈X, y∈Y}

Пример 2. Пусть X=<1,2>, Y=<1,3,4>

Тогда X*Y={<1,1>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4> } См. рис. а).

Пример 3. Пусть X и Y — отрезки вещественной оси. Прямое произведение X*Y изображается заштрихованным прямоугольником. См. рис. б).

Прямое произведение изменяется при изменении порядка сомножителей т.е.

X*Y ≠ Y*X

Прямое произведение множеств X₁, X₂, …, X_n — это множество, обозначаемое X₁*X₂*…*X_n и состоящее из всех тех и только тех кортежей длины n, правая компонента которых принадлежит X₁, вторая — X₂ и т.д.

Очевидно X*Y = ∅ ⇔ X = ∅ или Y = ∅.

Аналогично X₁*X₂*…*X_n = ∅ тогда и только тогда, когда хотя бы одно из множеств X₁, X₂, …, X_n является пустым.

Частным случаем прямого произведения является понятие степеней (декартовых) множества — прямое произведение одинаковых множеств

M^s=M*M*…*M, M¹=M, M⁰=∧.

Обычно R — множество вещественных чисел, тогда R²=R*R — вещественная плоскость и R³=R*R*R — трехмерное вещественное пространство.

Пример. A={a,b,c,d,e,f,g,h}, B={1,2,3, …,8}

Тогда A*B ={a₁, a₂, a₃, …, h7, h8} — множество обозначающее все 64 клеток шахматной доски.

Пример. Пусть A — конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания и т.д.). Такие множества обычно называют алфавитами. Элементы множества a_n называются словами длины n в алфавите A. Множество всех символов в алфавите A — это множество A^* = ∪Aⁱ = A¹∪A²∪A³… . При написании слов не принято пользоваться ни запятыми, ни скобками, ни разделителями.

СЛОВО ⇔ <С,Л,О,В,О>

Теорема. Пусть a₁, a₂, …, a_n — конечные множества и |a₁| = m₁, |a₂|=m₂, …, |a_n|=m_n. Тогда мощность множества a₁*a₂*a₃*…*a_n равна произведению мощностей a₁, a₂, …, a_n

|a₁*a₂*…*a_n|=|a₁|*|a₂|*|a₃|*…*|a_n|= m₁*m₂*…*m_n

Следствие |a_n|=|A|ⁿ

Проекция множества.

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

Пусть M — множество, состоящее из кортежей длины S. Тогда пролинией множества M будем называть множество пролиний всех кортежей из М

Пример. Пусть М={<1,2,3,4,5>,<2,1,3,5,5>,<3,3,3,3,3>,<3,2,3,4,3>}

тогда Пр₂М={2,1,3}, Пр₃M={3}, Пр₄M={4,5,3}, Пр₂₄M={<2,4>,<1,5>,<3,3>}, Пр₁₃M={<1,3>,<2,3>,<3,3>}, Пр₁₅M={<1,5>,<2,5>,<1,3>}, Пр₂₅M={<2,5>,<1,5>,<3,3>,<2,3>}.

Очевидно что если М=Х*Y то Пр₁М=Х, Пр₂М=Y

и если Q⊆Х*Y то Пр₁Q⊆Х и Пр₂Q⊆Y

Пример. V={<a,b,d>,<c,b,d>,<d,b,b>}

Пр₁V={a,c,d}

Пр₂V={b}

Пр₃V={d,b}

Пр₁2V={<a,b>,<c,b>,<d,b>}

Пр₂3V={<b,d>,<b,b>}

Пр₁3V={<a,d>,<c,d>,<d,b>}

Пусть V — множество векторов одинаковой длины S.

Пр_iV ={Пр_iv/v∈Y}, Пр_{i_i…i_k}v = { Пр_{i_i…i_k}v/v∈Y}.

Если V =A₁*A₂*…*A_n, то Пр_{i_i…i_k}V=A_i1*A_i2*…*A_ik.

В общем случае Пр_iV — вовсе не обязательно прямое произведение: оно может быть подмножеством.

Источник

Проекция — множество

Cтраница 1

Проекция множества, проведенная под углом, отличным от прямого, называется косоугольной проекцией.
[1]

Проекция множества определяется через проекцию кортежа.
[2]

Проекция множества, проведенная под углом 90 к оси, называется ортогональной ( или прямоугольной ] проекцией.
[3]

Проекцию множества Dt на пространство Еп обозначим через Xt, проекцию Dt на Ет — через Vt.
[4]

Проекцией множества М на i — ю ось называется и через пр ( УИ обозначается множество проекций кортежей из М на t — ю ось.
[5]

Проекцией множества М на пустое множество осей называется и через пр М обозначается множество проекций кортежей из М на пустое множество осей.
[6]

Рассмотрение проекций множества теряет всякий смысл, так как в геометрии имеют дело с множествами, элементами которых являются точки. В общем случае множество не имеет границ — оно представляет собой пространство, заполненное точками.
[7]

Неравенства, определяющие проекцию множества ( 2) на re — мерное пространство, могут быть получены следующим образом.
[8]

Отметим, что мера проекции множества конических и ребристых точек поверхности Ф2 на плоскость х, у равна нулю. В гладких точках выпуклая функция г ( х, у) имеет первый дифференциал.
[9]

Изображение поверхности на чертеже проекциями множества ее точек практически невозможно, так как эти точки заполнят все поле чертежа и нельзя будет установить проекционную связь между проекциями отдельных точек поверхности.
[10]

Обратим внимание, что задаются проекции множества X в целом, то есть неупорядоченный набор проекций его отдельных точек.
[11]

Ставится задача определения вектора, принадлежащего проекции множества пересечений гиперплоскостей на Еп, и осуществления рабочего шага вдоль этого направления.
[12]

Позднее мы обсудим, как найти проекцию множества функциональных и многозначных зависимостей.
[13]

Для построения ортогональной проекции линии необходимо определить проекции множества точек, составляющих линию.
[14]

Поэтому высказывание ЧуЭхА ( х, у) истинно, если проекция множества истинности предиката А ( х, у) на ось у совпадает со всей осью.
[15]

Страницы:

Источник

1.3 Отношения

Методы Оптимизации. Даниил Меркулов. Отделимость. Проекция. Опорная гиперплоскость

Interior

Внутренность множества

Относительная внутренность множества

Projection

Расстояние между точкой и множеством

Проекция точки на множество

Пример 1

Пример 2

Пример 3

Separation

Отделимые множества

Собственно отделимые множества

Строго отделимые множества

Сильно отделимые множества

Расстояние между множествами

Supporting hyperplane

Опорная гиперплоскость

Пример 4

Пример 5

Пример 6

Домашнее задание 3

«Теория систем и системный анализ»

Лекция 13: Операции над множествами. Упорядоченное множество

1. Объединение множеств

2. Пересечение множеств

3. Разность множеств

4. Универсальное множество

5. Дополнение множества

6. Разбиение множества

7. Тождества алгебры множеств

Дополнение к занятию «операции над множествами»

Упорядоченное множество

Прямое произведение множеств

Проекция множества.

Проекция — множество

Не пропустите также: