Программа как математический объект: Методические указания для самостоятельного изучения темы и выполнения РГР, страница 11

Для функций действительны операции над множествами, если они не нарушают правило единственности значений функции. Так, если f и g - функции, то f Çg, f - g  также являются функциями, но f È g не может быть функцией, так как (x, y) Î f, (x, z) Î g не удовлетворяет требованию единственности значения функции для случая y ¹z.

 Если f и g- функции, то  {(x, y) | y = f (g (x))} называется композицией ( суперпозицией)  функций g и f и обозначается как f ° g.

 

   Рис. 10

Если функция f рефлексивна, то она называется тождественной функцией при f(x) = x для каждого xÎD(f).

Если существует функция f т такая, что f т(f  (x)) = f( f т(x)) = x, то f т называется обратной функцией от f.

Если область значения функции f - это одноэлементное множество, то функция является константой ; если же область значения функции является множество {истина , ложь},она называется предикатной функцией ( предикат). Предикатная функция часто задаётся условиями из области определения. Например, предикат, заданный в форме

p = {( x, истина ) | x ³ 0} È {( x, ложь) | x < 0}является обозначением того, что x ³0, т.е. выделяется область, в которой предикат p принимает значения истина.

Предикатные функции можно использовать для описания других функций. Например,

f = {(x,y) | (x ³ 0 ® y = 3 | x < 0 ® y =4)}

В общем случае правило для функции можно задать в форме условного правила вида ( предикат ® правило), разделённых вертикальной чертой:

(p1 ® r1 | p2 ® r2 | ... | pk ® rk )

Такое условное правило означает следующее: предикаты p1, p2, ... pk вычисляются последовательно слева направо  и будет выполнено правило

ri , если соответствующий предикат pi первым принял значение истина ; если ни один из предикатов не принимает значение истина, то правило считается неопределённым. Другими словами данное выражение следует рассматривать как схематической записью оператора CASE или схему вложенных операторов IF_THEN_ELSE. Если pk является предикатом с постоянным значением истина, а все предшествующие предикаты принимают значение ложь, то в этом случае всегда выполняется правило rk; например,

f = {(x, y) | xÎ D,( x делится на 2 ® y = x/2 |

                   x делится на 3 ® y = x/3 |

                          истина ® y = x)}

Правило в круглых скобках эквивалентно записи:

IF x делится на 2 THEN y = x/2 ELSE

IF x делится на 3 THEN y = x/3 ELSE y = x

        3.2.2 Рекурсивные функции

Рекурсивная функция - это функция, использующая в своём определение саму себя. Рекурсивные правила могут быть использованы для описания сложных функций, когда эти функции трудно определить иначе. Например, пусть G – граф, который является моделью железнодорожной сети, связывающей  несколько городов, а C(x, y) - предикат, определяющий условие существования железнодорожной связи между любыми двумя городами:

G = {(x, y) |  поезд идёт из x и y}

С(x, y) = путь из x в y имеется

Тогда предикатная функции С может быть определена рекурсивно так:

C = {((x, y), w) | (x и y - города), w= C(x, y)}, где

С(x, y) = ((x, y) Î G ® w = истина | $z ((x, z)ÎG L C(z, y)) ® w = истина | истина ® w = ложь )

Это означает, что C(x, y) принимает значение истина в том случае, если либо есть прямая связь из x в y, либо возможно её установить через некоторый город z, в противном случае C(x, y) принимает значение ложь.

Заметим, что любое условное правило, определяющее функцию, можно записать как логическое высказывание

C(x, y) =((x, y)ÎG) V ($z ((x, z)ÎG L C(z, y))).

3.2.3  Функция и операция присваивания

 Проектировануя программы,  мы будем рассматривать оператор присваивания, как функцию, которая управляет изменением состояниями данных, содержащихся в проектируемой  программе. Область определения функции соответствует исходному состоянию данных, которые с помощью оператора присваивания преобразуются в результирующее состояние данных. Например, в программе с полем данных x, y, z присваивание  x := y  будет соответствовать функции присваивания, т.е. множеству упорядоченных пар, которые можно представить так :