Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.

§ 1.5. Модель. Алгебра отношений

к — конкатенация кортежа а £ Ra и кортежа 6 € Rp (конкате

нация кортежей (aj., а2, ..., ап) и (fti, 62, • • • 1 Ьт) — кортеж (ai,

02, bi, Ь2, ..., Ьт)). Например, для рассматривавшихся

отношений Ra и Rp расширенное декартово произведение есть

Ra xRp = {(а, Ь), (с, d), (а, е)} X {(а, Ь, с), (Ь, d, е)} =

= {(а, 6, а, 6, с), (о, 6, 6, d, е), (с, d, о, 6, с),

(с, d, Ь, d, е), (а, е, а, 6, с), (а, е, 6, d, е)}.

Понятия модели и алгебры отношений находят широкое при

менение при формализации реальных объектов. Рассмотрим, как

используется алгебра отношений при создании информационного

обеспечения, т. е. при разработке реляционной базы данных.

Основой построения реляционной базы данных является двумерная таблица,

каждый столбец которой соответствует домеиу (или атрибуту, соответствующему

части домена), а каждая строка — кортежу значений атрибутов, находящихся в

отношении R. Рассмотрим 5-ариое отношение Rs (экзамены) (табл. 1.8).

Т аб ли ц а 1.8

К 5-01

ТЕОРИЯ АВТОМАТОВ

ПРОФ.

ИВАНОВ

03 ЯНВ.

АУД.210

К 5-02

МАТЕМАТИЧЕСКАЯ

ЛИНГВИСТИКА

ПРОФ.

ПЕТРОВ

03 ЯНВ.

АУД. 211

К 5-03 ФИЗИКА

ПРОФ.

СИДОРОВ

03 ЯНВ.

АУД.211

К 5-04

АЛГОРИТМИЧЕСКИЕ

ЯЗЫКИ

ПРОФ.

ПЕТРОВ

05 ЯНВ. АУД. 210

К 5-01 ФИЗИКА

ПРОФ.

СИДОРОВ

09 ЯНВ. АУД.210

К 5-02

ТЕОРИЯ АВТОМАТОВ

ПРОФ.

ИВАНОВ

09 ЯНВ.

АУД.211

7 К 5-03

АЛГОРИТМИЧЕСКИЕ

ЯЗЫКИ

ПРОФ.

ПЕТРОВ

10 ЯНВ.

АУД.211

К 5-04

МАТЕМАТИЧЕСКАЯ

ЛИНГВИСТИКА

ПРОФ.

ИВАНОВ

10 ЯНВ. АУД.210

Табл. 1.8 определяет отношение реляционной модели данных. Отношение

Rs является подмножеством декартова произведения D\ х D? х D3 х D* х Ds,

в котором сомножители являются доменами. Элементами домена Di служат

значения атрибутов. Домеи Di (группа) содержит значения К 5-01, К 5-02,

К 5-03, К 5-04:

Di = {К5 - 01, К , 5 - 02, К5 - 03, К5 - 04};

аналогично получаем домены D? (дисциплина), Di (экзаменатор), D i (дата), Ds

(аудитория):

D, = {ТЕОРИЯ АВТОМАТОВ, МАТЕМАТИЧЕСКАЯ ЛИНГВИСТИКА,

ФИЗИКА, АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ},

Гл. 1. Основы многосортных множеств

D3 =(ПРОФ. ИВАНОВ, ПРОФ. ПЕТРОВ, ПРОФ. СИДОРОВ},

Dt ={03 ЯНВ., 05 ЯНВ., 09 ЯНВ., 10 ЯНВ.},

Я5 =(АУД. 210.АУД. 211).

Порядок столбцов в таблице фиксирован, строки в общем случае могут рас

полагаться произвольно. Цифры первого столбца 1, 2, ..., 8 идентифицируют

элементы отношения Д5.

Для преобразования отношений определим реляциокную ал

гебру. Носитель реляционной алгебры представляет собой множе

ство отношений, сигнатура, кроме введенных операций (объедине

ние, пересечение, разность и расширенное декартово произведение

отношений), включает специальные операции над отношениями:

