Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000, страница 8

теорему 1.4). Граф называется полным, если все его вершины попарно смежны. Теорем а 1.4. Если хотя бы три различных слова, опреде,ляемые отношением Я, соответствуют полному подграуту граута с., тпо граут ст не эадаетп отношение Я. До к а за тельство. При задании словесного отношения графом будем ассоциировать определяемое слово с полным подграфом графа ст'. Тогда теорема очевидна. Действительно, достаточно зз 2 1.5. Модель. Алгебра отношений 38 1. 2) т(1 Рнс. 1.1б р(1, 2, 3) о(1, 4) а Ркс.

1.17 Гл. 1. Основы мпозосортныг множеств рассмотреть следующий пример. Пусть 3-отношение в множестве М = (в, га, о, р) определяет слова,и1 = (пз, о, р), )(2 = (р, о, в), рз = (в, пз, о), которым соответствует граф О, изображенный на рис. 1.1б, а. Это полный граф на четырех вершинах. Он может за- давать слово (в, га, о, р) или слова (и), о, р), (р, о, в), (в, о, и)), или слова (га, о), (р, о), (и)> р), (в, р), (и), в), (в, о), т. е. имеет место неоднозначность.

Для однозначного задания словесных отношений необходимо каждой букве (вершине) сопоставить множество идентификаторов слов, в которые эта буква входит. Тогда всякому слову взаимно однозначно соответствует полный подграф, каждой вершине которого соответствует идентификатор этого слова. Такой полный подграф, соответствующий слову, в дальнейшем будем называть элементным. Процесс сопоставлении каждой букве множества идентификаторов слов, в которые эта буква входит, будем называть моделизапиеб графа с'. В результате моделизации графа С каждой вершине взаимно однозначно соответствует буква, взвешеннал множеством идентификаторов слов, в которые она входит; при этом две вершины смежны (соединены линией без ориентации— ребром), если им соответствует хотя бы один общий идентификатор. Полученную таким образом на графе функцию, областью определения которой являются вершины графа, а областью значений — множества идентификаторов слов, будем называть модельным графом (мографом) и обозначать (лт = ((У, зУ), Ц.

Здесь )У вЂ” множество идентификаторов слов. Могрзфы С> н Сз > звпыошне саатветстепно отношепио о> = ((т, о, р), (р, о, в), (в, о, т)) а ьзноаестве М> = (в, и>, о, р) к Яз = ((с, о, р), > (р, и, с), (с, ы, р), (о, с, а]) п множестве Мз — — (а, и, о, р, с, ы), кзсбрвиекы з з з нв рнс. 1.1б,6, 1.17,а. Для задания Я-отношений используют также термин гинерграф. При геометрической интерпретации гиперграфа его буквы взаимно однозначно сопоставляются вершинам, слова — кругам Эйлера, которые охватывают буквы, входящие в соответствующее слово. Геометрнтесквя пнтерпрегвкия гккергрвфв, опредептошвя совокупность (М, оз), гпе М = (а, и, о, р, с, ы), Яз = ((с, о, р), (р, и, с), (с, ы, р), (о, с, а)) > квабрв>вене ив рнс.

