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

Произведении множеств Пока мы в основном занимались построением из существующих множеств множеств меньшего размера. Сейчас будет рассмотрен один из наиболее общих способов конструирования больших множеств. Рассмотрнм для иллюстрации множество размеченных клеток шахматной доски (рис. $ЛО). Рассмотрим мнояеество столбцов, которые обозначим буквами а, Ь, ..., Ь (слева направо), и (Черные) а Ь о ее' е и у Ь (белые) Рве. 1ЛО множество строк от г до 8 (снизу вверх). Следовательно, как~два клетка может быть однозначно задана двумя символами: один — из множества г" (а, Ь, ..., Ы, другой— нз множества К (1, 2, ..., 8), например а$, )7, еЗит.д.

Таким образом, из множества столбцов )г и множества строк В мы образовали множество всех клеток доски. Этот пример содержит в себе новые идеи, которые используются при построении произведений множеств. Однако для того, чтобы быть в состоянии обобщить рассматриваемую ситуацию, следует быть немного болев точными. 3 д. кгн, г. веае 33 О и р е д е л о н и е. Обозначим последовательность из и элементов хн хз, ..., х через (хь хз, ..., х„).

Здесь круглые скобки испол'зуются для того, чтобы указать на порядок, в котором з. зясаяы элементы. Например, если х~ чьхе, то последовательность (хз, хи ..., х„) не совпадает с исходной. Будем называть такую последовательность набором длины и; набор длины 2 будем называть парой. Пусть даны и множеств Аь Лз, ..., А„; множество всех наборов (хь хз, ..., х„) таких, что х~ юЛи ..., х ш ш А, называют прямым произведением Аь ..., А„и обозначают А1ХЛзХ...ХА . Используя другие обозначения, это произведение запишем более кратко: Ц Аь // Пример 5.1. Пусть Х=(0, 1), У-(х, у), Е= (О, 1, 2). Тогда ХХ У ((О,х), (О,р), (<,х), (1,р)), УХ Х=((х, 0), (х, 1), (р, 0), (р, 1)).

Таким образом, Х Х У Ф У Х Х. При рассмотрении снова примера с шахматной доской становится ясно, чтб будет, если написать выражение Зе. Множества г" и Л пе пересекаготся и (е, 8)ыРХВ, а (3, е)чнРХВ. Например, ХХ У ((0,0), (0,1), (0,2), (1,0), (1,1), (1,2)) и (0,1) и (1, 0) — различные элементы Х Х У. Сзедовательно, с математической точки зрения вам следует отвергнуть запись Зе как неверную для шахматной доски. в" Мы часто будем использовать прямое произведепие для одинаковых множеств.

В этом случае будет удобнее записывать А Х Л Х... Х А как А". Упражнение 1.5. 1. Пусть Х <а, Ь,е) и У=(а, Ь,е,)). Найти ХХ У и Уз. 2. Доказатьс при А ыХ и Вш У, А ХВыХХ У. 3. Доказать, что А Х(В О С)-(А Х В) О (А Х С). 4. Доказать, что для любых непустых конечных множеств А и В выполняются соотношения: а) ИХА И; б) ЮХАчьА; в) АыАХА; г) 1А Х<х)! -!А<; д) А Х В В Х А тогда и только тогда, когда А В. ГЛАВА 2 ОТНОШЕНИЯ Часто в вычислениях необходимо выбирать элементы множеств, которые удовлетворяют покоторому «отношению».

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

Если ллы выберем конкретное значение из Р, то оно может использоваться в некоторых программах иэ Р, и для кажной программы иа Р существует совокупность значений из Р, которые в ней используются. Таким образом, мы имеем соответствие между значениями данных и программами, и, следовательно, существуют элементы в РХ Р, представляющие интерес. Аналогично, если мы сведем рассмотрекие к р жР, то р связывает соответствующие значения данных из Р с результатами из В. Можно рассмотреть данные, приводящие р к остановке, или результаты, которые не могут быть получены из р. Следовательно, мы приходим к подмноллеству Р Х В. (При переработке данных от Р к В возникают некоторые ассоциации, которые могут оказаться полезными для запоминания терминологии.) Перейдем теперь к формальным рассмотрениям.

й 1. Основные понятия п-местным отношением В на множествах Аь ..., А называется подмножество прямого пронзвецення А1Х...ХА.. Другими словами, элементы хн ..., х„(где х1 ш Аи ...) свяааны отношением В тогда н только тогда, когда (хь хэ... „х„) ж В ((хн хи ..., х„) — упорядоченный набор иэ и элементов). Наиболее часто встречаются отношения при и = 2; в атом случае они наэываются бинарными отношениями.

Следовательно, бинарное отношение менарду множествами А и В является просто подмноясеством А Х В. Коли эти множества эквивалентны (скажем, равны А), то будем говорить, что подмножество А' определяет отношение на А. Отношения не являются чем-то новым. Можно построить отношения, которые, несомненно, будут эпакомы читателю. Рассмотрим следующие примеры. Пример 1.1. Пусть А (1,2,3,4,5,6,7,8,9,10). Тогда В ((х, у): х, у ш А, х — делитель у и х < 5) может быть эаписано в явном вице: В ((1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (2, 2), (2, 4), (2, 6), (2, 8), (2, 10), (3,3), (3,6), (3,9), (4,4), (4,8), (5,5), (5,10)).