выбор, проекцию и соединение..

Операция выбора представляет собой процедуру построения

“горизонтального” подмножества отношения, т. е. подмножества

кортежей, обладающих заданным свойством.

Пример 1.3. С помощью операции выбора построить отношение R'5 (рас

писание экааменов проф. Иванова). Результатом операции выбора являются

строки, в которых домен Из представлен значением ПРОФ. ИВАНОВ; это строки

1, 6, 8 табл. 1.9).

Таблица 1.9

я*

Di D3

D3 Dt

1 К 5-01

ТЕОРИЯ АВТОМАТОВ

ПРОФ.

ИВАНОВ

03 ЯНВ. АУД. 210

К 5-02

ТЕОРИЯ АВТОМАТОВ ПРОФ.

ИВАНОВ

09 ЯНВ.

АУД. 211

К 5-04

МАТЕМАТИЧЕСКАЯ

ЛИНГВИСТИКА

ПРОФ.

ИВАНОВ

10 ЯНВ. АУД.210

Для определения проекций отношений множество в реляцион

ной алгебре разбивается на два подмножества в случае бинарного

отношения и на п подмножеств в случае n-арного отношения:

R 2 С М 2, М = А и В, АГ\В = 0 , R2CAxB;

R n С М п, М= U Ai, Aia П A ib = 0,

1 = 1

iflj Й € *2) * * • j ^ R n С A-i X A-2 X . . . X An .

Проекцией П р^г/А ) бинарного отношения R 2, R 2 С A X В,

на А называется множество элементов {а,/ (а,-, Ь,-) € Дг}.

Проекцией Пр [Rn/ Л(1, Л,-2, ..., Л,т ) п-арного отношения

Rn С Ai X А 2 х ... X Ап, п> т, на Atl, А;2, ..., А,т называется

множество кортежей (atl, a,-2, ..., a,m), где atl € Atl, a,-2 G A,-2, ...

• • •) °tm € A,m, каждый из которых является частью элемента

n-арного отношения R n.

Операция проекции определяет построение “вертикального” под

§ 1.5. Модель. Алгебра отношений 43

множества отношения, т. е. множества подмножеств кортежей, по

лучаемого выбором одних и исключением других доменов.

Пример 1.4. Проекция Пр(Й5/ D2, D3) порождает множество пар, каждая

из которых определяет дисциплину и экзаменатора (табл. 1.10).

Таблица 1.10

d 2

ТЕОРИЯ АВТОМАТОВ

ПРОФ. ИВАНОВ

МАТЕМАТИЧЕСКАЯ ЛИНГВИСТИКА ПРОФ. ПЕТРОВ

ФИЗИКА

ПРОФ. СИДОРОВ

АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ

ПРОФ. ПЕТРОВ

МАТЕМАТИЧЕСКАЯ ЛИНГВИСТИКА

ПРОФ. ИВАНОВ

Одинаковые строки в табл. 1.10 объединены в одну.

Операция соединения по двум таблицам, имеющим общий до

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

образуется соединением двух строк исходных таблиц. Из задан

ных таблиц берут строки, содержащие одно и то же значение из

общего домена; общему домену сопоставляется один столбец.

Пример 1.5. Найдем по двум заданным таблицам (табл. 1.11, 1.12) резуль

тат операции соединения по домену Di (табл. 1.13).

Т а б ли ц а 1.11

К 5-01

ТЕОРИЯ АВТОМАТОВ

ПРОФ.

ИВАНОВ

03 ЯНВ.

АУД. 210

К 5-02 МАТЕМАТИЧЕСКАЯ

ЛИНГВИСТИКА

ПРОФ.

ПЕТРОВ

03 ЯНВ.

АУД.211

К 5-03 ФИЗИКА

ПРОФ.

СИДОРОВ

05 ЯНВ.

АУД.211

К 5-04 АЛГОРИТМИЧЕСКИЕ

ЯЗЫКИ

ПРОФ.

ПЕТРОВ

05 ЯНВ.

АУД. 210

Таблица 1.12

D3 Di

К 5-01 ФИЗИКА

ПРОФ.

СИДОРОВ

09 ЯНВ.

