Из определений следует, что при

Задача 7.1.
Определите (по аналогии с п. (ж)) определения 7.5 семантику для программ вида
?= пока x < y делай ?1 все.
Задача 7.2.Построить структурированные программы, вычисляющие в z следующие функции, и доказать их корректность:

f{?}(x,y)= x*y;
ffact(x)= x!;
f-1(x)= x
1, где 0
1 = 0 и (x+1)
1 = x;
f-(x,y)= x
y, где x
y = x-y, если x
y и x
y=0, если x < y;
fsqr(x)= [sqrt x];
fexp(x)= 2x;
flog(x)= [log2x];
f/(x,y)= [x/y].

Задача 7.3.
Пусть ? - структурированная программа и |Var?| = m. Из определений следует, что при различной фиксации входных переменных и выходной переменной программа может вычислять различные функции.

Каково максимальное число функций от n
m переменных, которое может вычислять ?? Сколько всего разных функций может вычислить ??
Постройте программу ?(m,n), которая вычисляет максимальное число различных функций от n
m переменных.
Постройте программу ?(m) с |Var?| = m, которая для каждого n
m вычисляет максимальное число различных функций от n переменных.

Задача 7.4.Построить структурированные программы, вычисляющие в z следующие функции:

Задача 7.5.
Пусть структурированная программа ? вычисляет в переменной y некоторую всюду определенную взаимно однозначную функцию f(x), область значений которой совпадает с множеством всех натуральных чисел N. Пусть Var?={x, y, z1,… , zm}. Постройте структурированную программу, которая вычисляет обратную функцию f-1(x) = { z | f(z)=x}.
Задача 7.6. Пусть F(x) задана соотношениями F(0)=1, F(1)=1, F(x+2)= F(x)+F(x+1) (элементы последовательности F(x) называются числами Фибоначчи). Постройте структурированную программу, которая вычисляет функцию F(x).