Дискретная математика (998286), страница 8
Текст из файла (страница 8)
Здесь рассматриваются классы отношений, обладающих определенным набором свойств. Такое «абстрактное» изучение классов отношений обладает тем преимуществом, что один раз установив некоторые следствия из наличия у отношения определенного набора свойств, далее эти следствия можно автоматически распространить на все конкретные отношения, которые обладают данным набором свойств. Рассмотрение начинается отношениями эквивалентности (в этом разделе) и продолжается отношениями порядка (в следующем разделе).
Глава 1. Множества и отношения 1.7.1. Определение рефлексивное симметричное транзитивное отношение называется отношением экаивалентностла. Обычно отношение эквивалентности обозначают знаком ш. Пример Отношения равенства чисел и множеств являются отношениями эквивалентности. Отношение равномощности множеств также является отношением эквивалентности. Другие, более интересные примеры отношений эквивалентности приведены в последующих главах книги. 1.7.2. Классы эквивалентности Пусть ш — отношение эквивалентности на множестве М и х Е М.
Подмножество элементов множества М, эквивалентных х, называется классам эквивалентности для х: [х]=:=(у ] в Е Мйу мха Если отношение подразумевается, то индекс ш обьгчно опускают. ЛЕММА 1 'т'а Е М [а] Эв И. ДОКАЗАТЕЛЬСТВО а ш а =Ф а Е [а] ЛЕММА 2 а ш Ь =ь [а] = [Ь]. доказательство Пусть а ж Ь.
Тогда х Е [а] =ь х ш а й а и 6 =ь х ш Ь =ь х Е [Ь]; х Е [Ь] =ь х ш Ь =ь х ш Ьй а ш Ь =~ х ш Ь й Ь ш а =ь х ш а =ь х Е [а]. ЛЕММА 3 а 1в Ь =ь [а] П [Ь] = И. Доказательство От противного: [а] П [Ь] ф Е =~ Э с Е [а] и [Ь] =я с Е [а] й с Е [Ь] =ь =ь с ю а й с и Ь =ь а ш ей с ш Ь ==о а ш Ь. а Т. Отношении эквивалентности ТЕОРЕМА Всякое отношение эквивалентности на множестве:М определяет раз биение множеппва М, причем среди элементов разбиения нет пустых„и обратно, всякое разбиение множества М, не содержащее пустъи элементов, определяет отношение эквивалентности на множестве М: шс Мз е=ь д З = (В ( В; с М й В; Р' а й М = Ц В; й Ы г, У т -,6 у =ь =ь В; й В = ю. ДОКАЗАТЕЛЬСТВО Необходимость Построение требуемого разбиения обеспечивается следующим алгоритмом.
Вход: множество М, отношение эквивалентности ш на М. Выход: разбиение З множества М. У:=М„З:=и ЬВеи~шдо эе!ест а е У ( возьмем любой элемент из М ] А: = ЕЧ(а, М, ш) ( построим его класс эквивалентности т У:=УА ( удалим класс из множества 3 З: = З и (А] ( и добавим в разбиение ] еад чИе Функция Ео обеспечивает построение класса эквивалентности: Вход: элемент а из множества М, отношение эквивалентности ш на М.
Выход: последовательность элементов, образующих класс эквивалентности А. гог 6 е М до К 6 э— э а гйео у1ега 6 еид И епд гог гетаго А Достаточность. Положим а и Ь: = 3 т а Е В, й Ь Е В,. Тогда 1. рефлексивность: М = юг =ь Ыа е М 3 г а Е В;; а Е В; =ь а Е В, й а Е В; =ь а ш а; 2. симметричность: а ш Ь =ь Э з а е В; й Ь е В; =ь Зт' Ь е В; й а е В; =ь Ь ш а; 3. транзитивносттс а ш Ь й Ь ш с =~ [а] = [Ь] й[Ь] = [с] =ь [а] = [с] =ь а ш с 1.7.3.
Фактормножестша Если  — отношение эквивалентности на множестве М, то множество классог эквивалентности называется фактормножеспшаи множества М по эквивалент. ности В и обозначается М/В: М~В: =([к]ЛЬем 44 Глава 1. Множества и отношения Фактормиожество является подмножеством булеаигс М/В с 2лс. Функция пас В: М -+ М/В называется опюждествлением и опрЬделяется следующим образом: пас В(х): =(х)я. 1.7.4. Ядро функции Всякая функция, будучи отношением, имеет ядро. Ядро функции Г" обозначается Ьяг у: )сег ~: = Г" о Г' ТЕОРЕМА Ядро функции является отношением эквивалентности на области определения функции. Доказательство Пусть Г: А -т В. Не ограничивая общности, можно считать, что Гл = А и Гв = В. Тогда ЧЬ Е В Э а Е А Ь = Г" (а) й Ча Е А Э Ь Е В Ь = Да), )сег Г' = ((ас, аз) ! ам аз Е Ай Э 6 Ь = )(ат) йаз Е У (6)); Рефлексивность.
Пусть а Е А. тогда э 6 я В ь = Г(а) =ь а е Х 1(ь) =ь (а, ь) е э й(ь, а) е У ~ ~ =ь(а,а) иуос' Симметричность. Пусть (ат,аз) Е э' о У '. Тогда ЭЬ Ь = у(ат) йаз Е У '(Ь) ~ ат Е у '(Ь) й Ь = У(аз) =ь =ь Ь = Г'(аз) й ат Е с ~(Ь), я (аз, ат) Е у о у Транзитивнасть. Пусть (ат,аз) Е у о у 1 и (аз,аз) Е у о у ~. Это означает, что Э Ь, Е В Ьт — — у(а1) й аз Е у '(61) и ЭЬз Е В Ьз = у(аз) й аз Е у '(Ьз).
Тогда 61 —— Дат) й61 — — У(оо)йЬз = ~(аз) йЬз = 1(аз) =ь Ьт — — Ьз. Положим Ь:=Ь1 (или Ь: =Ьз). Тогда Ь = 1(ас) йЬ = Г'(аз) =ь Ь =- Г(ас) йаз е Г' (Ь) =ь =н (ат,аз) Е У о У ~. (э Прммвр Мощность множества является функцией из множества конечных множеств в множество неотрицательных целых чисел. Ядро этой функции — это отношение равиомощиости, которое является, таким образом, отношением эквивалентности. 1.8. Отношения порядка В этом разделе определяются различные варианты отношений порядка. Отиошеиие порядка позволяет сравнивать между собой различные элементы одного множества. Фактически, интуитивные представления об отношениях порядка ЬВ. Отношения порядка уже были использованы при описании работы с упорядоченными списками в подразделах 1.4.4-1А.7.
Здесь вводятся точные определения, которые предполагаются известными в остальной части книги. 1.8.1. Определения Антисимметричное транзитивное отношение называется отношением порядка. Отношение порядка может быть рефлексивным, и тогда оно называется отношением нестрогого порядка. Отношение порядка может быть антирефлексивным, и тогда оно называется отношением строгого порядка. Отношение порядка может быть полным (линейным), и тогда оно называется отношением нолного, или линейного порядка.
Отношение порядка может не обладать свойством полноты (линейности), и тогда оно называется отношением частичного порядка. Обычно отношение строгого порядка (полного или частичного) обозначается знаком <, а отношение нестрогого порядка — знаком <. Отношение порядка в общем случае обозначается знаком -с. ЗАМЕЧАНИЕ Для строгого порядка свойство антнснмметрнчностн можно определить следующим обра. эом:т'а,ьа<Ь~ (Ь<а). Пример Отиошение < на множестве чисел является отношением строгого полного порядка, Отношение < на множестве чисел является отношением нестрогого полного порядка.
Отношение с на булеане 2м является отношением нестрогого частичного порядка. Множество, на котором определено отношение частичного порядка, называется частична унорядочеииым. Множество, на котором определено отношение полного порядка, называется вполне упора дочеииьин. Пример Множество чисел упорядочено линейно, а булеан упорядочен частично. 1.8.2. Минимальные элементы Элемент х множества М с отношением порядка ~ называется минимальным, если не существует меньших элементов: — Зу н М у -с х йгу Ф х. Пример Пустое множество ю является минимальным элементом булеана по включению.
46 Глава 1, Множества н отношения ТЕОРЕМА Во всяком конечном непустом частично упорядоченном множестве существует минимальный элемент. ДОКАЗАТЕЛЬСТВО От противного. Пусть - (Вх е М -Эу е М у -с х). Тогда ч х Е М 3 у Е М у -«х =» 3 (и ), ч'т и +1 .ч и ег ит«1 Ть и;. Поскольку 1М~ < оо, имеем Зт,,у т < т' эти; = и-.
Но по транзитнвности и; м иг+1 и >-иу =»и;+т >-иу =и;. Таким образом, из+1 -«и, ег иььг; и; =» и1+1 = и; — противоречие. ЗАМЕЧАНИЕ Вполне упорндоченное конечное множество содержит один минимальный элемент, а в произвольном конечном частично упорядоченном множестве нх может быть несколько. ТЕОРЕМА Всякий чаапичный порядок на конечном множестве может быть дополнен до линейного.
ДОКАЗАТЕЛЬСТВО См. следующий подраздел. ЗАМЕЧАНИЕ В данном случае слова «может быть дополнен» означают, что существует отношение полного порядка, которое является надмножеством заданного отношения частичного порядка. 1.8.3. Алгоритм топологической сортировки Рассмотрим алгоритм дополнения частичного порядка до линейного на конечном множестве. Алгоритм 1.7. Алгоритм топологической сортировки Вход: частично упорядоченное множество гт. Выход: вполне упорядоченное множество иг. т«1т11е У П а йо т: = М(ГГ) ( функция М возвращает минимальный элемент ) у1еи т ( такой элемент т существует по теореме предыдущего раздела ) У: = гг '1 (т) епй ч'Ь!1е 1.9. Замыкание отношений ЗАМЕЧАНИЕ Всякая процедурз, генерирующая объекты с помощью оператора у1е14 определяет линейный порядок иа множестве своих результатов.
Действительно, линейный порядок — это последовательность, в которой объекты генерируются во время работы процедуры. ОБОСНОВАНИЕ Существование функции М обеспечивается первой теоремой раздела 1,8,2, П ЗАМЕЧАНИЕ Если отношение порядка представлено матрицей, то функцию М можно реализовать, например, так — найти Э матрице отношения первую строку, содержащую только нули.
1.8.4. Монотонные функции Пусть А и  — упорядоченные множества и г: А -+ В. Тогда если аг < аз =» у(аг) < у(аз), то функция у называется монотонно . а если аг < аз =» Даг) < Г'(аз), то функция Г называется строго монотонной. Пример Функция мощности конечного множества й: 2м -» Я является монотонной. 1.9. Замыкание отношений Замыкание является весьма общим математическим понятием, рассмотрение конкретных вариантов которого начинается в этом разделе и продолжается в других главах книги.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