АУД. 210

К 5-04 МАТЕМАТИЧЕСКАЯ

ЛИНГВИСТИКА

ПРОФ.

ИВАНОВ

10 ЯНВ.

АУД. 210

К 5-02

ТЕОРИЯ АВТОМАТОВ

ПРОФ.

ИВАНОВ

09 ЯНВ.

АУД. 211

К 5-03

АЛГОРИТМИЧЕСКИЕ

ЯЗЫКИ

ПРОФ.

ПЕТРОВ

10 ЯНВ.

АУД.211

Гл. 1. Основы многосортных множеств

К 5-01

ТЕОРИЯ АВТОМАТОВ

ПРОФ.

ИВАНОВ

03 ЯНВ.

АУД. 210

К 5-02 МАТЕМАТИЧЕСКАЯ

ЛИНГВИСТИКА

ПРОФ.

ПЕТРОВ

03 ЯНВ.

АУД. 211

К 5-03

ФИЗИКА

ПРОФ.

СИДОРОВ

05 ЯНВ.

АУД. 211

К 5-04

АЛГОРИТМИЧЕСКИЕ

ЯЗЫКИ

ПРОФ.

ПЕТРОВ

05 ЯНВ.

АУД. 210

Аналогично можно определить операцию соединения не только

по условию “равенства”, но и по другим условиям сравнения: >,

>, ф, <, <. Определим, например, операцию соединения по усло

вию “больше, чем” (>).

Соединением по условию “больше, чем” отношения R a по ат

рибуту X и отношения Rb по атрибуту Y (атрибуты X и Y явля

ются атрибутами одного и того же домена, общего для отношений

R a и Rb) X > Y называется множество всех кортежей 7Г; таких,

что 7Г,- — конкатенация кортежа а,-, принадлежащего R a, и кортежа

fcj, принадлежащего Rb, где X — часть a,-, Y — часть &,• и X > У.

Запрос в реляционной базе данных будет выполнен тем бы

стрее, чем меньше операций над отношениями он содержит. Та

ким образом, представляет практический интерес рассматривае

мая ниже задача упрощения представления множества через вве

денные операции (§ 1.6).

§ 1.6. Аксиоматика теории множеств,

минимизация представления множеств

Используя аксиоматический подход, формально построим тео

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

Аксиома существования. Существует, по крайней ме

ре одно множество.

Аксиома объемности (экстенциональности).Если

множества М а и Мь составлены из одних и тех же элементов,

то они совпадают (равны): М а = Мь.

Аксиома объединения. Для произвольных множеств М а

и Мь существует множество, элементами которого являются

все элементы множества М а и все элементы множества Мь

и которое никаких других элементов не содержит.

Из аксиом объемности и объединения следует, что для про

извольных множеств М а и Мь множество, удовлетворяющее усло

виям аксиомы объединения, единственно. Действительно, если бы

имелись два таких множества, MCl и М с3, то они содержали бы

§ 1.6. Аксиоматика теории множеств 45

Таблица 1.13

D'3 D't D's '

ФИЗИКА

ПРОФ. СИДОРОВ

09 ЯНВ. АУД. 210

ТЕОРИЯ АВТОМАТОВ

ПРОФ. ИВАНОВ

09 ЯНВ.

АУД. 211

АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ

ПРОФ. ПЕТРОВ

10 ЯНВ.

АУД. 211

МАТЕМАТИЧЕСКАЯ

ЛИНГВИСТИКА

ПРОФ. ИВАНОВ 10 ЯНВ. АУД.210

одни и те же элементы (все элементы, принадлежащие множеству

М„, и все элементы множества Мь), и поэтому согласно аксиоме

объемности MCl = MCj = М с. Назовем это единственное множест

во Мс объединением множеств Ма и Мь и будем писать Мс =

= М а иМ ь-

Аксиома разности. Для произвольных множеств М а и

Мь существует множество, элементами которого являются

те и только те элементы множества Ма, которые не явля

ются элементами множества Мь.

Аналогично, из аксиом объемности и разности заключаем, что

для произвольных множеств М а и Мь существует в точности одно

множество, содержащее элементы множества М„, не принадлежа

