Тема 3. Рекурсія та найменша нерухома точка. Неперервність операторів

Озн. ω-областю називаємо повну, частково впорядковану множину з мінімальним елементом.

Озн. Ланцюгом будемо називати довільну послідовність елементів {d₀, d₁, …} ω-області, що задовольняють умові : d₀ ≤ d₁ ≤… , де ≤ - відношення часткового порядку на ω-області.

Озн. Відображення φ : неперервне, якщо для ланцюга d₀ ≤ d₁ ≤… з ω-області D виконується

Лема : Нехай φ – n - вимірне відображення : φ : , де D - ω-область. φ – неперервне відображення, тоді і тільки тоді, коли φ – неперервне відносно кожного зі своїх аргументів.

Завдання 3.1. Довести неперервність оператора IF(p, f, g), де f і g неперервні.

Розв’язок.

Доведемо неперервність IF(p, f, g) за аргументом f. Візьмемо довільний ланцюг f₀≤ f₁≤ … . Доведемо рівність : . Маємо

Враховуючи неперервність і те, що f_i утворює ланцюг маємо :

Аналогічно доводиться неперервність IF(p, f, g)відносно аргументу g.

Доведемо тепер неперервність IF(p, f, g)відносно аргументу p. Візьмемо довільний ланцюг p₀≤ p₁≤ … . Доведемо рівність : .

Використовуємо неперервність p_і і те, що p_і утворюють ланцюг, покладемо k=max(k₁,k₂). Маємо:

Отже неперервність відносно аргументів доведеною Отже IF(p, f, g)–неперервна функція своїх аргументів.

Завдання 3.2. Довести неперервність оператора , де f і g неперервні.

Розв’язок.

Для того, щоб показати неперервність оператора F, нам потрібно довести його неперервність по f і g:

Доведемо 1) – неперервність по f:

а)

б)

Аналогічно доводиться для 2).

Тема 4. Натуральна семантика

Завдання 4.1. Нехай Program(a,b) – програма знаходження результату ділення a на b – res та залишку ділення ost (див. завдання 1.2). Обчислити за натуральною семантикою результат застосування програми Program(a,b) до даного .

Розв’язок.

Текст програми:

Program(a,b) =

Begin

rez:= 0;

k:= 0;

if (a = 0) then skip else

if (a < b) then skip else

while k <= a – b do

begin

res:= res+1;

k:= k+b

end;

ost:= a – k

End

Спочатку введемо скорочення для фрагментів програми:

Program(a,b) = Begin res:=0; k:=0; if (a=0) then skip else if (a<b) then skip else while k<=a-b do begin res:=res+1; k:=k+b end; ost:=a-k End	P₁ = res:=0; k:=0; if (a=0) then skip else if (a<b) then skip else while k<=a-b do begin res:=res+1; k:=k+b end; ost:=a-k	P₂ = k:=0; if (a=0) then skip else if (a<b) then skip else while k<=a-b do begin res:=res+1; k:=k+b end; ost:=a-k
P₃ = if (a=0) then skip else if (a<b) then skip else while k<=a-b do begin res:=res+1; k:=k+b end; ost:=a-k	P₄ = if (a<b) then skip else while k<=a-b do begin res:=res+1; k:=k+b end; ost:=a-k

Нехай = , тоді:

Результат:

Завдання 4.2. Нехай GCD(M,N) – програма обчислення найбільшого спільного дільника за алгоритмом Евкліда (див. завдання 1.1).

Обчислити за натуральною семантикою результат застосування програми GCD(M,N) до даного [M->19,N->8].

Розв’язок.

GCD(M,N)=

begin

while M N do

if M>N then M:=M-N else N:=N-M

end

Застосуємо програму до вхідного даного та обчислимо за натуральною семантикою результат станом [M->19,N->8].

Початковий стан:

Композиційний семантичний терм програми:

Отже,

(1.1):

(1.2):

(2):

(2.1):

(2.2):

(3):

(3.1):

(3.2):

(4):

(4.1):

(4.2):

(5):

(5.1):

(5.2):

(6):

(6.1):

(6.2):

(7):

Результат:

Завдання 4.3. Нехай Sum_fac(n) – програма обчислення суми факторіалів до вхідного n≥0 (включно) через множення і додавання.

Обчислити за натуральною семантикою результат застосування програми Sum_fac(n) до даного [n->2].

Розв’язок.

Sum_fac(n) =

Begin

i:=0;

fac:=1;

res:=1;

while i ≠ n

Begin

i:=i+1;

fac:= fac*i;

res:=res+fac

End

Введемо позначення:

Sum_fac(n) = i:=0; fac:=1; res:=1; while i ≠ n begin i:=i+1; fac:= fac*i; res:=res+fac end	P = i:=0; fac:=1; res:=1; while i ≠ n begin i:=i+1; fac:= fac*i; res:=res+fac end	P₁= fac:=1; res:=1; while i ≠ n begin i:=i+1; fac:= fac*i; res:=res+fac end
P₂= res:=1; while i ≠ n begin i:=i+1; fac:= fac*i; res:=res+fac end	W = while i ≠ n begin i:=i+1; fac:= fac*i; res:=res+fac end

Обчислення за натуральною семантикою: