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

Какие это множества: (у: у х+г;х,гш Х) и(у: х у+г;х,гжХ)? 5. Предположим, что х является элементом, а не множеством. Тогда у Фх для шобого у, н отсюда следует, что х Ф х. Можно лн упростить множество (х, (х), ((х)Н? Что можно сказать относительно (х, у, (х, уИ? 6. Пусть А — множество всех целых чисел. Описать словами множество Х (х: хшА и х 1 нли (х — 2)шХ). в 2, Простейшие операции над множествами Как мы видели иа рассмотрения «ошибочного множестваз г в яримвре 1.1 необходимо проявлить внимательность при определении множества.

Тем не менее, строя новые множества из старых по простым правилам, можно безопасно получить много интересных примеров. Позднев будут выписаны формальные правила, которым должны удовлетворять операции с множествами, а сейчас введем некоторые обозначения. Начнем с простейших операций. гь Определение. Пусть даны множества А и В. Пересечением мноя>еств А и В иааывается множество всех влементов, принадлежащих А и В, и обозначаетсн А П В; таким образом, Л ПВ (х: хжА и лшВ), Аналогично объединена«А и В обозначается А 0 В и определяется следующим образом: А ОВ (ач х«»А кли х«иВ). Значения »тих обоаначенвй нетрудно вапомпить, но иногда бывают ошибки.

Один из путей запомнить, какой символ обозначает какую операцию,— объединить символы в слове и ааписать «Пересечение» и «Объединение». Эти определения выводятся иа слов «я» и «или», н, как следствие, мы имеем АОВ ВОА, А ПВ ° ВПА и, что, вероятно, менее очевядпо, АОА А, АПЛ А. Эти тождества важны по двум причинам. >»о-первых, ив дальнейших математических рассуждений будет видно, что иногда следует сводить А 0 А (соответственно А П Л) к А или, наоборот, расширять А до А 0 А (соответственно А ПА). Во-вторых, можно не обратить на вто внимание нз-за того, что, выраясенные словами, ети тождества могут каааться лишенными смысла даже тогда, когда онп логически верны.

Заметим также, что определение объединения нспольвует включение «или», называемое так потому, что оно включает «и» так, что (1, 2) 0 (2, 3) (1, 2, 3), И, 2) 0 (2, 3) (2). Элементы в пересечении множеств (в данном случае это — единственное число 2) включаются в объединение.

Это обычная математическая договоренность, и существу« ет пример, в котором математическое вначепне является болев точным, чем при общем употребления, Пример 2Л. В иредполо>кении, что каждый день или дождливый, илн ясный, математическим (или логическим) ответом на вопрос «Ясно или дождливо сегодня)» 16 будет «Да». Определение. Равность множеств А и В (так»ье нааываемая дапо*нвнивм В до А) ааписывается в виде А~В в определяется соотношением А~В (х: х ~в А и х Ф В). Поэтому, если А (), 2, 3) и В (2, 3, 4), то А~В (1) и В~А (4).

Следующее определение включено для полноты. Хотя мы будем редко использовать его непосредственно, однако, как мы увидим в дальнейшем, етот оператор имеет большое значение в машинной арифметике. Определение. Симметрическая равность множеств А и В, т. е. АЬВ, определяется как АЬВ* (А Ц В)1(А й В). Возможно, читателя вапутали обоэначенпя й, (), 1, Л, или, наоборот, он поверил, что они настолько элементарны, что не имеют никакого практического применения, Следующие примеры помогут в этом разобраться.

Пример 2.2. Предполов»им, что мы имеем две программы, наэываемые Р в ч, и что А — множество всех эначенвй данных, доступных Р, а  — множество всех эначений данных, достуш»ых О. Тогда А П В вЂ” множество всех данных, доступных Р и О; А 0  — множество всех данных, доступных по крайней мере или Р, или О; АИ множество всех данных, доступных Р, но недоступных (); В~А — множество всех данных, доступных Д, но недоступных Р; АЛ — мнощество всех данных, доступных только одной иэ программ Р или Ч.

Чтобы полностью определить А и В, мы должпы знать некоторые данные о вычислениях, связанные с Р н Ч. В нашем случае достаточно сказать, что они проиэводятся на некоторой конечной ЗВМ. Перед дальнейшим излов'епием будет удобно определить два специальных множества, Первое иэ пих пустое множество. О яре дел ение, Пустое множество (обозначается И) есть множество, обладающее свойством хФ и» прн любом Второе множество, определение которого зависит от эадачи, пазывают упвверсальным множеством, 2 д. кт«, г. в»а» 1Т Определение. Универсальное множество (обозна чается д') есть множество всех рассматриваемых в данной задаче элементов.

