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

Вместо этого мы начнем с описании таких начальных понятий, как множество. Хотя материал может показаться простым, это делается для того, чтобы читатель мог свободно разобрать примеры, приведенные в конце параграфа. Множество — это совокупность определенных различаемых объектов таких, что для любого объекта можно установить, принадлежит этот объект данному множеству или нет. Множество, которое подчиняется лишь такому ограничению, может содержать объекты почти любой природы. Например: — множество всех подземных станций Лондона; — множество левых ботинок; — множество натуральных чисел: 4, 2, 3, 4 и т, д.; — множество символов, доступных специальному печатающему устройству; — множество кодов операций конкретного компьютера; — множество зарезервированных слов языка Пасиаль.

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

10 Множества обычно обозначают прописными буквами, например А, и сяецнфицируют одним из двух путей. Если множество содержит несколько элементов, то мы просто записываем все его элементы. Например, если мы определим А как множество всех целых чисел строго между 6 и 10, то это можно записать следующим образом: А (7,8,9) и прочитать как «А — множество, содержащее 7, 8, 9», Здесь символ «» используется в определенном смысле: А равно множеству„.

Далее будет использоваться высказывание «равно ли А ...». Поэтому мы должны предложить процедуру установления справедливости этого утверждения. Другими словами, множество моя~ко охарактеризовать определенными свойствами, и, следовательно, множество А можно определить как А 1ес х — целое число и 6<я<10) и прочитать кзк «А есть множество всех л таких, что ...». Множеству А првнадлежат только те элементы, которл»е являются целыми числами, большими 6 и меньшими 10, т. е.

7, 8 и 9, и, следовательно, мы имеем 7, 8, 9, как и ранее. Множества часто рассматривают как «неупорядочен- ные совокупности элементов», хотя иногда полезно под- черкнуть, что,например, (7,8,9) (8,9,7) 19,8,7) мы не делаем никакой оговорки о порядке, в котором рассматриваются элементы, поэтому было бы неправильным допускать какой-либо определенный порядок. Для любого заданного объекта можно определить, принадлежит ли он множеству А. В частности, если число принадлежит множеству, то будем говорить, что «оно является элементом множества». Так, например, если 7 является элементом множества А, то это утверл»денио может быть записано следующим образогк «7а А».

Утверждение «6 не является элементом А» будем обозначать как «6 ФА», гг Символ <и происходит от греческой буквы е. Отрицание обозначается через Ф. Такое обозначение отрицании операции (илк операцвовного символа) является общим в математике н часто будет всвольэоваться в дальнейшем. Надо подчеркнуть, что следовало бы обратить большее внимание на спецификацию множеств. Для каждого множества должна быть записала его спецификация. Процесс образования мноя<ества может продолжаться бесконечно долго.

