1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

Этот порядок отражает, однако, не столько какие-то внутренние свойства элементов множества М, сколько свойства его нуыерации и не исчерпывает других возможных способов упорядочивания. Поэтому понятия занумерованности и упорядоченности нужно различать. Аналогично наборам, для множеств используют символику, которая, обозначая само множество М, одновременно вводит обозначение для любого элемента т атого множества: М= (т) нли (для счетных занумерованных множеств) М = (т;) () = 1,...) и (для конечных множеств) М = (т„..., т„).

ГЛ. 2. ПОСТАНОВКА ЗАДАЧИ И ОБЩАЯ ТЕОРИЯ В этом месте стоит такн<е отметить разницу между занумеро- ванными конечными множествами и наборами. Объект, являю- щийся компонентой набора, отличается от элемента множества тем, что он всегда воспринимается вместе с информацией о том, какой компонентой набора он является. В частности, набор мо- жет иметь несколько одинаковых компонент, а для множеств го- ворить о нескольких одинаковых его элементах не имеет смысла. Эти различия могут быть подчеркнуты примерами нескольких множеств, связанных с набором — вектором а = (а, = 1, а« = 3, а, = 1, а, = 2), множество названий компонент (а„а„а„а4), множество названий компонент вместе с самими компонептамн ((а„ 1), (а„ 3), (а„ 1), (а4 2)), множество значений компонент (1, 2, 3). Наиболее близким к исходному набору является второе множество.

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

В этой трактовке с понятием переменной связываются три обоаначения, например, х — для самой переменной, х — для ее произвольного значения, являющегося элементом множества Х, которое называется областью задания переменной х. Употребление переменных величин в первом смысле можно рассматривать как некоторую вольность, когда обозначения для переменной и ее значений не рааличаются или же различаются по контексту. Последнее, например, имеет место в алголе 60. В программе начало вещ х; ввод (х)„х:= х + 1; вывод (х) конец % ЗЛ.

КРАТКОЕ ПОВТОРЕНИЕ МАТЕМАТИЧЕСКИХ ОСНОВ 99 п.рвов, второе и третье вхождение буквы х обозначает переменную величину, четвертое и пятое вхождение обозначают ее текущее значение, а служебное слово вещ характеризует область задания х. Если в отображении Р: Х-~У множество Х является областью аадания некоторой переменной величины х, то мы говорим о существовании функции р (х) аргумента х.

Если х — значение х, то Р(х) называется значением ерункцпи р (х), соответствующим указанному значению аргумента. В некоторых случаях имеет смысл говорить об отображениях Я:М-~Х, когда соответствие между элементами М и Аг существует не для любых элементов М. Отображение Я в атом случае называют частичным. Аналогично говорят н о частичных функциях. Существует несколько стандартных процедур построения новых множеств из заданных. Пусть дан ' набор из и непустых множеств Мг = (тх), Ме = (тз),..., М„= (т„). Прямым произведением, Мг Х х М, Х... х М„, называется множество, элементами которого являются любые наборы вида (тп тч,..., т„), Если хотя бы одно из множеств М, пусто, то, по определению, их прямым произведением будет пустое множество. Любое подмножество В прямого произведения двух множеств М (т) и У = (и) называется бинарным отношением, ааданным на множестве М Х )У.

Элементы (т, и) множества В в этом случае называют парами, удовлетворяющими заданному бинарному отношению. Пусть даны два множества, М и Ф. Из них можно построить множества, которые называются объединением (МДФ), пересечением (МП)У) и разностью (М ~ ЛГ). Характеристическими О войствами. элементов этих множеств является их принадлежностьл М или )ч' — для объединения, как М, так и )ч — для пересечения, М, но не У вЂ” для разности. Если АГ с: М, то М~Аг называется дополнением к )ч' до М. Конструктивный объект. В математике часто выделяют объекты, построения и рассуждения, которые называют конструктивными. Это слово употребляют потому, что для такого рода объектов, построений и рассуждений хотят подчеркнуть дополнительное допущение, состоящее в том, что эти объекты можно взять и Гл х пост«нозкА 3АдАчи н Овщ«я твогия рассматривать, построения можно выполнить, а рассуждения можно провести «эффективном Конкретизация этого допущения в реальном мире означает, что осуществление любого из указанных действий должно быть выполнимо в конечное время и с использованием конечного количества материальных средств.