щие множеству Мь. Назовем это множество Мс разностью мно

жеств М а и Мь: Мс = М а \ Мь.

Аксиома степени. Для каждого множества М сущест

вует семейство множеств В(М) (булеан), элементами кото

рого являются все подмножества Mj, М,- С М, и только они.

Аксиома существования пустого множества. Су

ществует такое множество 0, что ни один элемент ему не

принадлежит.

Если операции и понятия теории множеств были введены ин

туитивно, то аксиоматический подход позволяет формально на

основании введенных шести аксиом определить эти операции и

понятия теории множеств.

С помощью операций объединения и разности, используя вве

денные аксиомы, определим еще три операции на множествах.

Пересечение

множеств

Ма

Мь

определяется формулой

МаПМЬ=Ма\ [Ма \ Мь).

Можно показать, что элементами пересечения М„ П Мь являются

те и только те элементы, которые принадлежат как множеству М„,

так и множеству М(,.

Дополнение М множества М определяется формулой

Гл. 1. Основы многосортных множеств

Симметрическая разность множеств Ма и Мь определяется

формулой

М а\ 9МЬ = {Ма \ Mb) U (Мь \ Ма).

На основании введенной аксиоматики можно доказать справед

ливость как приведенных выше законов, определяющих свойства

сигнатуры алгебры множеств (законы идемпотентности, комму

тативности, ассоциативности, дистрибутивности, действия с кон

стантами, двойного дополнения, законы де Моргана), так и сле

дующих законов:

закон дистрибутивности пересечения относительно разно

сти

Ма П (Мь \ М с) = МаГ\ Мь\МаП М с\

закон коммутативности симметрической разности

Ма \ *МЬ = М ь\ •Ма;

закон ассоциативности симметрической разности

Ма \'{Мь\ •Мс) = (Ма \ 9Мь)\ *МС;

закон дистрибутивности пересечения относительно сим

метрической разности

Ма П (Мь \ *МС) =МаПМь\ •Ма П Мс]

законы склеивания

Ма П Мь и Ма П Щ = Ма, (Ма U Мь) П (Ма U Щ) = Ма;

законы поглощения

Ма и Ма П М(, = Ма, Ма п (Ма U Мь) = Ма;

законы Порецкого

М а U Мо П Мь = Ма U Mb', Ма П (Ма U МЬ) = М а Г) Мь.

Используя эти законы, рассмотрим задачу минимизации пред

ставления множества М с помощью операций U, Г),

Под сложностью представления множества М будем понимать

число символов Mi, Mi в задающем его выражении.

Пусть в пространстве 1 = {Mi, Мг, Мз} задано множество вида

M (M i, Ма, Мз) = Mi Л М2 П Мз U Mi П Mi П Мз U Mi П М2 П М3 U

U Mi П Afj П Ш и Mi П М2 П Щ и Mi П Мг П М3.

На основании законов идемпотентности, коммутативности и ассоциативности

объединения получаем

M(Mi, М2, М3) = (Mi П Mj П Мз U Mi П Мг П Мз) U (Mi П Мг П Мз U

иМ ГпМ 2П Мз) U (Mi n ^ n ^ U M i n ^ n Мз) U (Mi П Щ с Ж U

и Ml П М2 П Мз) и (Ml П Мг П Мз и Ml П Мг п Мз).

§ 1.6. Аксиоматика теории множеств

Согласно ааконам коммутативности объединения и пересечения и закону склеи

вания получаем

М {М \, М2, Мз) ~ Mi Л М2 U Мз U Mj Л М3 U Mi Л М2.

Согласно законам коммутативности пересечения и поглощения имеем

M (M i, М2, Мз) — Mi л М2 U Мз U Mi Л М2.

Сложность представления заданного множества уменьшилась с 18 до 5.

Последовательность применения законов будем называть

стратегией преобразования. Сложность представления множе

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

из которых определяет эквивалентное преобразование), зависит от

используемой стратегии. Найдем стратегию, всегда порождающую

минимальное выражение заданного множества.

Рассмотрим алгебру А = (В( 1), U, П, ) и определим множе

