Кук Д., Бейз Г. - Компьютерная математика, страница 8

Чтобы быть более конкретными, давайте в дальнейшем предполагать, что язык имеет три осповпые управляющие структуры и четыре метода доступа и более у него пет никаких особых свойств. Мы могли бы в качестве примера ваять семь программ, каждая яа которы~ включает только одну характеристику языка (хотя, вообще говоря, каждая программа моягет использовать более чем одну характеристику языка). Нсследование этих програм тогда могло бы покрыть большую часть свойств языка. Математически это моягно определить следующим образом. О п р е д е л е н и е.

Пусть Л вЂ” пепустое множество и (Л,) — совокупность подмножеств (1=1, ..., я, выр*) таках, что Совокупность этих подмножеств называется нокры- тиелс А. г' Пример 4Л. (А, В) — покрытие А 0 В, (А, А 0 В, В, С) — покрытие А сс В 0 С. с>' Используя понятие покрытия, можно обеспечить, что- бы ни одно из свойств пе было пропущено, так как каж- дый элемент включен по крайней мере в одно из под- множеств покрытия.

Однако в общем случае могут встречаться случаи дублировааая. Коли в дальнейшем потребовать, чтобы элементы покрытия попарно не пе- ресекались, то дублирования не будет. Отсюда возникает понятие разбиения. О п р е д е л е и а е. Разбиениелс непустого множества А называется совокупность подмноа;еств Р(А ) таких, что объединение всех элементов .Ус(А) совпадает с А и все элементы о.(А) взаимно не пересекаются, т. е. А разбито таким обрааом, что каждый элемент А содер- асится только в одном подмножестве разбиения.

Х П р и м е р 4.2. (А, А') — разбиение Ю, (А й В, А й В', А' й В, А' й В') — разбиение Ю, (А> В, А й В, В~А) — разбиение А 0 В. У Разбиение определяется однозначно, и части разбиения андуцируют особый род отношения, называемого отношением эквивалентности. Эти отношения ведут себя подобно отношению ч=» между числами или множествами. Выделяя основные свойства равенства, мы приходим к следующему определению. Определение. Бинарное отношение на множестве называют отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. сс Пример 4.3.

На маожестве всех треугольников отношение, определяемое как ((х, р)> х и у имеют одинаковую площадь), является тривиальным отношением эквивалентности. Более интересно следующее отношение, определенное на множестве всех программ: ((а, Ь): а и Ь вычисляют одну и ту же функцию на определенной машине).

Это отношение являетсн отношением эквивалентности. У Напомним, что мы рассматриваем более простые способы создания больших множеств, разбивая их на мел- 47 кие части, чем если бы в качестве этих частей брали элементы множества. В настоящий момент у нас уже имеется математический аппарат, однако недостает подходящих простых обозначений. Сейчас это будет сделано, после чего приведем несколько известных примеров.

Определение. Пусть р — отношение эквивалентности на мвол>естзе А. Определим класс эквивалентности [х) для х 1и А: [х] (у: хру). Таким образом, [х[ есть множество всех элементов А, которые р-эквивалентны х. В случаях, когда рассматривается только одно отношение эквивалентности, мы можем также использовать обозначение ч» (эквивалентно), поатому [х) - (у: у) В отдельных специальных случаях для обозначения эквивалентности иногда используют символ з-». Теперь вместо проверки всего множества мы можем любым способом выбрать представителей (по одному от каждого из классов эквивалентности), что упрощает вычисления. Следующий пример иллюстрирует вышесказанное.

Пример 4.4. Пусть в — фиксированный элемент Х; "чеделим отношение р, на Х: р, ((х, у): х — у . иа, где п ю Ю, Рассмотрим случай з 10. Тогда [1) (11, 21, -9, 10 976 631...,), [1066[ (66, 226, -24... ) и т. д. В действительности существуют только десять различяых классов эквивалентности. Целые О, 1, 2, 3. 4, 5, 6, 7, 8, 9 принадлел1ат различным классам. Поэтому мы мок>ем использовать их в качестве представителей этих классов. >т В вычислениях отпошевия эквивалентности представляют особый интерес, поскольку они ассоциируются с различными алгоритмами, дающими один и тот же результат, или приводящими к одной и той же обработке данных, нли же представляющими одну и ту же информацию о различных зквввааеытных структурах данных. Примером таких очевидных ситуаций является борьба с трудностями, которые возникают при исследовании раз- зз решимости.

Такие факторы, однако, не вызывают проблем, если множества образуются путем хорошо сконструированных процессов с конечной базой. И все же типичным нвляется случай, когда при описании даже зхорошего поведенняэ требуется большое число деталей, в связи с чем онп доля<вы быть здесь рассмотрены. Несмотря на зто, мы будем возвращаться к подобным вопросамв 3 бивгл.8и9. По-видимому, наиболее известное отношение эквивалентности знакомо читателю, хотя он мог и не знать, что оно — отношение эквивалентности. Это отношение связано с дробями. Рассмотрим множество ЕХЫ.

Пару (а, Ь) мы можем рассматривать как дробь а/Ь. Эти два способа обозначения элементов ЕХЫ являются различными, но они «изоморфны». Мы будем их рассматривать далее в $1 гл. 5. Отметим, что можно переходить от одной формы обозначения к другой. До сих пор все было хорошо, однако существуют различные злементы в Е Х Р), которые желательно рассматривать как одни и те же, хотя записываются они по- равному.

Чтобы преодолеть зту трудность, определим отношение эквивалентности на ЕХг( следующим образом: (а, Ь)~(с, б) тогда и только тогда, когда а ° б Ь»с. Множество всех классов эквивалентности, определяемых этим отношением на Е Х Р), называют рациональными числами и обозначают символом О. Обычно выбирают тех представителей классов, у которых самые малые а и Ь. Следует упомянуть, что предполагается существование действительных чисел (множество действительных чисел обычно обозначают через К).

Эти числа можно представить в форме ... О И ... Ыз Ы1 бз 61 бз ... б где каждое А и б, принадлежат множеству (О, 1, 2, 3, 4, 5, 6, 7, 8, 9) = Е|з, д„чь О, исключая случай я О. В частности, допускается бесконечная непериодическая десятичная дробь, хотя нули перед д„ обычно опускают. (Отрицательные числа представляют ненулевыми положительными числами со знаком минус.) Заметим, что индекс отношения эквивалентности р на множестве А — зто количество частей А, иидуцируемых р (число р-эквивалентных классов).

4 д. квь г, веаз 49 Упражнение 2А. Доказать, что любое отношение эквивалентности порождает такое разбиение, что для любых х, у ш А или (х) (у), или (я) П [у) = И. 2. Пусть А — конечное множество. Какие отношения эквивалентности дают наибольшее и наименьшее число эквивалентных классов7 3. Если (А» Аи ..., А„) — разбиение А и А конечное, показать, что а !А~ ~ 1А1)„ 5 5. Отношения порядка Поскольку иэ понятия равенства (скажем, между числами) возникает математическое понятие эквивалентности, некоторые неравенства могут также использовать ся как модели для болев широкого класса отношений.

Частичным порядком на множестве А назовем отношение, которое рефлексивно, антисимметрично и транзитивно. Порядок (называемый также отношением лорядка) — ато обобщение отношения < на Ь). Поэтому можно легко проверить требуемые три свойства. Заметим, что мы могли бы в качестве определения взять отношение <. Тогда отношение порядка было бы только транаитивно. Поэтому свойство транзитивности является наиболее важным для отношения порядка. Определив отношение <, можно определить отношение < следующим образом: а < Ь с=ь а < Ь и а чь Ь. Аналогично, если задано <, то а < Ь с*ь а Ь или а < Ь.

