Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 250
Текст из файла (страница 250)
Класс эквивалентности числа 4 есть [4] = (2, 4, 6,...), а класс эквивалентности числа 3 — [3] = (1, 3, 5,...). Основная теорема о классах эквивалентности заключается в следующем. Теорема Б.1 (Отношения эквивалентности тождественны разбиениям). Для любого отношения эквивалентности на множестве А классы эквивалентности образуют разбиение А, и обратно, любое разбиение А определяет отношение эквивалентности на А, для которого множества в разбиении являются классами эквивалентности. П Докаэательсшво. Для доказательства первого утверждения теоремы надо показать, что классы эквивалентности В непусты, попарно не пересекаются и их объединение дает множество А. Из рефлексивности В вытекает а Е [а], так что класс эквивалентности не является пустым; кроме того, поскольку каждый элемент а Е А является элементом класса эквивалентности [а], объединение всех классов эквивалентности равно А.
Остается показать, что классы эквивалентности попарно не пересекаются, т.е. что если два класса эквивалентности [а] и [6] имеют общий элемент с, то это один и тот же класс эквивалентности. В этом случае а В с и Ь В с, откуда в силу симметричности и транзитивности а В Ь. Таким образом, для произвольного элемента х е [а] имеем х В а и, как следствие, х В Ь, так что [а] С [Ь]. Аналогично, [Ь] С [а], так что [а] = [Ь]. Для доказательства второй части теоремы рассмотрим разбиение А А = (А;), и определим следующее отношение: В = ((а, Ь): существует такое (, что а е А, и Ь е А ) .
Покажем, что В есть отношение эквивалентности на А. Это отношение рефлексивно, т.е. из а е А; следует а В а. Симметричность В следует из того, что если Приложение Б. Множества и прочие художества 1209 а В 6, то и а, и 6 принадлежат одному и тому же множеству А;, так что 6 В а. Если а В Ь и Ь В с, то все три элемента принадлежат одному и тому же множеству, так что а В с, т.е. отношение В транзитивно. Чтобы показать, что множества в разбиении являются классами эквивалентности В, заметим, что если а е А;, то из хЕ 1а] вытекает х Е А,, а из х б А; вытекает х Е [а]. П Бинарное отношение В на множестве А является антисимметричньии, если из а В 6 и Ь В а следует а = 6. Например, антисимметричным на множестве натуральных чисел является отношение "<", поскольку если а < Ь и Ь < а, то а = Ь.
Отношение, являющееся одновременно рефлексивным, антисимметричным и транзитивным, является и отношением частичного порядка (рагба! оп1ег), а множество, на котором определено такое отношение, — частично упорядоченным множеством. Например, отношение "быть потомком" на множестве людей является отношением частичного порядка (если рассматривать человека как собственного потомка). В частично упорядоченном множестве А может не быть единственного "наибольшего" элемента а, такого что 6 В а для всех 6 е А. Вместо этого могут быть несколько макслмалъных элементов а, обладающих тем свойством, что не существует таких Ь Е А, отличных от а, что а В Ь. Например, в наборе ящиков разного размера может быть несколько максимальных ящиков, которые не могут поместиться ни в один другой ящик, так что одного "наибольшего'* ящика, в котором могут поместиться все остальные, не существуетз.
Отношение частичного порядка В является отношением полного (гога! огдег), или линейного (1шеаг огдег), порядка, если для всех а, МА имеем а В Ь или Ь В а, т.е. если любая пара элементов А может быть связана отношением В. Например, отношение "<" на множестве натуральных чисел является отношением линейного порядка, в то время как отношение "быть потомком" на множестве людей таковым не является, поскольку могут быть люди, которые не являются потомками друг друга. Упражнения Б.2-1.
Докажите, что отношение подмножества "С" на множестве всех подмно- жеств Х является отношением частичного, но не полного порядка. Б.2-2. Покажите, что для любого положительного ть отношение "тождественности по модулю и" является отношением эквивалентности на множестве целых чисел. (Мы говорим, что а ве Ь(шос(ть), если существует такое целое число д, что а — Ь = дп.) На сколько классов эквивалентности разбивает множество целых чисел это отношение? ьДля того чтобы отношение "может поместиться а*' было отношением частичного порядка, надо считать, что ящик может поместиться сам а себя. Часть Ч11!.
Приложения: математические основы 1210 Б.2-3. Приведите пример отношения, которое а) рефлексивно и симметрично,но не транзитивно; б) рефлексивно н транзитивно, но не симметрично; в) симметрично и транзитивно, но не рефлексивно. Б.2-4. Пусть Я вЂ” конечное множество, а  — отношение эквивалентности на Я х Я. Покажите, что если  — антисимметрично, то все классы эквивалентности содержат по одному элементу. Б.2-5. Профессор полагает, что всякое симметричное и транзитивное отношение В должно быль рефлексивным. Он предлагает следующее доказательство: из а Н 6 в силу симметрии следует 6 В а, а применение транзитивности к этому выводу дает а В а.
Прав ли профессор Б.З Функции Для данных двух множеств А и В функция )' представляет собой бинарное отношение на А х В, такое что для каждого а е А существует ровно одно 6 Е В, такое что (а, 6) Е г". Множество А называется областью определения (с1ошша) функции г", а множество  — областью значений (собоша1л). Иногда для функция используется запись ~: А - В; кроме того, если (а,Ь) е ~, то мы записываем 6 = ( (а), поскольку значение 6 однозначно определяется по значению а. Интуитивно функцию ~ можно рассматривать как операцию, которая ставит в соответствие каждому элементу А элемент В. Никакому элементу А не может быть поставлено в соответствие два различных элемента В, однако один и тот же элемент В может соответствовать разным элементам А.
Например, бинарное отношение ~ = ((а, Ь): а, Ь Е Х и Ь = а шос1 2) является функцией г": Х вЂ” + (О, Ц, поскольку для каждого натурального числа а имеется ровно одно число Ь из (О, 1), такое что Ь = а шос1 2. Например, 0 = З" (0), 1 = У (1), 0 = У (2) и т.д. Бинарное же отношение д = ((а,,Ь): а, Ь Е Х и а + Ь вЂ” четно) функцией не является, поскольку и (1, 3), и (1, 5) являются элементами д, так что элементу а = 1 соответствуют более одного элемента Ь, такого что (а, Ь) Е д.
Если у нас имеется функция Г": А - В, и 6 = 1'(а), то а называется арументом функции ), а Ь вЂ” значением функции ~ от данного аргумента а. Можно определить функцию, указывая ее значения для каждого элемента из области определения. Например, можно определить Г (и) = 2п для п Е 1Ч, что означает У = ((п,2п): п Е )ч'). Две функции )' и д называются равными, если у них 1211 Приложение Б.
Множества и прочие художества одинаковые области определения и значений и если для любого а из области определения / (а) = д (а). Конечная последовательность длины и представляет собой функцию /, область определения которой — множество из и целых чисел (0,1,...,и — Ц. Зачастую конечная последовательность записывается как список ее значений: (У (О), У (1),..., /(и — 1)). Бесконечной носледовательностью называется функция, область определения которой — целые неотрицательные числа. Например, последовательность чисел Фибоначчи, определенная рекуррентным соотношением (3.21), представляет собой бесконечную последовательность (О, 1, 1,2, 3, 5,8,13,21,...). Если область определения функции / является декартовым произведением, дополнительные скобки вокруг аргументов в записи обычно опускаются. Например, если у нас есть функция /: Аз х Аз х х А„- В, то мы можем записать Ь = /(аз,аз,..., а„), а не Ь = /((аз, аз,...,а„)).
Кроме того, в этом случае аргументом называется каждый элемент а;, хотя технически единым аргументом функции / является кортеж из и элементов (аз, аз,..., а ). Если Ь = / (а) для некоторой функции /: А — В, то иногда говорят, что Ь есть образ (ппайе) а. Образ подмножества А' С А определяется как / (А') = (Ь б В: Ь = У (а) для некоторого а Е А') . Множество значений (гапйе) функции / представляет собой образ ее области определения, т.е.
/(А). Например, множеством значений функции /: Х вЂ” + М, определенной как / (и) = 2п, является У (Х) = (гп: гп = 2п для некоторого и Е М) . Функция называется наложением или сюръекцией (звг1ес11оп), если ее множество значений совпадает с областью значений. Например, функция У (и) = 1п/2) представляет собой наложение множества неотрицательных целых чисел на множество неотрицательных целых чисел, так как каждый элемент этого множества служит значением / для некоторого аргумента. Функция же / (и) = 2п не является наложением Ь1 на Х, поскольку, например, число 3 не является значением / ни для какого аргумента; однако эта функция является наложением Х на множество четных натуральных чисел.
Сюръекцию /: А — В иногда называют отоброэкением А на В. Функция /: А -+ В называется вложением или иньекцией (1п1есиоп), если различным аргументам / соответствуют различные значения, т.е. из а ~ а' вытекает / (а) ф / (а'). Например, функция / (и) = 2п является вложением множества Х в Х, так как каждое четное число Ь является отображением не более одного элемента из области определения, а именно Ь/2. Функция / (и) = 1п/21' вложением не является, поскольку значение 1, например, получается для двух 1212 Часть ЧШ. Приложения: математические основы аргументов — 2 и 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
