Редукційне програмування функцій, заданих операціями мультиплікування

Під функцією, заданою операцією мультипліцування, розуміємо функцію, яка визначається рівністю:

(1)

де – довільна функція дійсних змінних та натуральної змінної .

Неважко побачити, що операції підсумовування і мультиплікування можуть здобуватись одна з одної відповідною заміною операцій + на . Звідси випливає, що все викладене вище стосовно функцій, які задаються операціями підсумовування, можна легко перенести на випадок функцій, які задаються операціями мультипліцування, замінивши всюди "+" на . Але не будемо обмежуватися лише цією заміною. Дещо змінимо також і систему рекурентних співвідношень, яка лежить в основі характеристичної властивості функції, що програмується. Подивимося, яких змін зазнає при цьому як сам процес програмування, так і ті схеми програм, які є його результатом.

Введемо до розгляду іменні функції, які використовуються у процесі композиційного конструювання коректних програм обчислення функції (1). Нехай

– D -іменна -функція, яка іменній множині зіставляє значення ;

– D -іменна -функція, яка іменній множині зіставляє значення ;

- D -іменний предикат, який іменній множині зіставляє значення .

Використовуючи ці функції, можна сконструювати коректні програми обчислення (1). Покажемо, що має місце таке твердження.

Теорема 1. Для обчислення функції (1) в елементарній програмній логіці виводиться коректна програма з оракулами (схема програм), що має такий вигляд

І:= 1; S:= ;

while do (S:=S ;I:=I+1) (2)

Доведення теореми проведемо шляхом безпосередньої побудови методом редукцій виводу в елементарній програмній логіці програми з оракулами (2), користуючись композиційною технологією програмування.

За характеристичну візьмемо таку властивість функції (1): її значення збігається із значенням такого члена першої із системи двох послідовностей, визначеної системою двох рекурентних співвідношень першого порядку

(3)

при j>0 та початкових значеннях , для якого предикат приймає значення false коли , значення true, коли .

Згідно до композиційної технології програмування, знайдемо спочатку функціональну структуру програми. Аналіз характеристичної властивості функції (1) показує, що функціональною структурою може бути (D,W)-іменна функція , яка іменній множині зіставляє іменну множину , де

таку, що іменний предикат іменній множині зіставляє false, коли , та значення true, коли .

Композиційна структура програми, в розробленні якої полягає другий етап композиційного програмування, здобувається розкладанням функції, яка задає функціональну структуру програми, на більш прості функції за допомогою відповідних композицій. За останні оберемо композиції структурного програмування, до яких належать аплікація, розгалуження та циклування.

Щоб розкласти функцію F, яка задає функціональну структуру програми, за допомогою обраних композицій, продовжимо аналіз характеристичної властивості функції (1). Неважко зрозуміти, що при розкладанні функції F має бути використана композиція типу циклування, наприклад, while_do. Але застосувати цю композицію зразу на першому етапі розкладання функції F неможливо, бо як і раніше, знайти редукцію цієї функції природним шляхом не вдається. Тому спробуємо, як це завжди роблять у таких випадках, розкласти спочатку функцію F, використовуючи композицію аплікації. З цією метою розглянемо функцію , де , такий член послідовності, а , , що предикат приймає значення false, коли та значення true, коли . Ця послідовність є першою в системі двох послідовностей, визначеній системою двох рекурентних співвідношень першого порядку

(4)

для та початковими значеннями .

Легко побачити, що при та система послідовностей, яка визначається системою рекурентних співвідношень (4), збігається з системою послідовностей, яка визначається системою рекурентних співвідношень (3) при вказаних початкових значеннях. Отже, при та для будь-яких припустимих значень значення функції збігається зі значенням функції :

= .

Введемо до розгляду (D,W)-іменну функцію , яка іменній множині

(5)

зіставляє іменну множину

, (6)

Тоді, зважаючи на сказане раніше, функцію F можна записати у вигляді:

(7)

Якщо для функції знайдеться редукція , то вона може бути представлена у вигляді: while P do , де Р – придатний предикат.

Покажемо, що (D,W)-іменна функція

, є редукцією функції . Для цього пересвідчимось, що виконується визначальна властивість редукції: .

Нехай задана іменна множина (5). Її образ відносно функції є

. (8)

Але згідно з означенням функції ,

Отже іменна множина (8), на яку функцією перетворюються іменна множина (5), збігається з іменною множиною (6), на яку та ж сама множина (5) перетворюється функцією

Таким чином, функція дійсно є редукцією функції . Тоді останню можна зобразити у вигляді:

while P do ().

Легко зрозуміти, що за Р можна обрати предикат . Це випливає з характеристичної властивості функції .

Беручи до уваги, що функція F, яка нас цікавить, зображувана у вигляді (7), можна зробити останній крок її розкладання, здобувши композиційну структуру цієї функції

while do .

Ця композиційна структура, очевидно, являє собою програму з оракулами (2), що обчислює функцію (1). Безпосередньо з побудови програми випливає її коректність. Теорему доведено.

Нехай – D -іменна -функція, яка іменній множині зіставляє значення .

Тоді аналогічно теоремі 1 доводиться наступне твердження.

Теорема 2. Для обчислення функції

, де ,

в елементарній програмній логіці виводиться коректна програма з оракулами (схема програм), що має вигляд

while do

Нехай функція визначається рівністю

(9)

де та – такі функції дшйсних аргументів та натуральних значень, що для всіх .

Нехай далі , та D -іменні -функції, які іменній множині зіставляють значення , та відповідно.

Нехай нарешті, - D -іменний предикат, який іменній множині зіставляє значення . Тоді має місце таке твердження.

Теорема 3. Для обчислення функції, яка визначається рівністю (9) в елементарній програмній логіці виводиться коректна програма оракулами (схема програм), що має такий вигляд

; +1;

while do (.

Доведення теореми аналогічно доведенню теореми 1.

За аналогією з теоремою 1 можна довести також наступне твердження.

Теорема 4. Для обчислення функції (1) в елементарній програмній логіці виводиться коректна програма з оракулами (схема програм), що має вигляд

S:= ; І:= 1;

repeat S:=S ;I:=I+1 until

Теореми 1-4 дозволяють діставати коректні програми обчислення різних скінчених добутків шляхом заміни у відповідній схемі програм довільних функцій, що до неї входять, відпьвідними конкретними функціями. Здобуті при цьому програми є коректними за способом своєї побудови.