Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 270
Текст из файла (страница 270)
хА, мощность которого равна )А"( = )А!", если А конечно. Можно также рассматривать кортеж из п элементов как конечную последовательность длиной и (см. с. 1219). Упражнении Б.1.1 Изобразите диаграмму Венна, которая иллюстрирует первое из свойств дистрибутивн ости (Б. 1). /з!5 Прнложенне и Множество н нрочне художество Б.1.2 Докажите обобщение законов де Моргана для любого конечного набора мно- жеств: Аг Г1 Аз Г1 и Ан — — Аг г5 Аз г5 г5 Ао Аг г5 Аз 0 ' г5 Ао = Аг Г1 Аз и ' ' Г1Ао Б.1.3 * Докажите обобщение равенства (Б.З), именуемое принципом включений и исключений (рппсгр1е о1 (пс!пзюп апб ехс!пз)оп): )Аг Г5 Аз Г5 -. Г5 А„( = 1Аг( + 1Аз) + . + )А„) — !Аг П Аг~ — 1Аг Г1 Аз~ — .
+ 1Аг П Аз Г1 Аз! + .. (все пары) (все тройки) +( — 1)" г 1Аг Г1АзГ1- Г1А„~ Б.1.4 Покажите, что множество нечетных натуральных чисел счетно. Б.1.5 Покажите, что для любою конечного множества Я степенное множество 2Б со- держит 2~Б~ элементов (те. имеется 21Б~ различных подмножеств множества Я). Б.1.о Дайте индуктивное определение кортежа из п элементов, используя понятие упо- рядоченной пары. Б.2. Отношения аВа.
Бинарным огпноквениеи (Ь1пагу ге1абоп) В между элементами двух множеств, А и В, называется подмножество декартова произведения А х В. Если (а, Ь) е В, это можно записать как а В Ь. Когда мы говорим, что В есть бинарное отношение на множестве А, имеется в виду, что В является подмножеством А х А. Например, отношение "меньше" на множестве натуральных чисел представляет собой множество ((а, Ь): а, Ь Е г) и а < Ь). Под и-арным отношением на множествах Аг, Аз,...,А„понимается подмножество декартова произведения АгхАзх хА„.
Бинарное отношение В ~ А х А являегся рефлексивным, если для всех а е А справедливо Части НП. Праеоисеиии: математические осиоаы Например, отношения "=" и "<" на множестве Н рефлексивны, но отношение "<" таковым не является. Отношение В симметрично, если из аВЬ следует ЬВа для всех а, 6 б А. Например, симметричным является отношение "=", но не "<" или "<".
Отношение В тренэитиено, если из аВЬ и ЬВс следует аВс для всех а,Ь, с е А. Например, транзитивнымн являются отношения "="„"<" и "<", но отношение В = 1(а,Ь): а,Ь Е )ч и а = 6 — 1) таковым не является, поскольку из 3 В 4 и 4 В 5 не следует 3 В 5. Отношение, которое является одновременно рефлексивным, симметричным и транзитивным, называется отноиеением эквивалентности. Например, на множестве натуральных чисел отношение "=" является отношением эквивалентности, а отношение "<" — нет. Если  — отношение эквивалентности на множестве А, то можно определить клесс экеиеелентности элемента а е А как множество [а] = (6 е А; а В 6), т.е.
множество всех элементов, эквивалентных а. Например, определим отношение В = 1(а, 6): а, 6 Е 1з и а + Ь является четным числом). В таком случае В является отношением эквивалентности, поскольку а+ а четно (рефлексивность), если четно а + 6, то четно и Ь + а (симметричность), и из четности а + Ь и Ь+ с вытекает четность а + с (транзитивность). Класс эквивалентности числа 4 представляет собой [4) = 10, 2,4,6,...), а класс эквивалентности числа 3 имеет вид [3] = 11, 3,5, 7,...).
Основная теорема о классах эквивалентности заключается в следующем. Теорема Б.1 10тношения экеиеелентности тождественны разбиениям) Для любого отношения эквивалентности В на множестве А классы эквивалентности образуют разбиение А; и обратно: любое разбиение А определяет отношение эквивалентности на А, для которого множества в разбиении являются классами эквивалентности. Доказательство.
Для доказательства первого утверждения теоремы необходимо показать, что классы эквивалентности В непусты, попарно не пересекаются, и их объединение дает множество А. Из рефлексивности В вытекает а б [а], так что класс эквивалентности не является пустым; кроме того, поскольку каждый элемент а е А принадлежит классу эквивалентности [а], объединение всех классов эквивалентности равно А. Остается показать, что классы эквивалентности попарно не пересекаются, т.е. что если два класса эквивалентности, [а] и [6], имеют общий элемент с, то это в действительности один и тот же класс эквивалентности.
Предположим, что а В с и Ь В с. В силу симметричности с В Ь„а в силу транзитивности а В 6. Таким образом, для произвольного элемента х Е [а] имеем х В а и, в силу транзитивности, х В Ь, так что [а] С [6]. Аналогично [Ь) С [а], так что [а] = [Ь). 12! 7 Лрмяожсенне д Множесшеп н прочие худпджесшеп Для доказательства второй части теоремы рассмотрим разбиение А = (А,) множества А н определим отношение В = ((а,Ь): существует т, такое, что а е А, и 6 б А;) Покажем, что В есть отношение эквивалентности на А. Это отношение рефлексивно, так как из а е А; вытекает а В а.
Симметричность В следует из того, что если а В 6, то и а, и 6 принадлежат одному и тому же множеству А„так что 6 В а. Если а В 6 н Ь В с, то все три элемента принадлежат одному и тому же мноукеству Ап так что а В с, т.е. отношение В транзитивно. Чтобы показать, что множества в разбиении являются классами эквивалентности В, заметим, что если а ~ А„то из х ~ [а] вытекает х ~ Ап а из х ~ А, вьпекает х ~ [а]. ° Бинарное отношение В на множестве А является антисимметрнчным, если нз аВЬ н ЬВа следует а=Ь.
Например, антисимметрнчным на множестве натуральных чисел является отношение "<", поскольку если а < 6 и Ь < а, то а = 6. Отношение, яапяюшееся одновременно рефлексивным, антисимметричным и транзитивным, является и отношением частичного норядка (рагйа! оп(ег), а множество, на котором определено такое отношение, — частично унорядоченньии множеством.
Например, отношение "быть потомком" на множестве людей является отношением частичного порядка (если рассматривать человека как собственного потомка). В частично упорядоченном множестве А может не быть единственного "наибольшего" элемента а, тажуго, что 6 В а для всех 6 е А. Вместо этого может быть несколько максимальных элементов а, обладающих тем свойством, что не существует таких Ь е А, отличных от а, что а В 6. Например, в наборе ящиков разного размера может быть несколько максимальных ящиков, которые не могут поместиться ни в один другой ящик, так что одного "наибольшего" ящика, в котором могут поместиться все остальные, не сушествуетз.
Отношение В является отношением ночного норядка (го!а1 огдег), если для всех а, Ь е А имеем а В 6 или Ь В а (или и то, и другое одновременно), т.е. если любая пара элементов А связана отношением В. Например, отношение "<" на множестве натуральных чисел является отношением полного порядка, в то время как отношение "быть потомком" на множестве людей таковым не является, поскольку могут быть люди, которые не являются потомками друг друга. Отношение полного порядка, которое является транзнтивным, но не обязательно рефлексивным и антисимметричным, называется полным нрямым норядком (гога! ргеоп)ег).
елля тото чтобы опшшение "может поместиться е" было отношением чястичното порядка, нужно считять, что ящик может поместиться сом я себя. 39 зьк этее 12!8 Часть ЕШ. Прилажеииее матеиотичесиие осиоеы Упражнении Б.2.1 Докажите, что отношение подмножества "С" на множестве всех подмножеств У является отношением частичного, но не полного порядка. Б.2.2 Покажите, что для любого положительного п отношение "тождественности по модулю и" является отношением эквивалентности на множестве целых чисел. (Мы говорим, что а = 6 (пюб и), если существует такое целое число с, что а — 6 = сп.) На сколько классов эквивалентности разбивает множество целых чисел это отношение? Б.2.3 Приведите пример отношений, которые и. рефлексивны и симметричны, но не транзитивны; б.
рефлексивны и транзитивны, но не симметричны; ж симметричны и транзитивны, но не рефлексивны. Б.2.4 Пусть Я представляет собой конечное множество, а В является отношением эквивалентности на Я х Я. Покажите, что если отношение Н антисимметрично, то все классы эквивалентности Я по отношению к В содержат по одному элементу. Б.2.5 Профессор полагает, что всякое симметричное и транзитивное отношение В должно быть рефлексивным. Он предлагает следующее доказательство; из а Л 6 в силу симметрии следует Ь В а, а применение транзитивности к этому выводу дает а В а. Прав ли профессор? Б.З. Функции Для данных двух множеств, А и В, функция 1 представляет собой бинарное отношение на А и В, такое, что для всех а е А существует ровно одно 6 е В, такое, что (а, 6) Е 1.
Множество А называется обласлеью определения (боша|п) функции 1, а множество  — областью змаченвй (сос(оша(п). Иногда для функции используется запись 1: А — + В; кроме того, если (а, 6) б 2', то мы записываем 6 = 1(а)„поскольку значение 6 однозначно определяется значением а. Интуитивно функцию 1 можно рассматривать как операцию, которая ставит в соответствие каждому элементу А элемент В. Никакому элементу А не может быть поставлено в соответствие два различных элемента В, однако один и тот же элемент В может соответствовать разным элементам А.
Например, бинарное Проложение д Множества и ираиие «удажестеа отношение 1 = ((а, Ь): а, Ь Е И н Ь = а шос1 2) является функцией г': И вЂ” ~ (О, 1), поскольку для каждого натурального числа а имеется ровно одно число Ь из (О, 1), такое, что Ь = а шос) 2. Например, 0 = ДО), 1 = Г" (1), 0 = Д2) и т.д. Бинарное же отношение д = ((а, Ь): а, Ь Е И и а+ Ь четно) функцией не является, поскольку и (1,3), и (1, 5) являются элементами д, так что элементу а = 1 соответствует более одного элемента 6, такого, что (а, 6) Е д.
Если имеется функция г': А + В и если 6 = г'(а), то а называется аргументом функции 1, а 6 — значением функции Г" от данного аргумента а. Можно определить функцию, указывая ее значения для каждого элемента из области определения. Например, можно определить 1(п) = 2п для п е И, что означает 1 = ((п, 2п): п Е И). Две функции, У н д, называются равнымн, если у них одинаковые области определения и значений и если для любого а из области определения Да) = д(а). Конечная последовательность длиной п представляет собой функцию 1, область определения которой — множество из и целых чисел (0,1,..., п — 1).
Зачастую конечная последовательность записывается как список ее значений: (г'(О), Д1),..., Дп — 1)). Бесконечной последовательностью называется функция, область определения которой — множество натуральных чисел И. Например, последовательность чисел Фибоначчи, определенная рекуррентным соотношением (3.22), представляет собой бесконечную последовательность (О, 1, 1, 2, 3, 5, 8, 13,21,...). Если область определения функции )' является декартовым произведением, дополнительные скобки вокруг аргументов в записи обычно опускаются. Например, если есть функция з": А1 х Аз х .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
