Лекции по СЯП (987656), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Утверждение 20. Пусть t(x,F) – терм, задающий суперпозицию монотонных функций. Тогда оператор τ, τ[F](x) = t(x,F), непрерывен.

Доказательство. Мы используем индукцию по структуре термов.

База индукции. Простейшими термами являются h(x) и F(x), где h – монотонная функция. В первом случае имеем τ[F](x) = h(x), т.е.

τ[F] = h, во втором случае – τ[F](x) = F(x), т.е. τ[F] = F. В обоих случаях оператор τ непрерывен.

Индуктивный переход. Опять имеем два случая:

А) t(x,F) = f (t₁(x,F), t₂(x,F),…, t_m(x,F));

B) t(x,F) = F(t₁(x,F), t₂(x,F),…, t_m(x,F)) .

Нужно доказать: если все операторы τ_j (1 j m),

τ_j [F](x) = t_j(x,F)

непрерывны, то оператор τ,

τ[F](x) = t(x,F)

также непрерывен.

Замечание. Мы здесь докажем индуктивный переход только для случая А. Случай В доказывается аналогично.

Сначала доказываем, что оператор τ монотонен:

g h τ_j [g] τ_j [h] для всех 1 j m (так как τ_j – непрерывен

и, значит, монотонен)

τ_j [g](x) τ_j [h](x) для всех х А и всех 1 j m

t_j (x, g) t_j (x, h) для всех х А и всех 1 j m

f (t₁ (x, g), t₂ (x, g),…, t_j (x, g))

f (t₁ (x, g), t₂ (x, g),…, t_j (x, g)) для всех х А (так как

функция f монотонна)

t(x, g) t(x, h) для всех х А

τ[g](x) τ[h](x) для всех х А

τ[g] τ[h].

Докажем теперь, что оператор τ непрерывен, т.е. для любой цепи f₀ f₁ f₂ … f_n … имеет место

