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