ства, которые могут быть порождены (образованы) из произволь

ных подмножеств M j, М 2, ..., Мп, называемых порождающими

или образующими пространство 1 с помощью операций U, П,

Множество

ДЛ<*\

/ , 0 | — 1 , •

, п

Mi - 1 Mi. <r.=0. * - 1>*>

\Mi, <Ti = 0,

в дальнейшем будем называть первичным термом. Множество

вида

Л м р = М {1 П M J2 П ... П М£", <т> = 0, 1,

Назовем конституентой.

Общее число различных конституент не превышает 2П. Ка

ждой конституенте можно сопоставить двоичный набор длины п;

число этих наборов равно 2П. Если некоторые конституенты рав

ны 0, то общее количество конституент меньше 2п, при этом среди

подмножеств найдутся хотя бы два таких, которые можно выра

зить одно через другое, т. е. зависимые. Например, если в = 2 и

М2 = Мх, то существуют только две отличные от 0 конституенты:

0 = М? П М2° = M l П M j,

Ci = Мх° П M j, C2 = M l D M2°.

Лемма 1.1. Пересечение двух различных конституент

пусто.

п п а *

Действительно, если конституенты С„ = П М р и Cj = П М -'

i=i ;=i 1

различны, то сг/е ф <?% по крайней мере для одного к, к < п. Но

тогда М£* Г) Мкк = 0 и, следовательно, Са П Сь = 0.

Гл. 1. Основы многосортных множеств

Лемма 1.2. Объединение всех конституент равно 1.

Представим 1 в виде 1 = П (М° U М /), и, раскрыв скобки, в

i=i

правой части равенства получим объединение всех конституент.

Лемма 1.3. Множество Mi равно объединению конститу

ент, каждая из которых содержит М \.

Согласно лемме 1.2 1 = С\ U С2 U ... U С/ = U С,-, где С;,

i=i

г = 1, 2, . . 2П, — конституенты. Определим пересечение левой

и правой частей этого выражения с М,\ Имеем

Mi = (Mi Г) Cl) и (Mi П С2) U ... U (Mi Г) Су) и...

Если Су содержит в качестве аргумента пересечения М°, то

Mi П Су = 0. Если же Су содержит то Су П Mi = Cj. Следо

вательно, Mi — объединение тех конституент, которые содержат

М} в качестве сомножителя; число этих конституент равно 2П-1.

Теорема 1.5. Каждое непустое множество, образованное

из множеств M i, М2, • • •, М„ с помощью операций U, П, , явля

ется объединением некоторого числа конституент.

Согласно лемме 1.3 теорема справедлива для множеств M i,

М2, ..., Мп. Следовательно, достаточно показать, что если про

извольные множества Ма и Мь представимы в виде объединения

некоторого числа конституент, то и множества М„ U Мь, Ма П Мь

и М , если они не пустые, также можно представить в виде объе

динения конституент.

Пусть множества М„ и Мь представимы в виде объединения

конституент М„ = UC0jU ...U C 0jk иМь = Сь1иСь2и ...и С б,.

Тогда множество М а U Мь, очевидно, можно представить в виде

объединения конституент.

По закону дистрибутивности Ма П Мь = (Са, П Сь1) U ...

... U (Сак П Ськ)', при этом если Сш. = Cbfi, то согласно лемме 1.1

П Cbfi = 0, в противном случае Со. = Сьр. Следовательно, пе

ресечение Ма П Мь либо пусто, либо представимо в виде объедине

ния конституент. Докажем, что множество М также представимо

в виде объединения конституент, если М = Ci U С2 U ... U С*.

Согласно закону де Моргана

M = CiUC2U...UC* = ^nC2n...nCfc =

Aff11 П М%” П ... Г) ЛС" Г) М р 1 П 2 n ... n M p n D ...

... n Mf*1 П Mp* n ... n Mnkn = (M l11 U Щ а U ... и Mnln) n

n(Mf21 и ^ и . . . и ^ ) п . . . п ( ^ и л ^ и . . . и л ё ^ ) .

Раскрывая скобки и используя соотношения Ма П Ма = 0,