τ[sup{f_n | n N} = sup{τ[f_n] | n N}.

Это соотношение эквивалентно двум соотношениям

τ[sup{f_n | n N} sup{τ[f_n] | n N}, (1)

sup{τ[f_n] | n N} τ[sup{f_n | n N}. (2)

Соотношение (1) доказывается проще:

имеем f_k sup{f_n | n N} для всех k N и

f_k sup{f_n | n N} для всех k N

τ[f_k] τ[sup{f_n | n N}] для всех k N (так как оператор τ

монотонен)

sup{τ[f_k] | k A} τ[sup{f_n | n N}]

sup{τ[f_n] | n A} τ[sup{f_n | n N}].

Доказываем (2):

τ[sup{f_n | n N}(x) = t(x, sup{f_n | n N})

= f (t₁(x, sup{f_n | n N}), …, t_m(x, sup{f_n | n N}F))

= f (τ₁[sup{f_n | n N}](x), …, f(τ_m[sup{f_n | n N}](x))

= f (sup{τ₁[f_n] | n N}(x), …, sup{τ_m[f_n] | n N}(x))

(так как все τ_j непрерывны)

= f (sup{τ₁[f_n](х) | n N}, …, sup{τ_m[f_n](х) | n N}).

Благодаря монотонности τ_j имеем цепь

τ_j [f₀](х) τ_j [f₁](х) τ_j [f₂](х) … τ_j [f_n](х) … .

Так как все члены этой цепи принадлежат множеству. В⁺, которое имеет тривиальный порядок, то существует индекс k(j) такой, что

τ_j [f₀](х) = τ_j [f₁](х) = τ_j [f₂](х) =…= τ_j [f_k(j)](х) = _┴

< τ_j [f_k(j)+1](х) = τ_j [f_k(j)+2](х) = τ_j [f_k(j)+2](х) = …

Возьмем k = max{k(j) | 1 j m}. Тогда для всех n k и всех 1 j m имеем:

τ_j [f_n](х) = τ_j [f_n+1](х) = τ_j [f_n+2](х) =…

и следовательно, sup{τ_j [f_n](х) | n N} = τ_j [f_k](х). Поэтому

f (sup{τ₁[f_n](х) | n N},…, sup{τ_m[f_n](х) | n N})

= f (τ₁[f_k](х), τ₂[f_k](х), …, τ_m[f_n](х))

= f (t₁(f_k, х), t₂(f_k, х), …, t_m(f_n, х))

= τ(f_k, х) = τ[f_k]( х) sup{τ [f_n]( х) | n N}.

Таким образом,

τ[sup{f_n | n N}(x) sup{τ [f_n]( х) | n N}.

Ч.т.д.

3.1. Неподвижные точки непрерывных операторов

Если оператор τ непрерывен, то для нахождения его неподвижной точки можно применить теорему Клини, согласно которой неподвижная точка вычисляется как супремум sup{τⁿ [] | n N}.

Примеры. Рассмотрим функционал τ : F(N⁺,N⁺) F(N⁺,N⁺), определяемый как

τ[F](x) = if x = 0 then 1 else x•F(x–1).

Замечание. Через _┴ мы обозначаем не только неопределенное значение, но и всюду неопределенную функцию: _┴(х) =_┴.

Имеем:

τ[_┴](x) = if x=0 then 1 else x• _┴(х–1) = if x=0 then 1 else _┴

τ²[_┴](х) = τ[τ[_┴]](х) = if x=0 then 1 else x• τ[_┴](х–1)

= if x=0 then 1 else x• (if x–1=0 then 1 else _┴)

= if x=0 then 1 else x• (if x=1 then 1 else _┴)

= if x=0 then 1 else (if x=1 then x else _┴)

= if x<2 then 1 else _┴ = if x<2 then x! else _┴.

Докажем индукцией, что 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

τ^k[_┴](х) = if x<k then x! else _┴ .

Если это верно, то

τ^k+1[_┴](х) = ττ^k[_┴](х) = τ[τ^k[_┴]](х)

= if x=0 then 1 else х• τ^k[_┴](х–1)

= if x=0 then 1 else х• (if x –1<k then (x–1)! else _┴)

= if x=0 then 1 else (if x<k+1 then x! else _┴)

= if x<k+1 then x! else _┴ .

Ясно, что τ^k[_┴] τ^k+1[_┴]. Следовательно,

sup{τ^k[_┴] | k = 0,1,2,…}(x) = x!

4. СЕМАНТИКА РЕКУРСИВНЫХ ПРОГРАММ

Рассмотрим рекурсивную программу

Q: F(x,y) <= if x=y then y+1 else F(x, F(x–1, y+1)).

С этой программой связан оператор τ_Q, преобразующий множество двуместных функций в себя. В данном случае этим множеством является Fun(Z Z, Z). Оператор τ_Q сопоставляет каждой функции f Fun(Z Z, Z) функцию τ_Q[f] F(Z Z, Z) :

τ_Q[f](x,y) if x=y then y+1 else F(x, F(x–1, y+1)).

Пример. Возьмем функцию f (x,y) x+y. Тогда

τ_Р[f](x,y) if x=y then y+1 else f (x, f (x–1, y+1))

if x=y then y+1 else x+(x–1+,y+1))

if x=y then y+1 else 2x+y.

В программе Q буква F обозначает функциональную переменную, т.е. переменную, принимающую значения в множестве функций F(Z Z, Z).

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

P: F(x₁, x₂,.., x_n) <= t(x₁, x₂,.., x_n F),

где t(x₁, x₂,.., x_n F) – некоторый функциональный терм, составленный из имен базовых функций и имени F функциональной переменной.

Таким образом, имеется некоторый набор базовых функций, включающий функцию if-then-else.

Замечание. Терм t(x₁, x₂,.., x_n F) сокращенно записываем как t(x, F).

Терм t(x,F) задает функцию, являющуюся суперпозицией тех функций, имена которых входят в этот терм. Кроме того, терм включает функциональную переменную, вместо которой можно подставлять имя произвольной функции суперпозиция базовых функций. Подставив вместо F имя f какой-либо конкретной функции, мы получаем терм, определяющий некоторую функцию, которая является суперпозицией входящих в терм функций и функции f.

С программой Р ассоциирован оператор τ_P:

τ_P[f](x) = t(x,F).

Утверждение 19. Следующие 3 функции f₁, f₂ и f₃ являются неподвижными точками оператора τ_Q , ассоциированного с программой Q: F(x,y) <= if x=y then y+1 else F(x, F(x–1, y+1)):

f₁(x,y): if x=y then y+1 else x+1,

f₂(x,y): if (x 1) (х=у) then x+1 else y –1,

f₃(x,y): if (x y) (x–y четно) then x+1 else _┴

Доказательство. Функцию if X then Y else Z графически можно представить так:

if X then Y else Z if X then Y else Z

X X или X

Y Z Y Z

В частности, f₁(x,y): if x=y then y+1 else x+1 представляется так:

f₁(x,y): if x=y then y+1 else x+1

x=y

y+1 x+1

Для выражения τ[f₁](x,y) имеем следующее дерево:

τ[f₁](x,y): if x=y then y+1 else f₁(x, f₁(x–1,y+1))

х=у

y+1 f₁(x, f₁(x–1,y+1))

x= f₁(x–1,y+1)

f₁(x–1,y+1)+1= x+1 x+1

Ясно, что это дерево эквивалентно дереву

f₁(x,y): if x=y then y+1 else x+1

х=у

у+1 х+1

Это показывает, что τ[f₁](x,y) = f₁(x,y). Следовательно, τ[f₁] = f₁.

2 ) f₂(x,y): if (x 1) (х = у) then x+1 else y –1

x 1

x+1 y–1

τ[f₂](x,y): if x=y then y+1 else f₂(x, f₂(x–1,y+1))

x=y

у+1= х+1 f₁(x, f₁(x–1,y+1))

x 1

х<1

x+1 f₁(x–1,y+1))–1

х – 1 1 (x 2) x<2

(x–1)–1 = x–2 (y+1)–1–1= y–1

3)Эквивалентность двух деревьев

f₃(x,y): if (x y) (x–y четно) then x+1 else _┴

(x y) (x–y четно)

x+1 _┴

τ[f₃](x,y): if x=y then y+1 else f₃(x, f₃(x–1,y+1))

x=y

f₂(x, f₂(x–1,y+1))

y+1 = x+1

(x у) (х– f₃(x–1,y+1) четно)

х+1 _┴

следует из того, что утверждение «(if x – y четно then 1 else _┴ ) четно» ложно. В самом деле, если х – у четно, то это утверждение переходит в утверждение «1 четно»; если х – у нечетно, то оно переходит в утверждение «_┴ четно».

Ч.т.д.

Рассмотрим вычисления по программе Q (в общем случае).

А)

F(a,a)

if a=a then a+1 else F(a,F(a–1,a+1))

a+1

Б) Пусть a<b. Тогда имеем:

