Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 5

б. Множество К=(йн „., й ) команд ЭВМ отображается в машинные коды этой ЭВМ, т. е. в натуральные числа. Кодирующая функция у имеет тип К-«-А!. С помощью суперпозицни этой функции и арифметических функций оказываются возможными арифметические действия над командами (которые сами по себе числами не являются!), т.

е. функции ~р(й,) +~р(йз), <~(й,) )-4 и т. д. в. В функции )~(хь хг, хз) =х,+2х,+7хз переименование хз в хз приводит к функции )~(хь хм х,) =х~+2хз-).7хм которая равна функции двух аргументов )з(хь хз) =х~+ +9хз. Переименование х, и хз в хз приводит к одноместной функции )з(хз) =!Ох,. г. Элементарной функцией в математическом анализе называется всякая функция 7, являющаяся суперпозицией . фиксированного (т. е.

не зависящего от значений аргументов 7) числа арифметических функций, а также функций е", 1оц х, з!их, агсз1н х. Например, функция !ой'(х~-!-хз)+ +Зз!пз!их~+ха элементарна, так как является результатом нескольких последовательных суперпозиций х~+хм х', 1оп х, Зх, з1п х. д.

Всякая непрерывная функция п переменных предста- вима в виде суперпозицин непрерывных функций двух переменных. (Этот результат получен в 1956 — 1957 гг. в работах А. Н. Колмогорова и В. И. Арнольда н является решением 13-й проблемы Гильберта.) е. Рассмотрим множество (1, 2, 3) и два преобразования этого множества: а (1«3, 2- 3, 3 — «1) н !1=(1- 2, 2 — «-1, 3-«-1). Обычно преобразования конечных множеств записывают так: а= ( ), р= ( 7!.

Композиция преоб- (ЗЗ 1) разований — это новое преобразование: ар=( ), ра = '123~ (,! 1 2)' =(ззз) Способы заданий функций. Наиболее простой способ задания функций — это таблицы, т. е. конечные списки пар (х, г(х)). Однако таким образом могут быть заданы только функции, определенные на конечных множествах. Таблицы функций, определенных на бесконечных множествах (например, логарифмических, тригонометрических и т. д.), задают зти функции только в конечном числе точек. Для вычисления значений (приближенных!) функций в промежуточных точках служат правила интерполяции.

Другим не менее известным способом задания функций является формула, описывающая функцию как суперпозицию других (исходных) функций (пример 1,10,г). Если способ вычисления исходных функций известен, то формула задает процедуру вычисления данной функции как некоторую последовательность вычислений исходных функций. Вычисления функций по таблицам, формулам, а также с помощью графиков являются частным видом вычислительных процедур. Для функции, заданной таблицей, процедура заключается в поиске нужной строки таблицы; для формулы= в последовательном вычислении всех функций, входящих в суперпозицию.

Существуют вычислительные процедуры, не относящиеся к указанным трем видам. Среди них особо следует выделить рекурсивные процедуры. Рекурсивная процедура задает функцию 1, определенную на Км следующим образом: 1) задается значениег (1) (илн !'(0)); 2) значение !(и+1) определяется через суперпозицию !(и) и других, считающихся известными, функций.

Простейшим примером рекурсивной процедуры является вычисление функции п1: !) О!=1; 2) (и+1)1=п!(и+1). В правой части последнего равенства имеется формула, однано это значение функции существенно отличается от задания формулой типа примера! ЛО,г. Отличие состоит в том, что для вычисления 8! необходимо сначала вычислить 71, тогда как в примере 1.10,г вычисление для любой тройки аргументов происходит «непосредственно».

Точнее, для вычисления и! требуется п умножений, т. е. число вычислительных шагов растет с ростом аргумента; для вычисления же функции примера 1.10, г требуется всегда одно н то же число шагов (если шагом считать вычисление функции, входящей в суперпозицию), равное восьми. 28 Наконец, возможны описания функций, которые не содержат способа вычисления функции, хотя сомнений в том, что функция однозначно задана, не возникает. Определим, например, функцию следующим образом: 1х, если х Е М. („(х) = !О, если хц-"М,„. Из описания Мл (см. $ 1.1) не видно, как убедиться в том, что хфМ, поэтому нет гарантии, что 1„(х) можно вычислить.

Отступление 1.3. для функций возникает тот же вопрос, что и для множеств: что значит «задать функцию»? По смыслу нашего определения задать функцию 1> А-»В — это значит описать определяющее ее подмножество АЭСВ, поэтому вопрос сводится н заданию неиоторога множества. Однако можно определить понятие функции, ие используя языка теории множеств: функция считается заданной, если задана вычислительная процедура, которая по любому заданному значению аргумента выдает соотиетстзующее значение функцив. Фу>гкция, опреде. ленная таким образом, называется вычислимой.

Пропедура должна однозначно приводить к результату. Уточнение понятия однозначной и результативной процедуры привело к созданию теории алгоритмов. Понятие алгоритма может быть принято за исходное при построении всей системы понятий математики. Такой подход и обоснованию математики, называемый канструктинным, допускает только те математические объекты н утверждения, которые могут быть получены с помощью алгоритмов. С этой точки зренпя описанная ранее функция (я вообще не заслуживает названия функции, поскольку для нее не указан алгоритм вычисления. Понятие множества перестает быть первнчным; оно определяется с помощью разрешающей нли порп>икающей процедуры (см. й и!), Множества, для которых нет таких процедур, просто не рассматриваются. Достоинства конструктивного подхода достаточно ясны Однаио его последовательное проведение показало, что он требует более радикальной ревизии основных понятай математики, чем это кажется с первого взгляда, и иногда приводит к значительным концептуальным и изыкозым неудобствам.

Поэтому в качестве «математического мировоззрения» конструктннизм разделяется относительно небольшим числом математиков, хотя, пожалуй, никто ие отрицает преимущести конструктивных методов в тех случаях, когда оци возможны. ЕЗ, ОТНОШЕНИЯ Подмножество ЛыМ" называется и-местным отношением на множестве М.

Говорят, что а>, „а„находятся в отно- 29 шенин Я, если (аь ...,а,)~)1. Одноместное отношение— это просто подмножество М. Такие отношения называют признаками: а обладает признаком )г, если пена и Р«:-М. Свойства одноместных отношений — это свойства подмножеств М; поэтому для случая п=! термин «отношение» употребляется редко.

