8344044625

strona 13

29 września 2008, godzina 17:13

Typy indukcyjne

123.    Udowodnić, żewQv zachodzi wtedy i tylko wtedy, gdy

•    w = e, lub

•    w = aw', v — av', dla pewnych w', v', oraz w' C v', lub

•    w = bw', v = bv', dla pewnych w' ,v', oraz w' C t/.

124.    Niech w C v oznacza, że v = u ■ w, dla pewnego u (porządek sufiksowy). Udowodnić, że dla dowolnego alfabetu A, relacja C jest porządkiem częściowym w A*. Pokazać, że w C. v zachodzi wtedy i tylko wtedy, gdy albo w = v albo v — av', gdzie a € A oraz w C v'.

125.    Suma prosta V © Z może być uważana za typ indukcyjny. Jakie są tu konstruktory i jaka zasada indukcji? A schemat definiowania przez indukcję?

126.    Typ jednostkowy Unit ma tylko jeden element •. Czy Unit można uważać za typ indukcyjny? Skonstruować z niego typy skończone o dowolnej liczbie elementów.

127.    Zdefiniować przez indukcję operację Aw.w^R odwracania słowa (tak aby na przykład (baba)^R = abab). Udowodnić przez indukcję, że (w^R)^R = w, dla dowolnego słowa w.

128.    Zdefiniować przez indukcję następujące operacje na listach:

(a)    Dopisanie liczby n na końcu listy;

(b)    Usunięcie ostatniego elementu listy;

(c)    Odwracanie listy, itp.

129.    Typ wartości logicznych Bool można utożsamiać z sumę prostą Unit©Unit a zatem za typ indukcyjny. Uogólnić tę obserwację na typy skończone o dowolnej liczbie argumentów. Sformułować dla takich typów zasadę indukcji i schemat definiowania przez indukcję.

130.    Skończone drzewa binarne to elementy typu indukcyjnego z jednym konstruktorem dwuargumentowym ^A i jedną stałą o. Sformułować dla tego typu zasadę indukcji i schemat definiowania przez indukcję. Zastosować ten schemat do definiowania takich funkcji jak „lewe poddrzewo drzewa t”, „liczba wierzchołków drzewa t”, „wysokość drzewa t" itd.

131.    Zdefiniować typ indukcyjny skończonych drzew binarnych etykietowanych liczbami naturalnymi, sformułować dla tego typu zasadę indukcji i schemat definiowania przez indukcję. Zdefiniować funkcję „suma etykiet drzewa t".

132.    Pokazać, że w C v zachodzi wtedy i tylko wtedy, gdy w(n) = v(n) dla n < |to|.

Moce zbiorów

133.    Jakiej mocy jest zbiór punktów leżących na powierzchni bocznej stożka?

134.    Jakiej mocy jest podzbiór płaszczyzny ograniczony krzywymi o równaniach y = x² i y = 1 — x²?