Реляционные системы - Учебное пособие для студентов специальности 2201 (Вычислительные машины, комплексы, системы... Реляционные системы. Морфизм алгебраических систем. Примеры морфизмов алгебр. Учебный сайт

Реляционные системы - Учебное пособие для студентов специальности 2201 (Вычислительные машины, комплексы, системы...




reshenie-gorodskoj-dumi-goroda-nizhnego-novgoroda-ot-14-dekabrya-2011-g-n-181-o-byudzhete-goroda-nizhnego-novgoroda-na-2012-god-stranica-13.html
reshenie-gorodskoj-dumi-goroda-nizhnego-novgoroda-ot-14-dekabrya-2011-g-n-181-o-byudzhete-goroda-nizhnego-novgoroda-na-2012-god-stranica-18.html

Реляционные системы.


Алгебраическая система A= называется моделью (реляционной системой), если множество О основных её операций пусто.
Пример1
Моделью является упорядоченное множество (т.е. множество, на котором определено отношение порядка). В случае |M|= n N упорядоченное множество можно представить графом. Так, если M = {a, b, c, d, e, f, g, h}, а отношение порядка x < y, если у Гx (где х, у  М), то элементы множества могут быть упорядочены следующим образом:
Это множество частично упорядоченно, т.к. в М не все элементы сравнимы (элементы a и b, b и h, b и f ,и т.д.), однако подмножества {b, c, d, e, f}, {a,h}, {f, g, h}- линейно упорядочены (т.к. в них любые два элемента сравнимы). Элементы b и h являются в представленном орграфе минимальными, а элементы a и h – максимальными. Элементы b{b, c, d, e, f}, h{a, g, f, h}, c{c,d,e,f}, d{d,e,f}, e{f,e} являются миноратами (наименьшие элементы), а элементы a{a, h}, e{b, c, d, e}, f{b, f, g, h, e}, g{g, h}, d{c, d}, c{b, c} – максораты (наибольшие элементы), причем элемент d – верхняя грань подмножества вершин {b, c, d} и нижняя грань для подмножества {d, e, f} (часто записывают d = sup{b, c, d} и inf{d,e,f}) .
Пример 2
Подмножества множества М={а, b, с} упорядочены по включению , т.е. , есть реляционная система. Это частично упорядоченное множество реализуется орграфом, как совокупность целей (линейно упорядоченных подмножеств заданного множества М)
В этом множестве цепей можно выделить шесть максимальных цепей (линейно упорядоченные подмножества, не являющиеся собственными подмножествами других линейно упорядоченных подмножеств), которые принято изображать диаграммой Хассе:
 {a}{a, b}{a, b, c};
 {b}{a, b}{a, b, c};
 {c}{b, c}{a, b, c};
 {a}{a, c}{a, b, c};
 {b}{b, c}{a, b, c};
 {c}{a, c}{a, b, c};



Очевидно, что для упорядоченных элементов булеана B(М): sup(Mi,Mj)=MiMj; Inf(Mi, Mj) = Mi Mj;
И при этом, если Mi, Mj, MtМ, то:
sup(Mi, Mj) = sup(Mj, Mi) – (коммутативность) ;
sup(Mi, sup(Mj, Mk)) = sup(sup(Mi, Mj), Mk) – (ассоциативность);
sup(Mi, Mi) =Mi; ( идемпотентность)
inf(Mi, Mi)= Mi;
sup(Mi, inf(Mi, Mj))= Mi;
inf(Mi, sup(Mi, Mj)) = Mi ; (поглощение).
Пример 3
Моделью является решетка (структура) – частично упорядоченное множество, в котором каждое двухэлементное подмножество имеет как точную верхнюю, так и точную нижнюю грани.
Очевидно, что , где |M|=nN является решеткой.
Решеткой является и любое линейно упорядоченное множество (цепь), в котором если x, y M и x< y, то sup(x, y) = y, inf(x, y)=x .
Если М – вполне упорядоченное множество (а, следовательно, и решетка), то и
Mn = MMM….M (n раз длины n, решетка), как частично упорядоченное множество кортежей.
Примечание1
Диаграмма Хассе не является решеткой, т.к. здесь не одна нижняя грань для подмножества {d, e}, т.е. inf(d, e)=b, inf(d, e)=c
Примечание2
Частично упорядоченное множество не является решеткой, т.к. некоторые параметры (например, {d, e}, {b, c}, {g, b}, и т.д. ) не имеют верхней грани.

Примечание 3
Решетка на множестве М становится алгебраической структурой <M, f12, f22>, если определить sup(x, y) = x f12y, inf(x, y) = xf22y. В таком случае эта алгебраическая структура удовлетворяет основным тождествам (x, y, z M):
x f12x=x; x f22x=x; x f12y= y f12 x ; x f22y= y f22x;
(x f12y) f12 z = x f12 (yf12 z); (x f22y) f22 z = x f22 (yf22 z).
наоборот, если алгебраическая структура <M, f12, f22>, обладает перечисленными свойствами, то на множестве М можно задать порядок <, полагая x < y, если x f12y=y ( при этом окажется, что х< y, тогда и только тогда, когда x f22y). Возникающее в таком случае частично упорядоченное множество будет решеткой, в которой sup(x, y) = x f12y; inf(x, y) = x f22y.

Морфизм алгебраических систем.


Л
Гомоморфизм алгебр. систем
Эндоморфизм алгебр. систем
юбая область человеческих знаний исследует сам объект как гомоморфные им алгебраические системы, имеющие различное строение. В этом случае, когда сопоставляемые алгебраические системы имеют одинаковый тип, то их сходство (похожесть) характеризуются видом морфизма. Морфизм  есть обобщение понятия бинарного соответствия q= между множествами M1 и M2 на сопоставляемые алгебраические системы, т.е. =<A1, A2, m>,где m- морфизм, A1 и A2совместимые (т.е однотипные по алгебраическим операциям и отношениям) алгебраические системы, мощности несущих множеств которых могут быть различными. В этом случае, когда имеют в виду отображения компонент алгебраической системы в однотипную ей, то говорят о гомоморфизме. Ниже рассмотрим морфизм согласно приводимой классификации:
Морфизм алгебр.систем

Морфизм упорядоченных
множеств

Антиизоморфизм

Изоморфизм упорядоч. множества

Мономорфизм упорядоч. множества

Эпиморфизм упорядоч. множества

Гомоморфизм упорядоч. множества

Изоторное отображение упорядоч. множества

   
Морфизм моделей
(реляционных систем)

Эндоморфизм
алгебр

Морфизм
алгебр

Гомоморфизм
алгебр

Эндоморфизм упорядочен. множества

Антитонное отображение упорядоч. множества



 


Эпиморфизм
алгебр
Мономорфизм
алгебр
Изоморфизм алгебр

Термин «гоморфизм» есть экспликация интуитивно ясных понятий «подобие» и «сходство» структур сопоставляемых систем. Гоморфизм, как отображение элементов несущего множества М1 алгебраической системы А1 в несущее множество М2 элементов другой однотипной алгебраической системы А2, сохраняет основные алгебраические операции и отношения на сопоставляемы множествах.
Формальным определением понятия гоморфизма является следующее: «Гоморфизмом алгебраической системы А1 = < М1 ,O1 , R1> в однотипную ей систему А2 = < М2 ,O2 , R2> называется отображение Г: М1 М2, удовлетворяющее условиям:



  1. Гf(fin )=in<Гf(a1), Гf(a2),… Гf(an)>,

  2. rjm  < Гf(a1), Гf(a2),… Гf(am) pjm >, где М1n , <Гf(a1),

Гf(a2),… Гf(an)>М2n , finO1 , in O2 ; rjm R1, fjm R2 »
Поскольку отображение Г может быть сюръекцией (JmГ= М2), инъекцией (Г-1 =Гf-1) и биекцией (JmГ= М2 и Г-1 =Гf-1), то гомоморфизм соответственно называется эпиморфизмом, мономорфизмом и изоморфизмом.
Формальное определение изоморфизма (изоморфного отображения) следующее: «Изоморфизмом системы А1 на систему А2 называется функциональная биекция Гf множества М1 на множество М2, обладающее свойствами:

  1. Гf(fin )=in<Гf(a1), Гf(a2),… Гf(an)>,

  2. rjm  < Гf(a1), Гf(a2),… Гf(am) >pjm > для всех элементов <М1, О1, R1 >

Таким образом, изоморфизм есть гомоморфизм, являющийся взаимно – однозначным отображением Гf, т.е. когда Гf Гf-1= ai Мi.
Очевидно, что отношение изоморфизма обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности, разбивающим любое множество, на котором оно определено, на непересекающиеся классы эквивалентности – классы попарно изоморфных систем.
Частным случаем гомоморфизма двух алгебраических систем является эндоморфизм алгебраической системы – отображение Г: ММ алгебраической системы А= в себя, согласованное с её структурой и удовлетворяющее двум условиям:

  1. Г(fin )=fin<Гf(a1), Гf(a2),… Гf(an)>,

  2. rjm  < Гf(a1), Гf(a2),… Гf(am)> rjm для всех элементов множества .

В частности, изоморфизм алгебраической системы на себя называется автоморфизмом (т.е. это эндоморфизм, для которого существует обратный).
Замечание

  1. Реальный (исследуемый) объект, как оригинал, имеет множество гомоморфных ему моделей (которые, в свою очередь, могут быть гомоморфными между собой).

  2. примерами интерпретаций гомоморфизмов алгебраических систем могут быть объекты различной природы:

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

Примеры морфизмов алгебр.



  1. Эпиморфизмом группы <M1, f2> группу <M2, 2>, где M1={a,b,c,d,e,f}; M2={x,y,z}, а бинарные операции заданы таблицами Кэли:


f2
a
b
c
d
e
f
a
b
c
d
f
a
e
b
c
d
f
e
b
a
c
d
f
e
a
c
b
d
f
e
a
b
d
c
e
a
b
c
d
e
f
f
e
a
b
c
f
d


2
x
y
z
x
x
y
z
y
y
z
x
z
z
x
y

я
Здесь каждому элементу множества M1={a,b,c,d,e,f} поставлен в соответствие один и только один элемент в множестве M2={x,y,z}. При этом композиции любых двух элементов из множества M1 соответствует композиции их образов. Так композиции Гf(a)2 Гf(c) = Гf2 x = y = Гf(d).
вляется следующее функциональное отображение Гf: М1М :
Замечание
Графической интерпретацией морфизма двух алгебр и < M2,n> является коммутативная диаграмма:
fn : M1n  M1
x  M1n y M1
Гf
z  M2n p=(Гf y) M2
n: M2n  M2
Здесь х =< x1, x2 ,…xn >  M1n; x1, x2 ,…xn  M1 , z=< z1, z2 ,…zn >  M2n ; z1, z2 ,…zn  M2 ,
(fn< x1, x2 ,…xn >)=y, n< z1, z2 ,…zn >)=p, p M2 , zi =Гf (xi ).
Смысл приведенной диаграммы следующий: если существует гомоморфизм между двумя алгебрами А1 и А2, то можно либо выполнить операцию fn на множестве M1 и отобразить результат в множество M2, либо сначала отобразить компоненты кортежа x M1n в множество M2 и выполнить операцию n на нем. В обоих случаях результат будет один и тот же.
2. Мономорфизмом группы < M1 , f2> в группу < M2 , 2> является следующее функциональное отображение :

2
a
b
c
d
e
f
a
a





b






c






d






e






f







f2
x
y
z
x
x
y
z
y
y
z
x
z
z
x
y

3. Алгебра множеств и алгебра булевых векторов <{0,1}|M| , , , >, где
B(M)= {,< x1 , 1>} {< x2, 0>, < x2, 1>} {,< xn , 1>} изоморфны.

Действительно, пусть М= {a,b,c} и M1 = {a,b} M, M2 ={b,c}. Тогда M1 M2 = {a,b,c}, M1 M2 ={b},
M1 = {c}, M2 = {a} есть результаты применения операций в первой алгебре.
Поскольку M1 = { }, M2 = { }, то имеем булевы вектора, сопоставленные подмножествам M1 и M2 , соответственно и . Операции второй алгебры дают следующие результаты:
 = ,
 = ,
 = ,  = .
Коммутативные диаграммы в этом случае имеют вид:
{a,b}{b,c} {a,b,c}
Гf Гf


{a,b}{b,c} {b}
Гf Гf


{a,b} {c}
Гf Гf



{b,c} {a}
Гf Гf


4. Алгебры и изоморфны, т.к. |D| = | D+|, и их тип , Гf (xi) = axi , a>1, xiD, a D+, Гf (xi+ xj) = a Xi+Xj = aXiaXj; Гf -1(yj)= loga y = xi.
Из любого предложения, относящегося к сложению чисел системы D, можно извлечь соответствующее ему предложение, относящееся к умножению чисел системы D+. Так, если в D сумма Sn = x1+ x2 +….+ xn членов арифметической прогрессии выражается формулой Sn=(n(x1+ xn ))/2, что в системе D+ произведение Pn = y1 y2  …. yn членов геометрической прогрессии и выражается формулой Pn =(( y1 yn)n).

5. Тривиальным автоморфизмом является следующее отображение <M, f2> в себя:



f2
a
b
c
d
a
d
a
b
d
b
a
c
a
b
c
b
a
d
a
d
d
b
a
c
M M






  1. Нейтральным автоморфизмом системы <M, f2> может быть следующее отображение на Гf :



f2
e
a
b
c
d
f

M Гf M
e
e
a
b
c
d
f
a
a
b
e
f
c
d
b
b
e
a
d
f
c
c
c
d
f
e
a
b
d
d
f
c
b
e
a
f
f
c
d
a
b
e
Примечание:
Понятие изоморфизма играет фундаментальную роль во всех областях науки и техники. Применение номограмм, графиков и т.д. базируется на изоморфизме множества действительных чисел и точек прямой. Широко применяется изоморфизм между комплексными числами и точками плоскости; между векторами n-мерного пространства и упорядоченными n- ками чисел. В вычислительной технике и автоматике используется изоморфизм между алгеброй Буля, арифметикой чисел в двоичной системе счисления, релейными и функциональными схемами.
1. орграф 2 = является гомоморфным образом графа 1=
поскольку отображение Г: V1V2 сохраняет отношение инцидентности (принадлежности вершин ребру и наоборот).
действительно Г = > = , Г = , Г = .
Рассматривая приведенные орграфы как множество дуг, перепишем полученный гомоморфизм в виде отображения дуг Г( u1) = u3` ; Г(u2) = u1` ; Г( u3) = u2`.


V1 Г V2


2.Граф 1= изоморфен графу 2=.
Действительно, поскольку | V1| =| V2|, | U1| =| U2|,
то можно установить взаимнооднозначное соответствие (функциональную биекцию) вершин, сохраняющее отношение инцидентности.

Замечание.
Очевидно, что изоморфизм реляционных систем означает, что как первая система (оригинал) может служить моделью второй, итак и наоборот, вторая система может быть моделью первой. Именно в этом плане понятие «трансляция данных» в вычислительной технике означает изоморфизм исходной системы данных в другую (рабочую) систему данных с однотипными отношениями.
Приведем другие примеры сопоставления частично упорядоченных множеств.
Отображением Г: М1М2 называется изотопным, если оно сохраняет порядок, т.е. если xi, xj  M, xi  xj, то {  yi Г (xi)  M1,  yj Г(xj) M2 , yi  yj }
В том случае, если из xi  xjследует, что Г(xi) ≥ Г(xj), то имеют в виду антитопное отображение.
Изотопное и антитопное отображения играют роль гомоморфизмов частично упорядоченных множеств.

Пример:

Это отображение изотопно.
Пример:

Это отображение – эпиморфизм.
Пример:


Это отображение – мономорфизм частично
упорядоченных множеств.
Пример:

Это отображение – эндоморфизм частично упорядоченного множества.


Пример:
Это отображение – автоморфизм упорядоченных множеств.



Теория графов.


Теория графов – область дискретной математики, особенностью которой является топологический (геометрический) подход к изучению объектов. Предмет теории графов – граф и его обобщения (гиперграф, сеть), отражающие топологию объектов – отношения на заданном множестве вершин. Графы и их обобщения служат инженеру в его практической деятельности как моделями изделий (существующих, проектируемых) и процессов, протекающих в них (в частности информационных процессов), так и математическим аппаратом решения соответствующих задач в терминах теории графов.
Подлежащие рассмотрению вопросы представим деревом (графом без циклов, т.е. ациклическим графом):
Сети N=
ε=E0UE
Транспорт
Вершинно-взвешенные графы
Взвешенный орграф


Взвешенные орграфы с выделенными полюсами

Гиперграфы
H=

Четкий гиперграф



антицепи

Нечеткие
Cеть Петри
матроиды
графы

Нечеткий
псевдограф

нечеткий граф


mpedagog.ru