Примером трехместного (нли, как говорят, тернарного) отношения является множество троек нападающих в хоккейной команде. !(аждый из нападающих находится в этом отношенИи со всеми теми игроками, с которыми он играет в одной тройке (один нападающий может, вообще говоря, участвовать более чем в одной тройке). Наиболее часто встречающимися и хорошо изученными являются двухместные, или бинарные, отношения. Именно о ннх будет идти речь в дальнейшем (слово «бинарные» будем опускать). Если а, Ь находятся в отношении Р, это часто записывается как а1гЬ. Пример 1.11.

а. Отношения на Л!: 1) отношение ( выполняется для пар (7,9) и (7,7), но не выполняется для пары (9,7); 2) отношение «иметь общий делитель, отличный от единицы», выполняется для пар (6, 9), (4, 2), '(2, 4), (4,4), но не выполняется для пар (7, 9) и (9, 7); 3) отношение «быть делителем» (т. е. аРЬ означает «а — делитель Ь») выполняется для пар (2, 4) и (4, 4), но не выполняется для пар (4, 2) и (7, 9).

б. Отношения на множестве точек действительной плоскости: 1) отношение «находиться на одинаковом расстоянии от начала координат» выполняется для пары точек (3, 4) и ( — 2, )~ 2!), но не выполняется для пары точек (3, 4) и (1, 6); это отношение совпадает с отношением «находиться на одной и той же окружности с центром в начале координат»; 2) отношение «находиться на разном расстоянии от начала координат» выполняется для тех и только тех пар точек, для которых не выполняется предыдущее отношение; 3) отношение «быть симметричным относительно оси х» выполняется для всех пар точек (хь у~) и (хм у~), удовлетворяющих условию х~ =хм у~= — ум в. Отношения на множестве людей: «жить в одном городе»; «быть моложе»; «быть сыном»; «быть знакомым».

Пусть дано отношение Р на М. Для любого подмножества М~с:-М естественно определяется отношение Р', называемое сужением Р на Мь которое получается из Я удалением всех пар, содержащих элементы, не принадлежа- щие М!. Иначе говоря, Я'=)тПМ!. Строго говоря, 14 н )т"— это разные отношения, с разными областями определения. Однако если не возникает разночтений, этот педантизм не соблюдается; например, вполне можно говорить об отношении «быть делителем», не уточняя, задано оно на М или каком-либо его подмножестве '.

Для задания бинарных отношений можно использовать любые способы задания множеств !например, список пар, для которых данное отношение выполняется). Отношения на конечных множествах обычно задаются списком или матрицей. Матрица бинарного отношения на множестве М 1о!, ..., и ) — это квадратная матрица С порядка тп, в которой элемент с;1, стоящий на пересечении )-й строки и 1-го столбца, определяется следующим образом: 1, если а,)тат; см —— О в противном случае.

Например, для конечного множества 11, 2, 3, 4, 5, 6) матрицы отношений 1 — 3 из примера 1.11,а приведены в табл. 1.1, а — а соответственно. Для любого множества М отношение Е, заданное матрицей, в которой по главной диагонали стоят единицы, а в остальных местах — нули, называется отношением равенства на М. Таблица 1,1 1 2 3 4 5 6 1 2 3 4 5 6 1 ! 1 1 1 1 6!О!О! О О! ОО1 О О О1ОО О О О О 1 О О О О О О ! О О О О О О О 1 О 1 О 1 ОО)ОО1 О 1 О 1 О 1 О О О О 1 О О 1 1 1 О 1 1 1 1 1 1 1 О О О 1 1 1 1 О О О 1 1 1 О О О О 1 1 О О О О О 1 в) б) ' Отметим, что это допустимо только потому, что совершенно ясно, как перенести это отношение с У на любое подмножестао Ф.