1673068209

Rozważmy funkcje częściowe / : D -* N, gdzie (2n \ n e N} ę D. Czy istnieje wśród nich najmniejsza funkcja?

Intuicja: Jeżeli zbiór takich funkcji jest niepusty, to zawsze będzie w nim istnieć najmniejsza funkcja.

- zbiór funkcji częściowych z relacją zawierania.

f - A « - /    ^lł    gdy n =    0

^J    {    2nx(2n-l)x/(2n-2),    w p.p.

.    /.    . fi,    gdy n = 0 \ ,

f~\ ⁹( 2nx(2n-l)x/(2n-2), w p.p. J ^

Funkcja / spełnia równość (*) wtw gdy jest punktem stałym operatora:

_ z v / \ f    1,    gdy n = 0

$(9)(n) “ |    2n x    (2n -1) x /(2n - 2),    w p.p.

Chcemy pokazać, że istnieje najmniejszy punkt stały tego operatora.

9.2.2 Powtórka z logiki

•    Jeżeli {X, <) jest kratą zupełną, a $ : X -* X jest funkcją monofoniczną, to $ posiada najmniejszy punkt stały.

•    Jeżeli (X, <) jest porządkiem zupełnym, $ : X -* X jest ciągła, to $ ma najmniejszy punkt stały a₀ i a₀ = V {/ⁿ(l)}-

Fakt. (N^sN,ę) jest porządkiem zupełnym, zaś operator $ jest ciągły. Zatem $ posiada najmniejszy punkt stały.

Definicja.

7T,	9(ir) = F
/(Mir)).	w p.p.
TT)	gdy g(7r) = F
/(Mn)).	w p.p.

Fakt. (N^sN,ę) jest porządkiem zupełnym, zaś operator $ jest ciągły. Z twierdzenia o punkcie stałym istnieje funkcja spełniająca równość (*).

[■]_: p -*■ (n -*■ n)

10 Wykład 08.04.2008

10.1 Wstęp

Omówimy sobie inne sposoby zadawania znaczenia (denotacji) języków programowania.

Dana Scott (ok. 1965) - Teoria dziedzin (Algol 60).

Spróbujmy przeprowadzić sobie rozumowanie (zamiast „zaglądać” do świata i stwierdzać, czy coś jest prawdziwe, czy nie). Zbudujmy sobie zatem system wnioskowania¹.

Definicja. System wnioskowania to zbiór aksjomatów oraz zbiór reguł wnioskowania. Najstarszym systemem wnioskowania jest System Hilbertowski.

13

1

siedzimy sobie w pustelni i myślimy...