Новиков Ф.А. Дискретная математика для программистов (860615), страница 13
Текст из файла (страница 13)
Множества и отношенияDef[] Положим а = Ь = Зг (а € Bi к Ь е Bi). Тогда отношение = рефлексивно,поскольку М = U B iVa е М (3г (a € Bi)) и а е В{а е Bi к а е Bi= • а = а. Отношение = симметрично, поскольку а = Ь = > 3 г ( a e B i k b e B i )=>• Зг (b е Bi к а е Bi) =>• Ъ = а. Отношение = транзитивно, поскольку a == Ь к Ь = с = • [а] = [Ь] к [Ь] = [с] =>• [а] = [с] = • а = с.•1.7.2.
ФактормножестваЕсли R — отношение эквивалентности на множестве М, то множество классовэквивалентности называется фактормножеством множества М относительно эквивалентности R и обозначается M/R:M/RD={[x)R}xeM.Фактормножество является подмножеством булеана: M / R С 2 м . Функцияnat R: МM/R называется отождествлением и определяется следующим образом:nat R(x) =f [х] R.1.7.3. Ядро функционального отношенияи множества уровняВсякая функция / , будучи отношением, имеет ядро / о / _ 1 , которое являетсяотношением на области определения функции.ЗАМЕЧАНИЕДаже если / — функция, / _ 1 отнюдь не обязательно функция, поэтому здесь о — знаккомпозиции отношений, а не суперпозиции функций.Термин «ядро» применительно к функции / и обозначение ker / обычно резервируются для других целей, поэтому в формулировке следующей теоремы вместослова «функция» употреблен несколько тяжеловесный оборот «функциональноеотношение».ТЕОРЕМАЯдро функциональною отношения делятсяности на множестве определения.ДОКАЗАТЕЛЬСТВОПусть / : АDom / = А и 1 т / = В.отношением эквивалент-В.
Достаточно рассматривать случай, когда[Рефлексивность] Пусть а € А, Тогда 3Ь Ш В (Ь = / ( e ) )(а, Ь) 6 ! к (Ь, а) S / ' U (а, а) 6 / о Г Ка 6 f=x{b)[Симметричность] Пусть (а^вя) € / о / " 1 . Т о г д а З й (Ь = / ( щ ) к ag 6 / = 1 ( 6 ) )^ € Г[(Ь) к b - / ( а а )Ь - / Ы & «1 € Г 1 ( Ь ) ^(a3,ai) 6 / о / " 1 .^^671.8. Отношения порядкаПусть (ai,a2) G / ° / 1 и (а2,аз) G / ° /Это означает,что ЗЬ! е В (bi = / ( a i ) к а 2 е Г Ч М ) и З Ь 2 е В (b2 = f ( a 2 ) к а 3 Е f ' 1 ^ ) ) .Тогда bi = / ( a i ) к bi = f(a2) к b2 = f(a2) к b2 = /(03)61 = b2. ПоложимЬ\ — Ъ\ (или b: = 62). Тогда b = / ( a 1) & 6 = / ( a 3 )b = / ( a i ) & a 3 € f'^b)=•[Транзитивность](ai,a3) G / o /- 1.•Пусть f : AВ — функция и / о / _ 1 — отношение эквивалентиости па Dom / .Рассмотрим фактормножество D o m / / ( / о / - 1 ) .
Класс эквивалентности (элементфактормножества) — это подмножество элементов А, которые отображаются водин и тот же элемент b е В. Такие множества называются множествами уровня функции / . Ясно, что | D o m / / ( / о / - 1 ) | = | I m / | . Неформально множествоуровня функции / , соответствующее значению с, — это множество решенийуравнения f(x) = с.ПримерМножество уровня 0 для функции sin(;r) — это 7rZ.ОТСТУПЛЕНИЕТермин «множество уровня» опирается на очевидные геометрические ассоциации.
Еслинарисовать график функции одной переменной в обычной декартовой системе координат и провести горизонтальную прямую на определённом уровне, то абсциссы точекпересечения с графиком функции дадут множество уровня функции.Пример Пусть задано множество М, \М\ = п. Рассмотрим функциональноеотношение Р между булеаиом 2м и множеством неотрицательных целых чисел(мощность):Р С 2м х 0..п,гдеР: = {(X, к) \ X С М к к G 0..п к \Х\ = к} .Тогда ядром такого функционального отношения является отношение равиомощности, а множествами уровня — семейства равномощных подмножеств.1.8.
Отношения порядкаВ атом разделе определяются различные варианты отношений порядка. Отношение порядка позволяет сравнивать между собой различные элементы одного множества. Фактически, интуитивные представления об отношениях порядка уже были использованы при описании работы с упорядоченными спискамив подразделах 1.3.4=1.3.7.1.8.1. ОпределенияАнтисимметричное транзитивное отношение называется отношением порядка.Отношение порядка может быть рефлексивным, и тогда оно называется отноше=иием нестрото порядка. Отношение порядка может быть аптирефлексивпым, итогда оно называется отношением строюю порядка. Отношение порядка можетбыть линейным, и тогда оно называется отношением линейною порядка, Отпоше-68Глава 1.
Множества и отношенияиие порядка может не обладать свойством линейности, и тогда оно называетсяотношением частичного порядка. Обычно отношение строгого порядка (линейного или частичного) обозначается знаком <, а отношение нестрогого порядка —знакомОтношение порядка в общем случае обозначается знаком -<.ЗАМЕЧАНИЕДля строгого порядка свойство антисимметричности можно определить следующим образом: Уа,Ь (а < b-i(6 < а)).ПримерыОтношение < на множестве вещественных чисел является отношением строгоголинейного порядка.
Отношение ^ на множестве вещественных чисел является отношением нестрогого линейного порядка. Отношение с на булеане 2 мявляется отношением нестрогого частичного порядка.Множество, па котором задано отношение частичного порядка, называется частично упорядоченным. Множество, на котором задано отношение линейногопорядка, называется линейно упорядоченным.Пример Множество вещественных чисел упорядочено линейно, а булеап упорядочен частично.1.8.2.
Минимальные элементыЭлемент х множества М с отношением порядка -< называется минимальным вмножестве М, если в М не существует меньших элементов: - d у е М (у -< х к у ф х).Пример Пустое множество 0 является минимальным элементом булеана повключению.1Во всяком конечном непустом частично упорядоченном множествесуществует минимальный элемент.ТЕОРЕМАО Т противного. Пусть ->(3х е М (~>3у е М (у -< х к у Ф х))).Тогда Vx е М [Зу € М (у ^ х)) => 3 (и»)~ х (Vi (щ+1 -< щ) к ui+1 ф щ). Поскольку \М\ < оо, имеем Зг, j (г < j к щ = Uj).
Но по транзитивностиДОКАЗАТЕЛЬСТВОЩ >- Щ+1 У • • • У Uj =>• Щ+1 >- Uj = щ.Таким образом, щ+\ -< щ к щ+i У щ => щ+i = щ — противоречие.•691.8. Отношения порядкаЗАМЕЧАНИЕЛинейно упорядоченное конечное множество содержит ровно один минимальный элемент, а в произвольном конечном частично упорядоченном множестве их может бытьнесколько.ТЕОРЕМА 2 Всякий частичный порядок на конечном множестве может быть дополнен до линейного.ДОКАЗАТЕЛЬСТВОСМ.следующий подраздел.•ЗАМЕЧАНИЕВ данном случае слова «может быть дополнен» означают, что существует отношениелинейного порядка, которое является надмножеством заданного отношения частичногопорядка.1.8.3. Алгоритм топологической сортировкиРассмотрим алгоритм дополнения частичного порядка до линейного на конечноммножестве.Алгоритм 1.12 Алгоритм топологической сортировкиВход: конечное частично упорядоченное множество U.Выход: линейно упорядоченное множество W.while U Ф 0 doга: = min(U) { функция min возвращает минимальный элемент }yield т { включаем элемент т в множество W }U : = U - т { элемент т более не рассматривается }end whileВсякая процедура, генерирующая объекты с помощью оператора yield, определяет линейный порядок на множестве своих результатов.
Действительно, линейный порядок — это последовательность, в которой объектыгенерируются во время работы процедуры.•ОБОСНОВАНИЕФункция min возвращает минимальный элемент, существование которого гарантируется теоремой 1 подраздела 1.8.2.Вход: конечное частично упорядоченное множество U.Выход: минимальный элемент га.select га е U { выбираем любой элемент в качестве кандидата в минимальные}for и £ U doif и -< га thenт : = и { меняем кандидата в минимальные }end ifend forreturn m { элемент га минимальный }70Глава 1.
Множества и отношенияОБОСНОВАНИЕРассмотрим последовательность элементов, которые присваивались т во время работы min. Эта последовательность не может быть бесконечной,и она линейно упорядочена. Рассмотрим последний элемент этой последовательности. Этот элемент т — минимальный. Действительно, от противного, пустьсуществует и^ткифтиииевходит в последовательность. Тогда по транзитивности и меньше любого члена последовательности, и он был бы включен впоследовательность в момент своего рассмотрения.•ЗАМЕЧАНИЕЕсли отношение порядка представлено матрицей, то функцию min можно реализовать,например, так — найти в матрице отношения первую строку, содержащую только нули.1.8.4.
Верхние и нижние границыПусть X с М — подмножество упорядоченного множества М с отношением порядкаЭлемент т е М называется нижней границей для подмножества X,если Wx е X (т -< х). Элемент т е М называется верхней границей для подмножества X, если Vx е X (х -< т). Верхние и нижние границы не обязанысуществовать для любого множества и если существуют, то не всегда единственны. Если существует наибольшая нижняя граница, то она называется инфимумоми обозначается inf(X).
Если существует наименьшая верхняя граница, то онаназывается супремумом и обозначается sup(X).Пример Рассмотрим множество рациональных чисел Q с обычным отношением порядка < и его подмножество X: = {х е Q | х > 0 к х2 > 2}. Тогдае X,а ^ является одной из нижних границ множества X. Инфимума это множествопе имеет.1.8.5.
Монотонные функцииПусть А и В — упорядоченные множества и / : А —> В. Тогда еслиai -< a 2 к ai ф а2 ==• f{ai)-< / ( a 2 ) V / ( a i ) = / ( a 2 ) ,то функция / называется монотонно возрастающей. Еслиai -< a 2 к ai Ф а2 ==• / ( a 2 ) -< / ( a i ) V f(ai)= /(а2),то функция / называется монотонно убывающей. Еслиai -< а2 к а\ Ф а,2 =•f(m)•< / ( a 2 ) к f(ai)Ф /(a2),то функция / называется строго монотонно возрастающей. Еслиа{ ~< а2 к ai ф а2 = • / ( a 2 ) -< / ( a i ) к / ( a i ) ф / ( а 2 ) ,то функция / называется строго монотонно убывающей.
Монотонно возрастающие и убывающие функции называются монотонными, а строго монотонно возрастающие и убывающие функции называются строго монотонными соответственно. Очевидно, что строго монотонная функция монотонна, но обратноеневерно.711.8. Отношения порядкаПримеры1. Тождественная функция у = х для чисел является строго монотонно возрастающей, а функция знака числа sign(x) = f if х < 0 then - 1 elseif х > 0 then1 else 0 end if является монотонно возрастающей.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