В результате получается множество, соответствующее определению. Частичная спецификация может быть полезной в том случае, когда не ясно, принадлежит данный элемент множеству или иет. До сих пор нам встречались символы (:), („,), ж и Ф. Их применение кажется достаточно простым, однако оно требует определенных навыков, которые будут проиллюстрированы на следую<цих примерах. П р и м е р (Л. Какие из приведенных определений множества являются правильными: А ((,2, 3), В (5, В, 6, 7), С (х; хФА), 0 (А, С), Е (х: х ( или х (у) и у<вЕ), Е (множества, которые не явля<отса элемоптами самих себя) (х: х — множество и х Ф х)? Если число членов множества А легко вычисляется и среди элементов множества вет повторений, то определение верно.

Множество В выглядит такя<о правильным, эа исключением лишь того, что число В встречаетсн дважды. Мы можем проверить, припадлея<ит ли элемент множеству или нет. Таким образом, это нааболее важное требование в определении множества выполнено. Следовательно, мы может рассматривать эту запись как верную и эквивалентную (5, 6, 7), Однако в этой ситуации возникают следующие проблемы. Если мы рассмотрим первоначальное определение В и выбросим одно из чисел В из множества, то мы, очевидно, будем иметь В <в В и В Ф В. Возникает противоречив. Поэтому мы будем рассматривать повторение символов в определении мноя<еств как упоминание одного и того и<е символа, а его дублирование как недо- $2 смотр; удаление повторяющихся символов образует основу для некоторых дальнейших математических рассуждений.

Мпоя«ество А содержит числа; это моя<ет вызвать недоумение, так как числа не существуют. Волее точно, мы используем символы чисел; эти символы называются так же, как и числа. Поэтому  — г«нон«ество имен, и мы обычно используем имена, чтобы представить объекты (элементы), на которые ссылаемся. В вычислениях имена имеют особов значение, особенно в изучении семантики программных языков (смысла программ).

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

Из данной информации нельзя выяснить правильный ответ, поэтому в данном случае следует быть осторожным. Определение С также справедливо как А, так как, если х<вА, то хФ С и, если л ФА, то л«в С. Множество С очень велико: оно содержит «вой», за исключением чисел 1, 2 и 3. Обозначение «вой» выделено и, как мы скоро увидим, «опасно«с математической точки арения. Так как определения Р, А и С представляют множества, то отсюда получаем, что определение Р также справедливо. Заметим, что зто — множество множеств (ничего неверного в этом нет!) такое, что оно имеет только два элемента, в частности 1 Ф Р, даже если 1 ««А и А «в Р. Зто легко проверить, так как 1 «" А, 1 чь С я только А и С являются элементами Р.

Множество Е является первым примером рекурсивно определяемого множества; оно определяется (частично) в терминах самого себя. Конструктивный процесс продолжается бесконечно, поэтому мы должны иметь правило для определения элементов. Мы не можем записать их явно. Заметим, что Е не определяется полностью в терминах Е. Мы должны знать о множестве что-то, что не 13 зависит от определенна; в данном случае это то, что 1ш К. Имеем: 1 (и Е, поэтому (1) ж Е, (1) ж К, поэтому П1Н ж Е, Н1П ж Е, поэтому (((1Ш ж Е и т.

д. Хотя конструктивный процесс неограничен, берл любой элемент и располагая достаточным временем, можно определить, содержится ли этот элемент в К. Перейдем теперь к Р; зто достаточно трудная задача. Чтобы увидеть, почему Р не может существовать, мы сначала допустим существование, а затем продемонстрируем, что существует особый элемент (обозначим его через р) такой, что мы ве можем определить, у жР илн у Ф Р.

Вообще исследование «неудобного» примера, па котором мы можем показать логический изъян, проводится нелегко; однако в данном случае мы можем использовать само множество Р. Чтобы прояснить дело, давайте обозначим это множество через С. Если, как мы предполагаем, Р— искомое множество, то или 6 ж Р, илп 6 Ф Р. Рассмотрим два возможных случая: а) 6»вР. Тогда 6 удовлетворяет условию содержания, т. е. СФС, и, следовательно, 6 ФР; б) 6 ФР говорит о том, что 6 пе удовлетворяет условию вхождения в Р, и, следовательно, 6 «в Р.

Следовательно, во всех случаях мы приходим к противоречию. Поэтому Р не может существовать. Где же была сделана ошибка? Множества множеств, вероятно, разрешаются, и бесконечно большие множества (например, рассмотренное выше множество Е) также разрешаются; однако с «множеством всех множеств» нельзя работать в обычной теории множеств — это требует другого рода математики. Эта аномалия теории множеств известна как парадокс Рассела. Коли мы уже имеем множество Н, то можно определить У: У ° (ал х »в Н и х ж х).

Р Таким образом, мы будем испольэовать только множества, которые могут быть явно записаны или же построены путем хорошо определенных процессов. Поэтому множества не так тривиальны, как опи могли вначале показаться. Однако, следуя приведенным выше правилам, работа с ними не будет особо трудной. Попытайтесь сделать самостоятельно следующее упражнение. 14 Упражнение 1Л. 1. Рассмотроть по крайней мере две возможные интерпретации множества (Смит, Смит, Браун).

Определить каждую из ннх настолько однозначно, насколько зто возможно. 2. Рассмотреть следующие четыре множества. Выяснить, как записи зтих множеств могут быть упрощены и какие из них эквивалентны. Предложить все возможные интерпретации, удовлетворяющие описанным выше предположениям: а) (1, 2, Э, 4); б) П, П, П1,!Ч, Ч); в) (1, один, опе, ипо, еш); г) (5, Ч, пять, Пте).

3. Проверить справедливость утверждений «Это утверждение неверное и «я лгун». Какие слова в утверждении требуют собственного (т, е. математически точного) определения для того, чтобы сделать ответы математически строгими? 4. Пусть Х вЂ” множество (1, 2), а У вЂ” множество (х: х у+ г; у, г ж Х). Определить в явном виде множество У.