Способы задания функций

Наиболее простой способ задания функций – это таблицы, т. е. конечные списки пар (х, f (х)). Однако таким образом могут быть заданы только функции, определенные на конечных множествах. Таблицы функций, определенных на бесконечных множествах (например, логарифмических, тригонометрических и т. д.), задают эти функции только в конечном числе точек. Для вычисления значений (приближенных) функций в промежуточных точках служат правила интерполяции. Другим не менее известным способом задания функций является формула, описывающая функцию как суперпозицию других (исходных) функций. Если способ вычисления исходных функций известен, то формула задает процедуру вычисления данной функции как некоторую последовательность вычислений исходных функций.

Вычисления функций по таблицам, формулам, а также с помощью графиков являются частным видом вычислительных процедур. Для функции, заданной таблицей, процедура заключается в поиске нужной строки таблицы; для формулы – в последовательном вычислении всех функций, входящих в суперпозицию. Существуют вычислительные процедуры, не относящиеся к указанным трем видам. Среди них особо следует выделить рекурсивные процедуры. Рекурсивная процедура задает функцию f, определенную на N₀, следующим образом:

1) задается значение f (1) (или f (0));

2) значение f (n+1) определяется через суперпозицию f (n) и других, считающихся известными, функций.

Простейшим примером рекурсивной процедуры является вычисление функции п!: 1) 0! = 1; 2) (п+ 1)! = n!(n+1).

Для функций возникает тот же вопрос, что и для множеств: что значит «задать функцию»? По определению задать функцию f: А® В – это значит описать определяющее ее подмножество А´В, поэтому вопрос сводится к заданию некоторого множества. Однако можно определить понятие функции, не используя языка теории множеств: функция считается заданной, если задана вычислительная процедура, которая по любому заданному значению аргумента выдает соответствующее значение функции. Функция, определенная таким образом, называется вычислимой. Процедура должна однозначно приводить к результату. Уточнение понятия однозначной и результативной процедуры привело к созданию теории алгоритмов.

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

3.6. Отношения

Подмножество R Í M ⁿ называется п-местным отношением на множестве М. Говорят, что а₁,...,а_n находятся в отношении R, если (а₁, ..., a_n) Î R. Одноместное отношение – это просто подмножество М. Такие отношения называют признаками: а обладает признаком R, если aÎ R и R Í M. Свойства одноместных отношении – это свойства подмножеств М; поэтому для случая
п = 1 термин «отношение» употребляется редко.

Наиболее часто встречающимися и хорошо изученными являются двухместные, или бинарные, отношения. Именно о них будет идти речь в дальнейшем (слово «бинарные» будем опускать). Если а, b находятся в отношении R, это часто записывается как aRb.

Пример 3.12.

1. Отношения на N:

a) отношение £ выполняется для пар (7,9) и (7,7), но не выполняется для пары (9,7);

б) отношение «иметь общий делитель, отличный от единицы», выполняется для пар (6,9), (4,2), (2,4), (4,4), но не выполняется для пар (7, 9) и (9, 7);

в) отношение «быть делителем» (т. е. aRb означает «а–делитель b») выполняется для пар (2, 4) и (4, 4), но не выполняется для пар (4, 2) и (7, 9).

2. Отношения на множестве точек действительной плоскости:

а) отношение «находиться на одинаковом расстоянии от начала координат» выполняется для пары точек (3, 4) и (–2, ), но не выполняется для пары точек (3, 4) и (1, 6); это отношение совпадает с отношением «находиться на одной и той же окружности с центром в начале координат»;

б) отношение «находиться на разном расстоянии от начала координат» выполняется для тех и только тех пар точек, для которых не выполняется предыдущее отношение;

в) отношение «быть симметричным относительно оси х» выполняется для всех пар точек (x₁, y₁) и (x₂, y₂), удовлетворяющих условию х₁ =x₂, y₁ = – y₂.

3. Отношения на множестве людей: «жить в одном городе»; «быть моложе»; «быть сыном»; «быть знакомым».

Пусть дано отношение R на М. Для любого подмножества M₁ Í M естественно определяется отношение R', называемое сужением R на M₁, которое получается из R удалением всех пар, содержащих элементы, не принадлежащие M₁. Иначе говоря, R' = R Ç M. Строго говоря, R и R' – это разные отношения с разными областями определения. Однако, если не возникает разночтений, этот педантизм не соблюдается; например, вполне можно говорить об отношении «быть делителем», не уточняя, задано оно на N или каком-либо его подмножестве.

Для задания бинарных отношений можно использовать любые способы задания множеств (например, список пар, для которых данное отношение выполняется). Отношения на конечных множествах обычно задаются списком или матрицей. Матрица бинарного отношения на множестве
М = {а₁, …, a_m} – это квадратная матрица С порядка т, в которой элемент c_ij, стоящий на пересечении i-й строки и j-го столбца, определяется следующим образом:

Например, для конечного множества {1, 2, 3, 4, 5, 6} матрицы отношений 1 – 3 из примера приведены в табл. 3.1, a, б, в соответственно.

Таблица 3.1

Для любого множества М отношение Е, заданное матрицей, в которой по главной диагонали стоят единицы, а в остальных местах – нули, называется отношением равенства на M.

Поскольку отношения на М задаются подмножествами М ², для них можно определить те же операции, что и над множествами. Например, отношение £ является объединением отношений < и равенства.

Определим еще одну операцию над отношениями. Отношение называется обратным к отношению R (обозначение R ^-1), если a_iR ^–1a_j тогда и только тогда, когда a_jRa_i (a_iR ^–1a_j « a_jR ^-1a). Из определения непосредственно следует, что (R ^–1) ^–1 = R. Для отношения £ обратным является отношение ³.