В качестве исходных конструктивных объектов рассматривая«г лишь такие, в отношении которых признается бесспорным допущение об их элементарности и возможности всегда их рассматривать целиком. Для того чтобы контролировать эти свойства конструктивных объектов, для них всегда уточняется их представление, т. е. изображение с помощью ограниченного набора «поистине» примитивных объектов, которые считаются «атомами» всякого объекта.

Чаще всего в конструктивном подходе такими атомами являются элементы некоторого фиксированного конечного мнон;ества, называемого алфавитом. Сами элементы называются буквами. С каждым алфавитом связывается множество слов этого алфавита. Каждое слово — это конечный упорядоченный набор букв, в котором мы различаем начальную букву, конечную букву, для каждой буквы, кроме начальной, ее левого соседа, и для каждой буквы, кроме конечной, ее правого соседа. Существует также пустое слово, не содержащее ни одной буквы. Число букв в слове называется его длиной. Практически, любые представления конструктивных объектов сводятся к их изображению в виде слов в некотором алфавите.

Например, натуральные числа в тщательно написанных работах по конструктивной математике изображают словами в однобуквенном алфавите, так что число п изображается словом длины и. Какие бы то ни было соответствия нли построения при конструктивном подходе считаются заданными или осуществимыми только в том случае, если они могут быть описаны в одном из принятых точных определений алгоритма, выполняющего действия над конструктивными объектами. В конструктивной математике рассматриваются бесконечныэ множества (например, натуральный ряд, множество всех слов в некотором алфавите), однако не допускаются никакие действия или рассуждения, которые используют принцип актуальной бесконечности.

Элемент т множества М считается данным только в том случае, если существует алгоритм, применение которого к другому уже данному конструктивному объекту поаволит получить элемент т. Принцип потенциальной бесконечности позволяет нам считать данным любое натуральное число или любое слово в заданном алфавите. Утверждение о существовании некоторого объекта признается конструктивным, если оно опирается на алгоритм явного его построения.

Такому доказательству противопоставляется косвенное рассуждение, когда из предположения о несуществовании та- $2Л. КРАТКОЕ ПОВТОРЕНИЕ МАТЕМАТИЧЕСКИХ ОСНОВ 6$ кого объекта приходят к противоречию (доказательство от противного). Граф. Мы закончим наш повторительный раздел описанием одной конструкции, которая будет постоянно использоваться в дальнейшем. Пусть дано конечное множество А = (а„..., а„). Ориентированным графом 6 = (А, Г) называется набор нз А и любого бинарного отношения Г, заданного на прямом произведении А х А = ((а;, а;) ). Элементы множества А называются вершинами графа, а пары (аи аг), удовлетворяющие бинарному отношению, называются дугами графа.

В дуге (а;, а;) вершина а~ называется предшественником своего преемника а;. Употребление таких слов как граф, верппгны и дуги связано с геометрическим представлением бинарных отношений на плоскости или в пространстве, когда вершины изображаются точками, а дуги — стрелками, ведущими от предшественников к преемникам. С использованием ориентированных графов мы уже познакомились в предыдущей главе на примере операторных схем, где операторы были вершинами, а передачи управления — дугами. Пусть А' — подмножество множества А. Тогда подграфом 6' графа 6 называется граф 6' = (А', Г'), где бинарное отношение Г' = Г()(А' х А'). Мы видим, что 6' — это граф с вершинами А', между любой парой которых проводится дуга в том и только в том случае, если эти вершины соединены дугой в графе 6.

Бинарное отношение Г, обладающее тем свойством, что если (а;, а;)веГ, то и (а;, а;) я Г и (аы а;) я (не принадлежит) Г, называется симметричным и антирефлексивным. Любое такое симметричное и антирефлексивное бинарное отношение Г задает не- ориентированный граф. Элементы множества А по-пре'кнему называются вершинами графа, а каждая пара (аи а;) и (ая а;) из Г вместе называется ребром, соединяющим смежные вершины а~ и а;. В геометрическом представлении неориентированного графа на плоскости или в пространстве вершины изображаются точками, а ребра — линиями, соединяющими изображения смежных вершин.

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

Характеристики

Список файлов книги