Пример 5Л. Пусть аадано проиавольное множество А. Тогда отношение ж на У'(А) есть тривиальное отношение порядка. (Хя'Х для всех Х; если Хшр и у.-Х, Х-у;Хжуя у=2 Х г) г Отношение порядка р па А нааывается полным, если для любых х, р а А или яру, или ррх (илп же выполняются оба). Пример 5.2.

Очевидно, что порндок на подмножествах данного множества не является полным. Естественный порядок чисел на действительной оси Е является полным. По мере достижения прогресса в изучении математики становится ясным, что математика не набор раэроанеияых идей, а совокупность связанных между собой концептуальных понятий, которые используются во многих непохонсих друг па друга ситуациях, Отсюда следует, что, если основной принцип установлен и исследован, он фактически единым обраэом решает проблемы для всех этих различных случаев, Следующий пример нвляется простой иллюстрацией этой идеи. Пример 5.3.

На основе порядка, определенного яа Х, мы можем формально получить обычные отношения порядка на множествах чисел Е, (( и К. (Как уже упоминалось, исследование Х будет проведено в т 3 гл. 3.)' Вначале рассмотрим Е. Чтобы облегчить рассуждения, раэобьем Е следующим образом: Е г(0(0) ОА. Поэтому А ( — л: яш50. Определим отношение (которое будем называть полным отношением порядка) на Е рассмотрением всевоэможных элементов л и у ив разбиения (Х 0 (0) ОА). Есля х ° у, то х< р и у*=я.

Пусть ячьу. Тогда; а) если х, у ш Х, то порядок в Е тот же самый, что и вМ; б) если х, ршА, то я < у тогда и только тогда, когда -р»Я -л в М (т. е. -5 < — 4, так как 4 < 5); в) если я 0 и уыХ, то я<у; г) если хшА и у О, тол~у; д) если яшА и рш М, то я < у или в противном случае р < я. На основе порядка на Е и обычных арифметических операций с целыми числами мы можем определить порядок на ((: а/5 < сЯ тогда н только тогда, когда а » Ы< Ь е с.