Новиков Ф.А. Дискретная математика для программистов (860615), страница 10
Текст из файла (страница 10)
Упорядоченные пары и наборыЕсли а и b — объекты, то через (а, Ь) обозначим упорядоченную пару. Равенствоупорядоченных пар определяется следующим образом:(а, Ъ) = (с, d) = f а = с & b = d.Вообще говоря, (а, Ь) ф (Ь, а).ЗАМЕЧАНИЕФормально упорядоченные пары можно определить как множества, если определить ихтак: (а,Ь) = {а, {а, Ь}}. Таким образом, введённое понятие упорядоченной пары пе выводит рассмотрение за пределы теории множеств.Аналогично упорядоченным парам можно рассматривать упорядоченные тройки,четвёрки и т.
д. В общем случае подобные объекты называются n-ками, кортежами, наборами или (конечными) последовательностями. Упорядоченный набориз п элементов обозначается ( a i , . . . , а п ). Набор ( a i , . . . , а п ) можно определитьрекурсивно, используя понятие упорядоченной пары:( а ь . . . , а п ) =f ( ( a i , . . . , a n _ i ) , а п ) .Количество элементов в наборе называется его длиной и обозначается следующим образом: | ( a i , .
. . , а п )\.ТЕОРЕМАДва набора одной длины равны, если равны их соответствующие эле-менты:Vn ^ ( a b . . . , a n ) = ( 6 i , . . . , b n )Да» = ^•491.4. ОтношенияИндукция по п. База: при п = 2 по определению равенстваупорядоченных пар. Пусть теперьДОКАЗАТЕЛЬСТВО71 — 1( а ь . . . , a n _ i ) = (bi,... ,b n _i)Д а, = bi.г= 1Тогда( а ь . . .
,а„) = ( 6 i , . . . ,ЬП)-Ф=>( ( a i , . . . , a n _ i ) , a n ) = ( ( b i , . . . ,6„_i) ,Ь„)( а ь . . . , a n _ i ) = ( b i , . . . , 6 n _ i ) к ап = bnn-1Д ai = 6».•г=1Отсюда следует, что порядок «отщепления» элементов в рекурсивном определении кортежа не имеет значения.ЗАМЕЧАНИЕНаиболее естественным представлением в программе n-ки с элементами из множества Аявляется массив array [l..n] of А.1.4.2.
Прямое произведение множествПусть А и В — два множества. Прямым (декартовым) произведением двух множеств А и В называется множество всех упорядоченных пар, в которых первыйэлемент принадлежит А, а второй принадлежит В:АхВ = f {(а,Ь) | а G А & beВ}.ЗАМЕЧАНИЕТочка на плоскости может быть задана упорядоченной парой координат, то есть двумяточками на координатных осях.
Таким образом, R 2 = 1 х К. Своим появлением методкоординат обязан Декарту1, отсюда и название «декартово произведение».ТЕОРЕМАДля конечных множеств А и В \А х В\ = \А\ \В\.Первый компонент упорядоченной пары можно выбрать \А\способами, второй — | £ | способами, причём независимо от выбора первого элемента. Таким образом, всего имеетсяразличных упорядоченных пар.•ДОКАЗАТЕЛЬСТВО1Реле Декарт ( 1 5 9 6 - 1 6 5 0 ) .50ЛЕММАГлава 1. Множества и отношения[Ах В)х С ~ А х (ВхС).ДОКАЗАТЕЛЬСТВО(Ах В) х С ={((а,Ь)с) |(а, Ь) GА х В к с 6 С} == {(а, Ь, с) \ а е. А к b € В к с £ С}~ {(а, (6, с)) | а е А к{Ь,с) € 5 х С} = Л х [В х С).•Понятие прямого произведения допускает обобщение. Прямое произведение множеств А1у..., Ап — это множество наборов (кортежей):Ai х • • • х Ап = f { ( a i , .
. . ,ап) | ai в A\ k ... k aTl € An) .Множества Л/ не обязательно различны.Степенью множества А называется его n-кратпое прямое произведение самогона себя. Обозначение:Ап =' А х ••• х А.п рпаСоответственно, А[ =' А, А'2 =' Ах А и вообще Ап = f А х А п ~ 1 .СЛЕДСТВИЕ|ЛП| =|Л|П.1.4.3. Бинарные отношенияПусть А и В — два множества. Бинарным отношением между множествами А иВ называется тройка (A,B,R), где R — подмножество прямого произведения Аи В:RcAxB.R называется графиком отношения, А называется областью отправления, а. В —областью прибытия. Если множества А и В определены контекстом, то частопросто говорят, что задано отношение R. При этом для краткости отношениеобозначают тем же символом, что и график.ЗАМЕЧАНИЕПринято говорить «отношение между множествами», хотя порядок множеств имеет значение, и отношение между А и В совсем не то же самое, что отношение между В я А.Поэтому иногда, чтобы подчеркнуть это обстоятельство, употребляют оборот «отношениеR из множества А в множество В».511.4.
ОтношенияСреди элементов множеств А и В могут быть такие, которые пе входят ии в однуиз пар, определяющих отношение R. Множество элементов области отправления,которые присутствуют в парах отношения, называется областью определенияотношения R и обозначается БошЛ, а множество элементов области прибытия, которые присутствуют в парах отношения, называется областью значенийотношения R и обозначается Im R\DomR = {абЛ\3beB1тД =({ЬеВ\Зае((а,6) £ Д)} ,А ((a,b)eR)}.Если А = В (то есть R с Л 2 ), то говорят, что R есть отношение на множестве А.Для бинарных отношений обычно используется инфиксная форма записи:aRb = f (а,Ь)€ R c АхВ.Инфиксная форма позволяет более кратко записывать некоторые формы утверждений относительно отношений:aRbRc s1 (а, Ь) € R k {Ь} с) € R.ПримерыПусть задано множество U.
Тогда 6 (принадлежность) - отношение между элементами множества U и элементами булсапа 2' ; , а с (включение) и - (равенство) — отношения на 2й. Хорошо известны отношенияопределённые на множестве вещественных чисел.Пусть R есть отношение между А и В: R с А х В. Введём следующие понятия:Обратное отношение:я-1 = { М ) IДополнение отношения:R = {(a, b) | (а, b) £ R} с А х В.Тождественное отношение:I = f {(а, а) | а € А} с А2.Универсальное отношение:U — {(а, b) | а е А к b € В} = А х В.а) G R} С В х А.DefЗАМЕЧАНИЕГрафик тождественного отношения на множестве А иногда называют диагональю в Ах А.Введем обобщённое понятие отношения: п-местное (п-арное) отношение R —это подмножество прямого произведения п множеств, то есть множество упорядоченных наборов (кортежей):DefR С Ах х • • • х Ап = { ( а ь ..., ап) \ аг <Е Ai к ...
к ап € Ап} .52Глава 1. Множества и отношенияЗАМЕЧАНИЕЧисло п, то есть длину кортежей отношения, называют иногда вместимостью.ОТСТУПЛЕНИЕМногоместные отношения используются, например, в теории баз данных. Само название«реляционная» база данных происходит от слова relation (отношение).Далее рассматриваются только двуместные (бинарные) отношения, при этомслово «бинарные» опускается.1.4.4. Композиция отношенийПусть R\ с А х С — отношение между Aw С, а Яг С С х S - отношение междуС и В. Композицией двух отношений R\ и Я 2 называется отношение R с А х Вмежду А и В, определяемое следующим образом:R =f#iой2=f{(M)I aeAkbeBкЗсеС(aRlC кcR2b)}.Другими словами,aRi о R2bТЕОРЕМАV ДхСЗсеС(aR\c кcR2b).Композиция отношений ассоциативна, то естьА х В, R2СВ х С, Я 3СС х D ((Ях о Я 2 ) о Я 3 = Ri о (Я 2 о Я 3 )).ДОКАЗАТЕЛЬСТВОa(Ri о Я 2 ) о R3d ^^ЗсеС(aRi о Я 2 с к cR3d)Зс <Е С ( ( З б е Я (аЯхб & bR2c)) к cR3d)^3 Ь 6 В, с е С (аЯхб к bR2c к cR3d)^ З Ь е В (aRib к(ЗсеС(bR2c к3 Ь е В (aRib к bR2 о R3d)cR3d)))аЯх о (Я 2 о R3)d.•Композиция отношений на множестве А является отношением на множестве А.Пример Композиция отношений < и ^ на множестве вещественных чиселсовпадает с отношением с < о ^ = <.ЗАМЕЧАНИЕВ общем случае композиция отношений не коммутативна, то есть R\ о R2 Ф R2 о Ri.Пример На множестве людей определены отношения кровного родства и супружества.
Отношения «кровные родственники супругов» и «супруги кровныхродственников» различны.531.4. Отношения1.4.5. Степень отношенияПусть R — отношение на множестве А. Степенью отношения R па множестве Аназывается его n-кратная композиция с самим собой. Обозначение:Rn='до---ой,п разСоответственно, R° =f I, R1 =f R, R? =f R о R и вообще Rn =f Rn~l о R.Если некоторая пара (а, Ь) принадлежит какой-либо степени отношения R на множестве А мощности п, то эта пара принадлежит и некоторой степени R не выше п — 1:ТЕОРЕМАRC А2 к \А\ =п=>ДОКАЗАТЕЛЬСТВОУ a,beА (3 k (aRkb)(aRhb)) .3 к<пПо определению(а, b) е RK => 3ci,...,ck-iДалее, если \А\ = п к к ^ п, то 3 i,jе А (с)0 RCIRC2R.
..Rck-XRck.(Cj — Cj к i Ф j), и значит,CQRC\R . . . RciRcj+\R...Rck-\Rck,то есть (a, b) еОбозначим через d процедуру, которая вычисляет паручисел ( i , j ) . Существование требуемого числа к (степени отношения R) обеспечивается следующим построением:while к ^ п doс 0 : = а; ск:=Ь( i , j ) : = d()к: = к- ( j - г)end whileСЛЕДСТВИЕ•R С А2 к \А\ = пЦ=1 R i =UlTi1 R i -1.4.6.
Свойства отношенийПусть R с А2. Тогда отношение R называетсярефлексивным,если Va е А (aRa);антирефлексивным,если Va е А (-*aRa);симметричным,если Va, b е A (aRb ==> bRa);антисимметричным,если Va,b е A (aRb k bRa ==$• а = Ь);транзитивным,если Va, b, с е A (aRb к bRc =>• aRc);линейным,если Va, 6 е А (а = b V aRb V bRa).54Глава 1. Множества и отношенияЗАМЕЧАНИЕИногда линейное отношение R называют полным. Такой термин является оправданным,поскольку для любых двух различных элементов а и b либо пара (а,Ь), либо пара (Ь, а)принадлежит отношению R. Отношение, не обладающее свойством полноты, при этомвполне естественно называть частичным. Однако использование термина «полное отношение» может порождать терминологическую путаницу.
Дело в том, что устойчивое словосочетание «вполне упорядоченное множество», рассматриваемое в подразделе 1.8.6, оказывается созвучным словосочетанию «множество с полным порядком», хотя эти словосочетания обозначают существенно различные объекты. Во избежание неоднозначности мыиспользуем термин «линейное отношение» как антоним термина «частичное отношение».ТЕОРЕМАПусть Я с Л х А — отношение на А.
Тогда:1. Rрефлексивно2. Rсимметрично3.I с R;\v R = Я •'•jЯRmpamumueHoОЯ с Я;4. RантисимметричноЯ П Я " 1 = /;5. RантирефлексивноЯП / = 0;6.я и / и яRлинейноДОКАЗАТЕЛЬСТВО- 1= U.Используя определения свойств отношений, имеем:[ 1. <!=> ] Va G A (aRa) <=i> VaeA((a, a) G R) <=> I С R.[ 2. <=• ] Va,ft G A (aRb => bRa)Va, b G A ((a, ft) G Я(b, a) G R)Va,b £ A (((a, ft) G R = > (ft, a) G R) k ((ft, a) G R => (a, b) G R))V a , b £ A (((a,ft) G R=> (a,b) G Я " 1 ) k ((a,ft) € Я " 1(a,b) G R))^ f i C Я " 1 k R~l С R <=> Я = R-\[ 3.] VA,FT,с G A (aRb k bRc =• aRc) <=*Va, ft, r: G Л ((a, ft) 6 Я & (6, с) G R = • (a, с) G Я)Va,С G Л (3 ft G D ((a, ft) G Я & (FT, C) G Я) ==• (a, C) G Я) <*=>•Va, с € Л ((a, с) G R о R.(a, c) G Я) <=>(аЯ о Яс ==> аЯс)Я о Я С Я.[ 4.] От противпого.
ЯП Я - 1 ^ / =>• За ^ ft (аЯй & о/2~16)З а ^ ft (aRb k[ 4.] Я П Я"1bRa).= / = • (aRb к a,R~lbа =ft)(аЯЬ & ЬЯаа = ft).[ 5. =>. ] От противпого. Я П / ^ 0 = >З а G Л (аЯа & а / а )[ 5.З а G Л (аЯа)^ V a G Л (-паЯа).] Я П / = 0 ==> S a £ А (аЯа) = Ф Va G Л (-.аДа).[ 6. <!=> ] Va, ft G Л (а = ft V aRb V ЬЯа)Va, ft G Л ((a, b) £ I V (a,b) £ R V (a, ft) G Я - 1 )с/ с / и я и я - 1С/ = Я и / и Я " 1 .•551.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