У Пример 1.2 (шахматы). Как и выше, пусть Р (а, 5, с, А, е, 7', у, й), В (1, 2, 3, 4, 5, 6, 7, 8) и пусть В РХВ. Таким обраэом, Я вЂ” множество всех клеток, обоэначаемых парами (х, у), где х ш Р, у шВ. Определим бннарное отношение С (для ладьи!) ва Я так, что (е, Г)ш С тогда и только тогда, когда е и 1 — элементы Я и ладья может пройти от е к г одним ходом на пустой доске. (Напомним, что ладья может изменять либо гориэонтальную координату, либо вертикальную, но не обе координаты 36 одновременно.) Поэтому Сщ ЯХЯ н С (((/„г.), (/н г<)): (/.

/, и г.чьг,) вли (/. ть /< н г. = г,) ). П На первый взгляд определение С может выглядеть сложно, по внимательное исследование показывает, что значение отношения находится непосредственно и вся необходимая информация содерн<ится в определении. В общем случае ряд различных отношений на множестве А зависит от 1А!. Ббльшая часть этих отношений не представляет особого интереса. Ния<е приведены три отношения, которые полезны при рассмотрении множеств. Определение. Для любого множества А определим толсдестеенное отпошенпе 1„и универсальное отношение Ул следующим образом: 1 ((а, а): а<вА), У ((а, Ь): ашА, Ь<иА). Таким образом, <чл Ат. Так как и ьз А>, то д> является отношением на А и называется пустым отношением. П Пусть отношение В определено в соответствии с иъ>- бражением па рис.

2Л. Необходимо сконцентрировать наше внимание на том, что происходит на концах В, т. е. У Элементы Л, ье Зчвнееты Л ч В, Еееюечты е, ие Пееючеееые е Р еелючечные П е включенные П Е Рис. 2.1 рассмотреть элементы А и В, которые првнадлея<ат В. Они являются элементами подмво>кеств А и В соответственно и, как следовало о>кидать, имеют специальные навванвя.

Определение. Свяжем с каждым бипарным отношением В между А и В два множества — область определения В(В) н область значений Я(В). Ови определяются следующим образом: 0(В) (аи (л, у1<иВ), вх(В) (у: (и, у)<и В), П 37 Пример 1.3. Пусть отношение В такое же, как и в примере 1Л. Тогда Ы(В) (1, 2, 3, 4, 5), Я(В) А. К Пример 1.4. Предположим, что мы имеем некото- рую программу. Она читает деа числа из множества А— (1, 2, 3, 4, 5), обозначаемых х и у, и, если х( у, печа- тает число з (также из А) такое, что х < э ( р.

В любом случае программа останавливается после считывания всех чисел иа А. Задача определяет отношение Р, Р ш А Х А такое, что Р (((х, р), э): х ( у, х ( э < р). Не все входные данные приводят к выдаче результата. Поэтому область определения Р не совпадает с А'. Ясно, что Р (((1, 2), 1), ((1, 3), 1), ((1, 3), 2), ((1, 4), 1), ((1, 4), 2), ((1,4), 3), ((1, 5), 1), ((1, 5), 2), ((1, 5), 3), ((1, 5), 4), ((2, 3), 2), ((2, 4), 2), ((2, 4), 3), ((2, 5), 2), ((2, 5), 3), ((2, 5), 4), ((3, 4), 3), ((3, 5), 3), ((3, 5), 4), ((4, 5), 4)); Я)(Р) ((1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)); Я(Р)= (1„2,3,4). У Хотя каждое отношение является множеством и мо- жет быть обозначено прописной буквой, существует так- же практика обоаначения отношений строчными гречески- ми буквами, например р, о и т.

Часто используют следу- ющие обозначения: а) (а, Ь)ш р, т. е. (а, Ь) наводится в р; б) арЬ, а связано с Ь отношением р; в) Ь ш р(а). Первое из обозначений является естественным (оно следует из определений теории множеств). Второе де- лается более разумным, если мы рассмотрим отношение порядка (которое будет определено несколько ниже), где Вш)т'э и В ((х, р): х(р). Здесь вместо 6В7 мы можем написать 6 < 7; следовательно, мы разрешаем вались любого отношения с использованием рассмотренных выше символов, если результирующая последовательность символов будет однозначно определенной. Третья форма записи является новой и будет преобрааована к более привычным обозначениям в гл.

3. Из заданного бинарного отношения монс- но вывести ряд других отношений, большинство иа которых будут обратными отношениями. О п р е д е л е н и е. Пусть  — бинарное отношение. Определим обратное отношение В ' следующим образом: В-' ((х, у): (у, х)»иВ). Таким образом, В-' связывает те х<е пары элементов, что н В, но «в другом порядке». г' Следовательно, если Вж А Х В, то В-'жВХА, 'Ь(В ') — Я(В) и Я(В ') Я)(В). Чтобы избеягать использования большого количества скобок, будем также испольэовать обозначения лр, а Я, вместо йр(В) и Я(В) соответственно.

У и р а >к н е н и е 2.1. 1. Пусть Х - (2, 4, 6, 8) и р - ((х, у): х, у «а Х и х . у). Выписать все злементы р и р-'. 2. Пусть «» У((а, б, с)). Найти все элементы отношений ~ и ш на Ю. 3. Пусть д' Е» и р ((х, у): х «. у). Описать р'— дополнение р — без использования отрицания отношения «меньше». 4.