Ограничение д' в атом случае помогает избежать трудностей, подобных тем, которые возникали при рассмотре. нни «мпожества» Р примера 1.1; в любо»г случае большинство элементов несущественно в каждой данной задаче, Например, размеры «Английского словаря», несомненно, неинтересны, если рассматривается поведение отдельной программы на Фортране.

О и р е д е л е н и е. Два множества А и В не пересекаются, если А П В ° И. Определение. В каждом случае, когда й' задано, определим дополнение множества А (обозначается А') как А'-В~А = (хс х ФА), Из определений 8, д' п А' следует справедливость тождеств А 0А'=Е, А ПА' О, В т 4 будет показано, что для данного В' эти тождества достаточны, чтобы однозначно определить А'. Пример 23. Пусть »»' И,2,3,4), А И,3,4), В-(2,3), С И,4). Из определений легко найти, например, А', В П С, С~А и т.

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

Напри- мер, в (А П В)' пересечение ((3)) вычисляется раньше, чем дополнение (И,2,4)). Этого соглашения, очевидно, достаточно. Однако, чтобы избежать такого множества скобок, мы не будем требовать скобок, когда хотим произ. вести операцию дополнения перед любой иэ операций с множествами (Э, П, 1, й). Поэтому АЬВ' означает А П (В') и т. д.

Следовательно, А ПВ' А ПИ,4)-И,4), (А П В) ' = (3) ' - И, 2, 4), (В~А)Э С =(2) ОС= И, 2,4). Р 13 Читатель может быть удивлен, почему изложение построено на понятии мноя~ества, а не числа. Действительно, до сих пор мы использовали числа только как элементы множеств. Это делалось лишь для того, чтобы читатель познакомился с объектами, с которыми ему придется работать. Дело в том, что существуют множества более сложные, чем числа; мы можем получить числа из множеств, но пе наоборот. Однако для многих приложений последующей теории необходимо сделать точные утверждения о некоторых специальных множествах чисел.

Чтобы обеспечить основу, с помощью которой будут конструироваться такие множества, определим множество Х целых иоложительных чисел (натуральных чисел): Х (1,2,3, ...), Точное определение множества Х вместе с арифметическими операциями + и ~ и его упорядочивание будут даны ниже. Однако в настоящей главе мы будем предполагать, что читатель знаком с некоторыми свойствами Х. Аналогично Е определяют как множество всех целых чисел: Е (..., — 2, — 1, О, 1, 2, ...). Конечно, множества Х и г' не могут быть выписаны явно (они достаточно велики), но в настоящее время мы должны понимать «...э как аи так далее».

Рассмотрим теперь множество А (1, 2, ..., и) (х: хыХ, 1<х<п), Оно имеет и элементов. Будем говорить, что мощность (или размер, норма, длина) этого множества есть п. Это обозначается как )А! сатй (А) в. Далее любое множество В, которое имеет то же число элементов, что и А, имеет такую л'е мощность, и, конечно, эти элементы пе надо пересчитывать. Для небольших множеств достаточно легко пересчитать элементы, но для других множеств (например, Х) это может быть невозможно.

Далее мы дадим строгое, но в то же время неформальное правило для вычисления количества элементов. Опре деле п не. Роворят, что миолгество Х конечно, если Х = И пли если для некоторого и ыХ существует множество (1, 2...,, к) такое, что опо имеет то же самое ЯФ 19 число элементов, что и Х. Если Х чь Ю н никакого я пе может быть найдено, то Х называют бесконечным. Сейчас, когда мы ввели некоторые определения, можно сформулировать несколько упражнений.

Чтобы сделать мноя~ества легко записываемыми, мы снова будем использовать числа и буквы для элементов, но будем помнить, что те же операции могут быть применены к произвольным множествам. Упражнение 1.2, 1. Пусть 8'-(1,2,3,4), У (1,2,4), Х вЂ” (1, 5), Я (2,5), Найти множества: а) ХПУ';б) (ХПЯ)0Г; в) Х О (У П г); г) (Х О У) П (Х О г); д) (ХО У)', е) Х'П г"", ж) (ХП У)'; э) (Хи У)Ог; н) Хи(УОг); «) Хи; л) (Х~г)и(уи), 2. Пусть й' (а,б,с,д,е,(), В ((,е,с,а), А (а, Ь, с), С (с(, е, (), Найти множества; а) А~С; б) В~С; в) С~В; г) Л~В;д) А'ОВ; е) ВПА", ж) Л ПС; з) СПЛ; и) СЛЛ. 3. Даны два произвольных множества А и В такие, что Л П В ° И, Что представляют собой множества Л~В и В~А"г 4.