F(a,b)

if a=b then b+1 else F(a,F(a–1,b+1))

F(a,F(a–1,b+1))

F(a, if a–1=b+1 then b+1+1 else F(a–1,F(a–1–1,b+1+1)))

F(a,F(a–1,F(a–2,b+2)))

F(a,F(a–1, if a–2=b+2 then b+2+1 else F(a–2,F(a–2–1,b+2+1))))

F(a,F(a–1,F(a–2,F(a–3,b+3))))

:

:

Следовательно, F(a,b) = _┴ , если a<b.

С) Пусть a b. Положим а = b+k.

F(b+k,b)

if b+k=b then b+k+1 else F(b+k,F(b+k–1,b+1))

F(b+k,F(b+k–1,b+1))

F(b+k, if b+k–1=b+1 then b+1+1 else F(b+k–1,F(b+k–1–1,b+1+1)).

Если a+k–2>a, то

F(b+k,F(b+k–1,F(b+k–2,b+2)).

F(b+k,F(b+k–1, if b+k–2=b+2 then b+2+1

else F(b+k–2,F(b+k–2–1,b+2+1))))

Если b+k–4>b, то

F(b+k,F(b+k–1,F(b+k–2,F(b+k–3,b+3))))

F(b+k,F(b+k–1,F(b+k–2, if b+k–3=b+3 then b+3+1

else F(b+k–3,F(b+k–3–1, b+3+1)))))

Если b+k–6=b, то

F(b+k,F(b+k–1,F(b+k–2,F(b+k–3,F(b+k–4,b+4))))) (1)

:

:

Предположим, что k четно, например, k = 8. Тогда терм (1) будет таким

Характеристики

Список файлов лекций