X X

П П (JT-oft)

-1п=2

Как и было обещано, формула Вормелла не использует тригонометрических функций. Однако, как указал Вормелл, они появятся вновь, если заменить степени -1, используя соотношение (-1)" =cos7tn.

16.4. Формулы для других сложных функций

Еще раз внимательно посмотрим на то, что сделали Виллане и Вормелл. Ниже постулированы правила, определяющие, что именно мы подразумеваем под классом функций, которые могут быть представлены "формулами" и которые мы назовем "формульными функциями". Здесь х означает сокращение xi, Хг, ..., дгл для любого л s 1. Область значений представляет собой целые числа ... -2, -1, О, 1, 2,....

Константы ... -1, О, 1,... являются формульными функциями.

Функции отображения /[х) = х для i<,iun являются формульными.

Выражения х + у , х-у и ху являются формульными функциями, если таковыми являются д: и у.

Класс формульных функций замкнут по отношению к суперпозиции функций (подстановке), т.е. f[g (х), (x),...,g„ (х)) является формульной функцией, если/ и gi являются таковыми для i=\,...,m.

Ограниченные суммы и произведения

1/(.)и П/()

Представляют собой формульные функции, если а, b и f являются таковыми и а{х}<Ь{х).

Требование ограниченности сумм и произведений сохраняет вычислительный характер формул, т.е. формулы могут быть вычислены подстановкой значений аргументов и проведением конечного числа операций. Причина наличия штриха у символов Z и П поясняется далее в этой главе.

При формировании новых формульных функций с использованием суперпозиции в случае необходимости применяются круглые скобки в соответствии со стандартными соглашениями об их применении.

16.4. ФОРМУЛЫ ДЛЯ ДРУГИХ СЛОЖНЫХ ФУНКЦИЙ 267

Pn=2 + Z{n(m)<n), после вынесения постоянных множителей за знак суммы получаем

Заметим, что деление в приведенный выше список не включено. Однако даже при этом приведенный список нельзя считать минимальным. Конечно, интересно найти минимально необходимый список правил, но не будем останавливаться на этом вопросе в нашей книге.

Определение "формульной функции" близко к определению "элементарной функции", приведенному в [9]. Однако область значений, использованная в [9], представляет собой неотрицательные целые числа (как и в обычной теории рекурсивных функций). Кроме того, в [9] требуется, чтобы границы итерационных сумм и произведений были О и д: -1 (где X - переменная) и допускали пустые диапазоны (в этом случае сумма считается равной О, а произведение - 1).

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

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

В нашем рассмотрении под "предикатом" понимается функция, которая возвращает значение, равное О или 1, в то время как в теории рекурсивных функций предикат представляет собой функцию, которая возвращает значение истинно/ложно, и каждый предикат имеет связанную с ним "характеристическую функцию", которая возвращает значения 0/1. Мы ассоциируем значение 1 с истиной, а О с ложью, как обычно делается в языках программирования и в вычислительных машинах в целом (в плане работы команд и и или). Однако в теории логических и рекурсивных функций встречается и противоположная ассоциация логических и числовых значений.

Приведем ряд примеров формульных функций.

1. = аа , а= одд и т.д.

2. предикат а = Ь:

3. {аФЬ) = \-{а-Ь).

4. Предикат а>Ь:

(«-»); («-*>; ((«-*)-)

(aSb)=S ((«-Ь) = 0=1 П

Теперь можно объяснить, почему не используется соглашение, в соответствии с которым итеративная сумма/произведение принимают при пустом диапазоне суммирования/произведения значения 0/1. Если поступить подобным образом, то можно получить такие "жульничества", как

(а = Ь)= 5 1 И (ab) = YlO.

Предикаты сравнений являются ключом ко всему последующему материалу, поэтому не желательно, чтобы они были основаны на искусственных построениях такого рода.

f V т.(»(Г)Л(Г)) Л

l2.llf{i,x) = Ub{x)a{x) -1+ П /(.

Начиная с этого момента, символы суммы и произведения используются без штриха. Таким образом, все дальнейшие определения функций корректны для любых значений аргументов.

13. л! = J][i. Это определение дает нам л.= 1 для л < О.

В формулах ниже PhQ обозначают предикаты. Ы.{х) = 1-Р{х).

15. P{x)&Q{x) = Pix)Q{x).

16. Р(Г)е(Г) = 1-(1-Р(Г))(1-е(Г)).

17. P{x)®Qix) = {P{x)-Q{x)f.

18. if Р{х) then /(у) else «(г) = Р(Г)/(у) + (1-Р(Г))«(г).

19. а = if лйО then JJa else 0.

Эта формула дает результат О для л < О и 1 для 0°, что в ряде случаев может оказаться некорректным решением.

20. (,п<Ухл)Р(х,у) = Пр(х,у).

21. {m<3xun)P{x,y) = l-fl{l-P{x,y)).

Пустое V истинно, пустое 3 ложно. 16.4. ФОРМУЛЫ ДЛЯ ДРУГИХ СЛОЖНЫХ ФУНКЦИЙ 269

6. {aub) = {ba).

7. (a<b) = {b>a).

8. a = (2(a>0)-l)a.

9. max(a,ft) = (aSb)(a-ft) + ft.

10. rtua{a,b) = {ab)(b-a) + a .

Теперь можно скорректировать итерационные суммы и произведения таким образом, чтобы они давали корректный результат и при пустом диапазоне суммирования или произведения.

Н) ™х(»(г).*(г))

П. f{i,x) = {bix)>a{x)) 2 /()-