Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 249
Текст из файла (страница 249)
Множество не может содержать один и тот же элемент дважды', кроме того, элементы множества не упорядочены. Два множества А и В равны (что записывается как А = В), если они содержат одни и те же элементы. Например, (1,г,з) = (з,г,1). Для часто встречающихся множеств используются специальные обозначения: 'Модификация множества, юторое может содержать несколью одинаювык элементов, называется мультимножеством (юц16аее).
Приложение Б. Множества и прочие художества 1203 ° 9 обозначает пустое множество, т.е. множество, не содержащее ни одного элемента; ° Х обозначает множество целых чисел, т.е. множество (..., — 2, — 1, О, 1, 2,... ); ° К обозначает множество действительных чисел; ° 'гч обозначает множество натуральных чисел, те.
множество (1, 2, 3,...)з. Если все элементы множества А содержатся во множестве В, т.е. из х е А вытекает х Е В, то мы записываем, что А С В и говорим, что множество А является подмножествам В. Множество А является истинным подмножеством (ргорег зпЬзе1) множества В (что записывается как АСВ), если А С В, но А ф В.
(Многие авторы используют обозначение А с В не только для истинных подмножеств, но и для отношения обычного подмножества.) Для любого множества А справедливо А С А; для двух множеств А и В А = В тогда и только тогда, когда А С В и В С А. Для любых трех множеств А, В и С из А С В и В С С следует А С С. Для любого множества А справедливо соотношение 9 С А, Иногда множество определяется посредством другого множества. Так, имея множество А, мы можем определить множество В С А, указав свойство, которым обладают элементы множества В.
Например, множество четных чисел можно определить следующим образом: (х: х б Е и х/2 — целое число). Двоеточие в такой записи читается как "такой что" (некоторые авторы вместо двоеточия используют вертикальную черту). Для данных двух множеств А и В можно определить новые множества при помощи следующих операций над множествамн. в Пересечением множеств А и В является множество АПВ = (х: хе Анхо В). ° Объединением множеств А и В является множество А 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): а, Ь е М и (а+ Ь) — четное число), то В будет отношением эквивалентности, поскольку а+ а четно (рефлексивность), если четно а + Ь, то четно и Ь + а (симметричность), и из четности а + Ь и Ь+ с вытекает четность а + с (транзнтивность).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