Ма U Ма = 1 , а также добавляя в те пересечения, в которых от

сутствует нижний индекс /?, сомножитель MpUMp, получаем, что

множество М также представимо в виде объединения конституент.

Теорема 1.6. Из п множеств в алгебре А = (-B(l), U, Г), )

можно образовать не более чем 22 множеств.

Каждое множество М согласно теореме 1.5 является объедине

нием конституент, число которых не превышает 2 П; следовательно,

число различных объединений не превышает 22". При этом если

множества М \, М2,..., Мп независимые, т. е. все конституенты

отличны от пустого множества, то число различных конституент

равно 2 П, и число множеств, образованных из этих конституент в

виде их объединения, равно 2 2 (с учетом пустого множества).

Введение понятия конституенты позволяет задавать множество

М при фиксированных независимых подмножествах Mlt М2, •..

..., Мп универсального множества 1 в виде объединения консти

туент:

м = и п м р .

j i=l •

Каждое фиксированное множество Mi С 1 разбивает простран

ство на две части: на собственно Mi и на Mi. При независимых

множествах М,- € {М ,/ i = 1 , ..., п} пространство разбивается

на2х2х...х2 = 2п областей. Каждая область является пере-

S... у . - и.-/

71 раз

сечением п множеств Mi или Mj, » = 1 , ..., п. Сопоставим этой

области двоичный вектор (&1, а2, ..., <т„), в котором <г,- = 1 , если

в пересечение С = ПМ^‘ входит М,-, и ffi = 0, если входит М;, а

также десятичный эквивалент

*(<?) = £ > • 2 '- 1.

>'=1

Любое множество М в пространстве 1 можно задать в виде

объединения этих областей. Сопоставим множеству М двоичный

вектор длины 2 П, в котором t-му разряду соответствует область

с десятичным эквивалентом, равным i. Вектор, определяющий

множество, представим в виде десятичного эквивалента:

2 "—1

d(M)= с, = 0,1.

«=о

Следовательно, множество М в пространстве может быть задано в

виде соответствующего десятичного эквивалента.

§ 1.6. Аксиоматика теории множеств 49

—

....

■ ' ■ | — 1

...

Гл. 1. Основы многосортных множеств

Рассмотрим, например, в трехмерном пространстве 1 = {Mi,

Мг, М3} множество M (Mi, М2, М3) с десятичным эквивалентом

d(M) = 217. Имеем

217 = 1 • 2 7 + 1 • 2 6 + 0 • 2 s + 1 • 2 4 + 1 • 2 3 + 0 • 2 2 + 0 • 2 1 + 1 • 2 °.

Множеству М соответствует двоичный вектор

(1, 1, 0, 1, 1, 0, 0, 1),

определяющий включение областей в множество М (рис. 1.18, а).

Кроме диаграммы Эйлера, пространство может быть задано в

виде гиперкуба или n-мерного куба (п — размерность простран

ства, равная числу фиксированных множеств).

Гиперкубом (п-мерным кубом) называется граф Н, каждая

вершина которого взаимно однозначно соответствует области про

странства, и две вершины соединены ребром, если они соответ-

Щ2(1, 3)

Ш 1,

А/3(2, 5)

з(1. 3, 4)

Л/^З, 4, 5)

Таблица 1.14

Рис. 1.18

ствуют соседним областям (имеющим общую границу). Сопоста

вленные этим областям двоичные векторы отличаются в одном и

только одном разряде.

Гиперкуб для рассматриваемого примера изображен на рис. 1.18,5 (вер

шины, соответствующие коиституентам

множества М, заштрихованы).

Часто множество М задают в виде дво

ичной таблицы, каждой строке которой

взаимно однозначно соответствует консти-

туеита. Множество строк таблицы линейно

упорядочено по возрастанию десятичного

эквивалента соответствующего двоичного

набора. Столбцам соответствуют множества,

образующие пространство, последний стол

бец сопоставляется множеству М и едини

ца указывает иа вхождение конституенты

в множество М. В данном случае имеем

табл. 1.14.

d(c) Mi

М2

Мз

1 0

0 1 0

3 0 1 1

4 1

0 0

0 1 0

7 1