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

Пусть о ((х, у): х~у). Может ли о' быть описано тем же способом, что и р' в 2.1, 3) Ответ проверьте. 5. На улице есть 30 домов, пронумерованных обычным способом: нечетные номера с одной стороны, а четные с другой. Пусть Ь, обозначает я»ителя, н.изущего в доме с номером п. Описать пра помощи символов отношение Ж на множестве жителей такое, что й, находится в отношении Й к йе если они являются соседями.

Как будет выглядеть )»', если улица является тупиком) 6. Вернемся к мноя»еству Я клеток шахматной доски. Отношение К связывает клетки, которые определяютгя ходом копя (т. е. если копь может перейти с х на у за один шаг). Определить К при помощи символов. зв 7. Пусть С вЂ” отношение на Я такое, что хСу тогда и только тогда, когда х есть начальная позиция (белой) пешки, а у есть клетка, где первый ход игры заканчивается, Описать С, м)(С) и Ж(С). й 2.

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

Хотя этим методом и можно воспользоваться, особенно при описании некоторых больших множеств чисел, существуют методы, которые более эффективны в общих ситуациях (включасощих, в частности, бинарные отношения на небольших множествах). В этом параграфе мы кратко рассмотрим некоторые из них. Для описания этих методов используем множество Х (а,д,с,сс) и отношения 1х, Уз и В, где В ((а, Ь), (а, с), (Ь, с(), (с, е), (е, Ь)). Вначале рассмотрим метод, относящийся к традиционной аналитической геометрии. Начертим пару взаимно перпендикулярных осей (ОХ вЂ” горизонтальная ось, а ОУ вЂ” вертикальная ось) и на каждой отметим точки, представляющие элементы множества Х (рпс.

2.2, а). Теперь в правом верхнем координатном углу отметим точки с координатами (х, у), у которых х ш Х и у ш У. Мпоясестза, соответствующие 1,„0 и Л, изображены на ряс. 2.2, Ъ, с и с(. Основной недостаток этого метода заключается в том, что при увеличении ! Х! трудно увидеть элементы в области и установить соответствие с точками, обозначающими отношения. Чтобы преодолеть этот недостаток, можно опустить точки и соединить стрелкой хшй и ушЯ, когда (х, у) принадлежит отношению (рис.

2.3), Диаграмма, представляющая Уз, получалась довольно запутанной, но это естественно, поскольку число элементов в 40 0з увеличилось. С другой стороны, отношения Ух и Н представлены наглядно, и легко увидеть их области определения и значений. Диаграмма для Уз наиболее неудобна в месте пересечения осей. Теперь, когда не используются координаты в областях определения и значений для а Ь е и' е а е Ь е а в Ь а Ь Е а Е Рис.

2.2 расстановки злементов, отношенвя (как в первом методе) можно начертить параллельными. Позтому, используя параллельные вертикальные линии и двигаясь слева направо (линия слева является областью определения), мы получаем диаграмму, изображенную на рис. 2.4. Здесь стрелки не требуются, так как мы знаем, что отношения идут от области определения к области значений. Это приводит к двум возможностям: мы можем или заменить стрелки прямыми линиями, или заменить две линии, изображающие области определения и значений, простой совокупностью точек. (Например, точка е в об- 41 ласти определения является той же самой, что и точка, представляющая с в области значений.) Это показано на диаграмме, изображенной на ркс. 2,5.

Итак, обозначены наиболее важные методы графического изображения бинарных отношений. Они будут ис- Я Гь~ С ~9 гг Ь и, Рвс. 2.5 пользоваться в оставшейся части книги. Обсуждение графических методов, связанных с соотношениями, мы продолжим В гл. 7. У п р а ж н е н и е 2.2. 1. Начертить диаграмму, представляющую отношение р из упражнения 2.1, 1. 2. Начертить диаграмму, ь.едставляющую отношение )ч' (см. упражнение 2.1, 5) яа улице, имеющей десять домов. Как изменится диаграмма, если улица является тупикомг й 3. Свойства отношений Очевидно, что общие отношения, будучи только подмножествами произведения множеств, пе особенно интересны, поскольку о них можно сказать очень мало.

Одпако, когда отношения удовлетворяют некоторым дополнительным условиям, относительно них можно сделать более содержательные утвернщеиия. В этом параграфе мы рассмотрим некоторые из основных свойств, которыми могут быть наделены отношения, Говорят, что свойство имеет место, если только выполнено соответствующее условие. Определение. Пусть р — отношение на множестве А. Тогда: а) р реЯлсксиено, если хрх для любого хчвА; б) р симметрично, если хру влечет урх; в) р траизитисно, если хру и ург влечет хрг; г) р антисимметрично, если хру и урх влекут х - у. 43 Терминология, введенная здесь, вероятно, является новой для читателя, однако он, по-видимому, знаком с зтнмн понятиями.

