Новиков Ф.А. Дискретная математика для программистов (860615), страница 11
Текст из файла (страница 11)
Отношения1.4.7. Ядро отношенияЕсли Л с А х В — отношение между множествами А и В, то композицияназывается ядром отношения R и обозначается ker R. Другими словами,aiker Ra2ЗЬ е В (aiRb кRoR-1a2Rb).Ядро отношения R между А и В является отношением на А:R С А х В => ker R с А2.Примеры1. Пусть отношение N\ «находиться на расстоянии не более 1» на множествецелых чисел определено следующим образом:N i : = { ( n , т ) | \п — га| ^ 1} .Тогда ядром этого отношения является отношение N2 «находиться на расстоянии не более 2»:N2: = {(n,m) | \п - m\ ^ 2} .2. Ядром отношения «быть знакомыми» является отношение «быть знакомымиили иметь общего знакомого».3.
Ядро отношения е между U и 2и универсально: Va,Ъ е U ({а, Ь] е 2и).4. Ядро отношения С на 2и также универсально.5. Рассмотрим отношение «тесного включения» на 2и\X c Y =fX c Y k \X\ + 1 = \Y\.Ядром отношения с1 является отношение «отличаться не более чем однимэлементом»:ker С = {X,Y€ 2и \ \Х\ = |У| к \Х П Y\ > |Х| - l } .ЗАМЕЧАНИЕТермин «ядро» и обозначение ker используются также и для других объектов. Их песледует путать — из контекста обычно ясно, в каком смысле используется термин «ядро».ТЕОРЕМАЯдро любого отношения рефлексивно и симметрично на области опре-деления:VЛ С Л х Б (Va G DomR ( a k e r R a ) k Va,6 G D o m R ( a k e r R b =>bkerRa)).ДОКАЗАТЕЛЬСТВО[ Рефлексивность ] Пусть a e DomR.
Тогда 3b £ В (aRb)=> 3b e В (aRb k bR~1a) => (a,a) € RoR'1aker Л a.[ Симметричность ] Пусть a, be Dom Л k a ker Л b. Тогда Зс e В (aRc k=>3ceB(bRc k cR~la) =>• (b, a) e Ro Л - 1 ==>• 6 ker Л a.cR~lb)•56Глава 1. Множества и отношения1.4.8. Представление отношений в программахПусть R отношение па A, R с А2 и \А\ = п.
Перенумеруем элементы множества А, А = { a i , . . . ,ап}. Тогда отношение R можно представить булевой матри[г, j] = cuRaj^j.цеи R : array [l..n, 1 ..п] of 0..1, где Vг, j е 1 ..пЗАМЕЧАНИЕТермин «булева матрица» означает, что элементы матрицы — булевские значения и операции над ними выполняются по соответствующим правилам (глава 3). В частности, еслиI А | и | В | — булевы матрицы, то операции па ними определяются следующим образом:| А \ [i,j] = f |~л] [?, г];транспонирование:вычитание-.- |~в|) [i, j] ==0[®> Jl &~0инвертирование-. \ А | [г, j] =' 1 — А [г, j];А | х В ^ [i,j] = f \/умножение:| Й1 V R2 ^ [i,j] = f Riдизъюнкция:[г, к] &; В_[ i , j ] V R2 [i,j].В следующих утверждениях предполагается, что все рассматриваемые отношения определены на множестве А, причём \А\ = п.ТЕОРЕМА1R -1ДОКАЗАТЕЛЬСТВОR(6, a ) e R1( a , b) е RR[a, b] = 1R[6, a] = 1.•В универсальное отношение U входят все пары элементов, поэтому все элементыматрицы универсального отношения U равны 1.иR-Ь) е R(иСЛЕДСТВИЕR—R-.R ) м(a, b) £ R= 1.R[а, Ь] = 0и•571.5.
Замыкание отношенийТЕОРЕМА 3о Д2ДОКАЗАТЕЛЬСТВО(A,B)Д2.е R\ о R24Зс е А (aRxc к cR2b)[с, 6] = l ) Ф ^ З с е А ( ( И f 'Rk&ИЗСc ьf' 0=1)ЕА^(]~йГ[ х [д7[) [а, 6] = 1.•RR\ U Д2ДОКАЗАТЕЛЬСТВО= 1х[a,fc]& [йТ] [А;, Ь]^ = 1СЛЕДСТВИЕТЕОРЕМАДхa([ДП [а, с] = 1 & Щ^ V=(A,b)-RiVЕ ДХИД2д2aR\b\JaR2bД1 [а,ft]= 1 V Д 2 [а, ^ =V |~йГ[) [а,ft]= 1.ПЗАМЕЧАНИЕПредставление отношений с помощью булевых матриц — это только один из возможныхспособов представления отношений. Другие варианты рассматриваются при обсуждениипредставления графов в главе 7.1.5.
Замыкание отношенийЗамыкание является весьма общим математическим понятием, рассмотрение конкретных вариантов которого начинается в этом разделе и продолжается в другихглавах книги. Неформально говоря, замкнутость означает, что многократное выполнение допустимых шагов не выводит за определённые границы. Например,предел сходящейся последовательности чисел из замкнутого интервала [a,ft]обязательно принадлежит этому интервалу, а предел сходящейся последовательности чисел из открытого (то есть не замкнутого) интервала (a, ft) может лежать внеэтого интервала.
В некоторых случаях можно «расширить» незамкнутый объекттак, чтобы он оказался замкнутым.1.5.1. Транзитивное и рефлексивное замыканиеПусть Д и R' — отношения па множестве М. Отношение R' называется замыканием R относительно свойства С, если:1) Д' обладает свойством С:С(Д');2) R' является надмножеством Д:Д С Д';3) Д' является наименьшим таким объектом:C(R") & Д с R"Д' с R".58Глава 1. Множества и отношенияПусть R+ — объединение положительных степеней R, a R* — объединение неотрицательных степеней R:ооТЕОРЕМАi= 1R+ — транзитивное замыкание R.оог=0Проверим выполнение свойств замыкания при условии, чтосвойство С — это транзитивность.ДОКАЗАТЕЛЬСТВО[С(Я+) ] Пусть aR+b & bR+c. Тогда З п (aR n b) & 3 m (bRmc). Следовательно,3 c i , .
. . , c n _ i (aRc\R... Rcn-\Rb) и 3 d i , . . . , d m _ i (bRd\R... Rdm-\Rc).Такимобразом, aRc\R... Rcn-\RbRdiR...Rdm_iRc ==> aRn+m+1caR+c.oo[ R с R+ ] R — R1 ==>• R с U R l ^ R c R + .i=i[ C(R") & R с R" ==• Я + с Л" ] аД+ЬЗА; (аД*Ь) =Ф3 c i , . . . , c f c _ i (aRc\R... Rck-iRb); R С R" =>• aR"ciR"=>• аЯ"Ь. Таким образом, i? + с Д".ТЕОРЕМАЯ* —ДОКАЗАТЕЛЬСТВО... R"ck-iR"b=>•рефлексивное транзитивное замыкание R.Упражнение 1.5.•Вычислить транзитивное замыкание заданного отношения можно следующимобразом:Т1 — 1д+ = [_|д« = I ]г=1г=1п— 171 — 1у[дМ = V [яГ-г=1г=1Такое вычисление будет иметь сложность 0 ( п 4 ) .1.5.2.
Алгоритм УоршаллаРассмотрим алгоритм Уоршалла1 вычисления транзитивного замыкания отношения R на множестве М, \М\ = п, имеющий сложность 0 ( п 3 ) .Алгоритм 1.11 Вычисление транзитивного замыкания отношенияВход: отношение, заданное матрицей R: array[1..n, l..n] of 0..1.Выход: транзитивное замыкание отношения, заданное матрицейТ: array[l..n, l..n] of 0..1.S: = Rfor i from 1 to n dofor j from 1 to n do1Стсфап Уоршалл (p. 1935).for к from 1 to n doT{j,k]: = S\j,k] V S[j,i] к S[i,k]end forend forS: = Tend forНа каждом шаге основного цикла (по г) в транзитивное замыкание добавляются такие пары элементов с номерами j и к (то есть T[j, к]: = 1), длякоторых существует последовательность промежуточных элементов с номерамив диапазоне 1 .
. . г, связанных отношением R. Действительно, последовательностьпромежуточных элементов с номерами в диапазоне 1 . . . г, связанных отношением R, для элементов с номерами j и к существует в одном из двух случаев:либо уже существует последовательность промежуточных элементов с номерамив диапазоне от 1 . . . (г — 1) для пары элементов с номерами j и к, либо существуют две последовательности элементов с номерами в диапазоне от 1 .
. . (г — 1) —одна для пары элементов с номерами j и г и вторая для пары элементов с номерами i и к. Именно это отражено в операторе T\j,k]:=S\j,k]V S[j, г] к 5[г,/с].После окончания основного цикла в качестве промежуточных рассмотрены всеэлементы, и, таким образом, построено транзитивное замыкание.•ОБОСНОВАНИЕ1.6.
ФункцииПонятие «функция» является одним из основополагающих в математике. В данном случае подразумеваются прежде всего функции, отображающие одно конечное множество объектов в другое конечное множество. Термин «отображение» мы считаем синонимом термина «функция», но различаем контексты употребления. Термин «функция» используется в общем случае и в тех случаях,когда элементы отображаемых множеств не имеют структуры или она ни важна. Термин «отображение» применяется, напротив, только в тех случаях, когда структура отображаемого множества имеет первостепенное значение. Например, мы говорим «булева функция», по «отображение групп». Такое предпочтение слову «функция» оказывается в расчёте па постоянное сопоставлениечитателем математического понятия функции с понятием функции в языкахпрограммирования.1.6.1.
Функциональные отношенияПусть / — отношение между А и В, такое, чтоVa ((a, b) € f к (а, с) е f => b = с).Такое свойство отношения называется однозначностью, или функциональностью,а само отношение называется функцией из А в В, причём для записи используется одна из следующих форм:f: АВилиАВ.60Глава 1. Множества и отношенияЕсли b = /(а), то а называют аргументом, a b — значением функции. Если изконтекста ясно, о какой функции идет речь, то иногда используется обозначение а ^ Ь. Поскольку функция является отношением, для функции / : А —> Вможно использовать уже введенные понятия: множество А называется областьюотправления, множество В — областью прибытия иобласть определения функции:область значений функции:DefDom / = {а £ A\3bDefI m / = {ЬеВ\ЗаеА£ В (6 = /(а))};(b = f(a))}.Область определения является подмножеством области отправления, Dom / с А,а область значений является подмножеством области прибытия, Im / с В.
ЕслиDom / = А, то функция называется тотальной, а если Dom / ф А — частичной.Сужением функции / : А —> В па множество М с А называется функция / | м .определяемая следующим образом:Def/ | м = {(а, 6) | (а, 6) € / & а € М } = / П ( М х В).Функция / называется продолжением д, если д является сужением / .ОТСТУПЛЕНИЕИ математике, как правило, рассматриваются тотальные функции, а частичные функции объявлены «ущербными». Программисты же имеют дело с частичными функциями,которые определены не для всех допустимых значений.
Например, математическая функция х2 определена для всех х, а стандартная функция языка программирования sqr даётправильный результат отнюдь не для всех возможных значений аргумента.Далее, если явно не оговорено противное, речь идёт о тотальных функциях, поэтому области отправления и определения совпадают.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