1.17, 6. Однозначно задать Я-отношение с помощью графа можно, если в качестве носителя графа взять не только множество букв, но и множество идентификаторов слов. Такое задание Я-отношения осуществляется двудольным графом. Граф (з = (У, Ц называется двудольным (простым или графом Кенига), если его носитель разбит на два подмножества, У+ и У, не имеющих общих вершин, и начало каждой дуги и Е (? принадлежит подмножеству У+, и только ему, а конец — подмножеству У, н только ему.

При задании Я-отношений элементам подмножества У+ в двудольном графе (' = (У, ()) взаимно однозначно сопоставляют буквы, элементам подмножества У вЂ” идентификаторы слов и (р, р))) Е 1), если и только если вершина и,„ соответствует букве, входящей в слово )>)). Двудольный граф, задающий 3-отношение Яз = ((с, о, р), (р, и, с), (с, ы, р), (о, с, а) ) в 2 З множестве (а, и, о, р, с, ), изображен на рис.

1.17, в, Одним из основных в дискретной математике является понятие модели. Моделью >Р называется совокупность множества М с заданными в нем отношениями а = (4(11> Л!2» ° ° ° ГЗ!в» ЗЬ21> Г(22» ° ° Ззтпз> . ", Пт1> )(тт> ", аввы) > где множество М вЂ” иосип!ель модели, а заданные отношения В(„Щ, с М' образуют сигнагпуру модели >р = (М, Я). 41 Гл. 1. Основы многосортных мнолсесте 40 81,5.

Ут(адель. Алгебра отношений Степень носителя определяет арноспзь опзноизенид. Два отношения В и Вту, имеющие одну и ту же степень, называются совмеспзи,ными по объединению или просто совместимыми. Очевидно, что п-местную операцию у„(тг, тг, ..., т„) = = тп„бг можно рассматривать как (и+ 1)-арное отношение В„ез. Совокупность множества М с заданными в нем операциями и отношениями, следуя А.И. Мальцеву, будем называть алвеБраической сиспземой. Частным случаем алгебраической системы является алгебра отношений и ее расширение — реляционная алгебра. Рассмотрим алгебру отношений, носитель которой — множество отношений, а сигнатура — операции объединения, пересечения, разности и расширенного декартова произведения отношений.

Объединением В (т'Вд двух совместпиных отношений В и Вд является множество всех кортежей, каждый нз которых принадлежит хотя бы одному из зтих отношений. Объединение отношений В = ((а, Ь, с), (а, Ь, а), (Ь, с, е)) Вту = ((а, 6, д), (Ь, д, е), (с, д, е)) есть В 11 Вд = ((а, Ь, с), (а, Ь, т(), (Ь, с, е), (Ь, а, е), (с, д, е) ).

Рассмотренные отношения В и Вд являются совместимыми, так как их степени равны: в(В„) = в(Вь) = 3, В„Вь С Мз, М = = (а, Ь, с, т(, е). Пересечением В й Вту двух совместимых отпношений Ва и Вд является множество всех кортежей, принадлежащих как отношению В, так и отношению Вд. Пересечение отношений В и Вд для рассматриваемого примера есть В П Вр = ((а, Ь, с), (а, Ь, т(), (Ь, с, е)) П П ((а, Ь, д), (Ь, д, е), (с, а, е)) = ((а, Ь, д)). Разностпью В' 1 Вд двух совместных отношений В и Вту является множество всех кортежей, принадлежащих отношению В и не принадлежащих отношению Вд, для данного примера В ~Яд= = ((а, Ь, с), (а, 6, д), (Ь, с, е)) 1 ((а, Ь, с(), (Ь, з(, е), (с, тз, е)) = = ((а, Ь, с), (Ь, с, е)). Расширенным декартпоеым произведением В х Вд двух отпношений В и Вту является множество всех кортежей к таких, что Рз Рз АУД.

210 03 ЯНВ. ПРОФ. ИВАНОВ К $-01 ТЕОРИЯ АВТОМАТОВ АУД. 211 03 ЯНВ. ПРОФ. ПЕТРОВ МАТЕМАТИЧЕСКАЯ ЛИНГВИСТИКА К $-02 АУД. 211 АУД. 210 03 ЯНВ. 0$ ЯНВ. ПРОФ. СИДОРОВ ПРОФ. ПЕТРОВ ФИЗИКА АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ К $-03 АУД. г10 09 ЯНВ. ПРОФ. СИДОРОВ ФИЗИКА К $-01 К $-02 К $-03 АУД. 211 АУД. 211 09 ЯНВ. 10 ЯНВ. ТЕОРИЯ АВТОМАТОВ АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ ПРОФ. ИВАНОВ ПРОФ. ПЕТРОВ АУД.

210 10 ЯНВ. ПРОФ. ИВАНОВ МАТЕМАТИЧЕСКАЯ ЛИНГВИСТИКА Табл. 1.8 определяет отношение реляционной мазеля лэииыд. Отношение тсз является додмноиеством депэртовэ произведения Р, х Рз х Рз х Р, х Рз, в затором сомноиитсли являются доменами. Элементами домсив Р; слуиэт вивтения атрибутов. Домен Рз (грудзв) содсриит эивчсния Н $-01, К $.02, К $-03, Н 5-04: Р,=(кь 01,к,ь-ог,кь-оз,кь-04).

аналогично получаем домены Рз (дисциплина), Рз (эпэвменвтор), Рз (дэтв), Рз (аудитория): Рз зэ (ТЕОРИЯ АВТОМАТОВ, МАТЕМАТИЧЕСКАЯ ЛИНГВИСТИНА, ФИЗИНА, АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ), зт — конкатенация кортежа а б В и кортежа Ь б Вд (конкапзенаиид кортежей (аг, аг, ..., а„) и (6м Ьг, ..., 6„,) — кортеж (аг, аг,...,а„, 61, Ьг, ..., Ь )). Например, для рассматривавшихся отйошений В и Вд расширенное декартово произведение есть В х Вд = ((а, Ь), (с, т(), (а, е)) х ((а, Ь, с), (Ь, д, е)) = Понятия модели и алгебры отношений находят широкое применение при формализации реальных объектов.

Рассмотрим, как используется алгебра отношений при создании информационного обеспечения, т. е. при разработке реляционной базы данных. Основой построения реляционной бвэы дэниыц является двумерная таблица, зэидый столбец загорай соответствует дамену (или атрибуту, соотвзтсззузошсму масти домена), в звидвя стропэ — зортсиу энээсяий этрибутоэ, иээодюцихся э отношсзии В. Рассмотрим 5-эриое отношение Нз (эзэвмгиы) (табл. 1.8). Таблица 1.8 43 3 1.5. Модель.

Алеебро опзнотиеиий 42 Таблица 1.9 Таблица 1.11 Рз АУД. 210 03 ЯНВ. ПРОФ. ИВАНОВ К 5-01 ТЕОРИЯ АВТОМАТОВ АУД 211 03 ЯНВ. К 5-02 МАТЕМАТИЧЕСКАЯ ЛИНГВИСТИКА ПРОФ. ПЕТРОВ АУД. 211 Об ЯНВ. ПРОФ. СИДОРОВ К 5-03 ФИЗИКА АУД. 210 05 ЯНВ. ПРОФ. ПЕТРОВ К 5.04 АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ Таблица 1.12 Рз Рз Рз 09 ЯНВ.

АУД. 210 ПРОФ. СИДОРОВ ФИЗИКА К 5-01 10 ЯНВ. АУД. 210 ПРОФ. ИВАНОВ МАТЕМАТИЧЕСКАЯ ЛИНГВИСТИКА К 5-04 09 ЯНВ. АУД. 211 ПРОФ. ИВАНОВ К 5-02 ТЕОРИЯ АВТОМАТОВ 10 ЯНВ. АУД. 211 АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ ПРОФ. ПЕТРОВ К 5-03 Гл. 1. Основы мноеосортныт мнолсесте Рз =(ПРОФ.

ИВАНОВ, ПРОФ. ПЕТРОВ, ПРОФ СИДОРОВ), Р, =(03 ЯНВ., 05 ЯНВ., Оз ЯНВ., 10 ЯНВ.), Порядок столбцов в таблице фиксирован, строки в обшем случае могут располагаться пропввольпо. Кифри первого столбца 1, 2, ..., 8 ипеизифицируют злемекты отношения Нз. Для преобразования отношений определим реллциоззную алгебру. Носитель реляционной алгебры представляет собой множество отношений, сигнатура, кроме введенных операций (объединение, пересечение, разность и расширенное декартово произведение отношений), включает специальные операции нвд отношениями: выбор, проекцию и соединение.. Операция выбора представляет собой процедуру построения вгоризонтального" подмножества отношения, т. е. подмножества кортежей, обладающих заданным свойствам. Пример 1.3.

С помошью операдии выбора построить отношение Нз (расписание звзаменов проф. Иванова). Ревультатом операпкн выбора являются строки, в которыт домен Рз представлен вначеиием ПРОФ. ИВАНОВ; зто строки 1, 6, 8 табл. 1.9). Для определения проекций отношений множество в реляцион- ной алгебре разбивается на два подмножества в случае бинарного отношения и на и подмножеств в случае н-арнога отношения: В2СМ2, М=АиВ, АПВ=а, В2САхВ; В„с М", М= (.) А;, А1. ПАгз = Ы, ем 1 за,зь б111,12,...,1 ), тат=ем ВаСА1хАтх...хА„. Проекцией Пр (В2/А) бинарного отношения Вт, В2 С А х В, на А называется множество злементов (а;у (а;, 61) б Вт). Проекцией Пр(Ва/ А;„А;, ..., А; ) и-арнога отношения В„С А1 х А2 х...х А„, н > т, на А;„А;„..., А; называется ..., а; я А;, каждый из которых является частью элемента н-арного отношения В„.