Семантика на програмните езици. Непрекъснати изображения в области на Скот
| Информационни технологии | 2009-12-04 | 65 сваляния |
13.Непрекъснати изображения в области на Скот.
Нека {(ak1 , ak2 ,, akn)} е монотонно растяща редица от елементи на А.Нека а1 е точната горна граница на редицата {ak1 } в А1, а2 е точната горна граница на редицата {ak2} в А2 и т.н., аn e точната горна граница на { akn } в Аn . Тогава (а1 , а2 , ...,аn) е точната горна граница на редицата {(ak1 , ak2 ,, akn)} в А. Едно тотално изображение f на А1 в А2 наричаме непрекъснато ако при всеки избор на монотонно растяща редица a1 }1a2}1... }1aк }1... от елементи на А1, f(ak) е точната горна граница на редицата { f(ak) } в А2 . Компактните оператори от тип (n,r) са точно непрекъснатите изображения на Fn в Fr .Както при операторите непрекъснатитезображения се оказват монотонни.Нека f : А1 А2 . Изображението f е монотонно ако а }1 b следва f(а) }2 f(b).Всяко непрекъснато изображение f на А1 в А2 е монотонно. Нека f и g са елементи на (А1 А2 )Тогава f } g ако при всеки избор на елемент а от А1 е изпълнено неравенството f (а) }2 g(а). При тази наредба елементът Y на (А1 А2 ), определен като Y(а)= 2 , се оказва най-малкият елемент на (А1 ђ А2 ). Непрекъснатоста на Y се проверява непосредствено.Същата проверка показва и че всяко константно изображение на А1 в А2 е непрекъснато. Нека f1} f2}...} fк}... е монотонно растяща редица от елементи на (А1 ђ А2 ). Нека а е фиксиран елемент на А1. От монотонността на редицата {fk } следва че {fk (а)} е монотонно растяща редица от елементи на А2 и следователно тя притежава точна горна граница fk (а) в А2 .Да дефинираме изображението h на А1 в А2 като положим h(а)=f k(а). Изображението h е непрекъснато и h е точната горна граница на редицата {fk }. Нека А1 , А2, А3 са области на Скот. Нека f : А1 А2 и g: А2 А3 .Да образуваме композицията h= g0 f на f и g,като положим h(а)= g(f(а)) за всяко аА1 . Ако f
и g са непрекъснати изображения то и композицията h= g0 f е непрекъснато изображение. Нека a0 }1a1}1... }1aк }1... е монотонно растяща редица от елементи на А1 .Тогава h(aк)= g(f(aк))= g(f(aк))= g(f(aк))= h(aк).Нека f( А1 А2)и g( А1 А3).Образуваме изображението f‡g: А1 А2‡ А3 , като положим f‡g(а)= f(а), g(а).Тогава f‡g(А1 А2‡ А3).Казваме че елементът а на А е минимална неподвижна точка на f ако f(а)=а и всеки път когато f(b)= b имаме а }b. Казваме че а е кваизминимална неподвижна точка на f ако f(а) }а и всеки път когато f(b)}b е изпълнено а}b. Нека f е монотонно изображение на А в А и а е квазиминимална неподвижна точка на f.Тогава а е минимална неподвижна точка на f.Теорема на Кнастер-Тарски:Всяко непрекъснато изображение f на А в А притежава минимална неподвижна точка.Нека f1 ,..., fn са непрекъснати изображения на D съответно в А1,... Аn . Тогава системата(*) притежава минимално решение. Казваме че b1 ,..., bn e квазирешение на системата (*) , ако са в сила неравенствата fi (b 1 ,.., b n) } b i , i=1,,n. Нека b1 ,..., bn e квазирешение на системата (*) , а a1 ,.., an е минимално решение на (*) .Тогава a1 ,.., an = dк } b 1 ,.., b n .
Тагове от реферата: програмнит, семаика, непрекъсна, емент, редиц, монотонно