Поясним нх на следующих примерах. Пример ЗА. Пусть р = ((х, у): х, у ж г( и х — делитель у), о=((х, у): х, ужй( их<у), т = ((х, у): х, уж Х~(1) и х и у имеют общий делитель>. Тогда р: а) рефлексивно, так как х/х 1 для всех хжг(; б) несимметрично, поскольку 2 — делитель 4, но 4 не является делителем 2; в) транзнтивно, так как если у/хжг( и х/ужг(, то х/х — (у/х) + (х/у) ж г(; г) антиснмметрично, так как если х/у ж г( н у/х юг(, то х у. Лналогично с: а) рефлексивно, так как х < х для всех х <а р(; б) несвмметрнчно, так как 2 < З,по 3 ьа 2; в) трапзнтввпо; г) антиспмметричпо, так как если х < у и у < х, то х у. Наконец, т рефлексивно и симметрично, но не трап- зитнвяо или апткснмметрично.

р Пример 3.2, Пусть Р— множество всех людей, а А и Я определяются следующим образом: А ((х, у): х, у ж Р и х — предок у), Я ((х, у)ю Р н х и у имеют одних и тех же родителей). Очевидно, что А транзвтквпо, а Я рефлексивно, симме- трично и транзитивно.

р Заметим, что свойства симметричности и антнсимме- трнчпостн не являются взаимоисключающими. Для лю- бого множества Х отношение 1х являетая симметричным и антнсимметричпым. (Проверьте() Мы можем также иметь отношения, которые не являются ни симметрич- ными, ни антисвмметричными. Пример 3.3. Пусть опять Р вать множество всех людей. Определим отношение В такое, что хВу тогда н только тогда, когда х является братом у. В семье, состоя- щей из двух братьев р и й и сестры г, мы имеем ситуа- цию, нзобраягевную на рис.

2.6. Отношоние В не сим- метрично, так как рВг, но не гВр. Зто отношение также 44 не является антисимметричным, так как рВд и оВр, хотя р и о различны. В более общей ситуации мы мол<е>< интерпретировать рассмотренные выше характеристики отношения путем построения диаграммы: а) отношение рефлексивно а * ~, ~ а ме существует стрелка, которая начинаетсн и заканчивается на етом узле~ > б) отношение симметрично то- Рис.

26 гда и только тогда, когда длн каждой стрелки, соединяющей два узла, существует также стрелка, соединяющая зти уалы в обратном направлении; в) отношение транзитивно тогда и только тогда, когда для каждой пары узлов л и р, связанных последовательностью стрелок от х к а<, от а> к а>, ..., от а„ < к а„, от а„к р, существует также стрелка от х к у; г) отношение антисимметрично тогда и только тогда, когда не существует двух различных узлов, связанных парой стрелок. Существует много других свойств отношений, которые можно было бы рассмотреть.

Однако рассмотренные выше свойства являются наиболее важными и будут часто использоваться в дальнейшем. У и р а ж н е н и е 2.3. 1. Являются ли следующие отношения рефлексивными, симметричными, транзитивпыми или анситимметричными: а) отношение на (1, 2, 3, 4, 5) определяется как ((а, Ь): а — Ь четное); б) отношение на (1, 2, 3, 4, 5) определяется как ((а, Ь): а+ Ь четное); в) отношение на Р (множестве всех людей) определяется как ((а, Ь): а и Ь имеют общего предка)< 2. Следующее утверждение ошибочно.

Симметричное и транзитивное отношение на Я является также рефлек- сивным, так как аЛЬ и ЬВа влекут аЛа. Внимательно е5 изучив определения, найти ошибку. Построить отноше- ние на (1, 2, 3), которое является симметричным и трап- зитивным, по не рефлексивным. 3. Пусть р — отношение между А и В, а жА. Тогда р(а) определено как мнол~ество (Ь: арй) и является под- множеством В, Пусть на (-4, -3, — 2, — 1, О, 1, 2, 3, 4) определены следующие отношения: р ((а, Ь): а<Ы, и ((а, Ь): Ь вЂ” 1(а(Ь+2), т ((а, Ь): а'< Ы. Какие это множества: а) р(0); б) а(0); в) т(0); .) р(1) д) о(-1');е) ( — '1)г $ 4. Разбневия и отношения эквивалентности Во многих вычислительных задачах берутся большие мнокестеа и разбиваются таким образом, чтобы все интересующие вас ситуации можно было исследовать на нескольких правильно выбранных примерах.

Например, одвв из путей получения качественной оценки характеристик языка программирования — это посмотреть конкретные программы, написанные на этом языке. Однако каждый интересный язык, включая такие языки высокого уровня, как Паскаль и Фортран, порождает бесконечно много программ, и, следовательно, мы должны выбирать программы так, чтобы опн правильно отражали достоинства я недостатки языка.