34773

Edited by Foxit PDF Editor

b) xQy <=żd(x,y) = 1, są relacjami równoważności?

Zadanie 10. Dany jest zbiór L wszystkich słów utworzonych z liter łacińskich. Czy następujące relacje zdefiniowane dla słów a, b € L:

(?) a F b <=> a i b mają tę samą długość,

b) a Q b 4=> a i b rozpoczynają się od tego samego znaku,

c) u R b o a i b są zbudowane z tych samych znaków,

d) a S b <=» a i b różnią się co najwyżej jednym znakiem, są relacjami równoważności?

Zadanie 11. * Dla relacji występujących w zadaniach 8-10., będącymi relacjami równoważności, wskaż klasę abstrakcji wybranego przez siebie obiektu.

Zadanie 12. Rozpatrzmy kwadrat K — (0,1]² i relację porządku leksykograficznego na K. Wyznacz dla p =

- (0.1,0.7) € K i q = (02,0.5) € K:

(?) zbiór elementów większych od p,

b) zbiór elementów mniejszych od p,

c) zbiór elementów większych od p i mniejszych od q.

Zadanie 13. Wykonaj polecenia a), b) z poprzedniego zadania dla relacji porządku produktowego na kwadracie K. Pónadto wyznacz

(?) zbiór elementów porównywalnych z p,

b) zbiór elementów nieporównywalnych z p,

c) przykładowy element większy od p i od q.

Zadanie 14. Dany jest zbiór L wszystkich słów utworzonych z liter łacińskich. Czy następujące relacje zdefiniowane dla słów a, b € L:

(?) aPb^a jest słowem nie krótszym, niż b,

b) a Q b 4=ż a jest słowem krótszym, niż b,

c) aRb^ wszystkie litery słowa a występują w alfabecie nie wcześniej, niż wszystkie litery słowa b,

if) a S b <=> na każdym miejscu litera słowa a jest wcześniejsza w alfabecie, niż litera w tym samym miejscu słowa b,

są relacjami porządkującymi?

Zadanie 15. * Uzasadnij, że następujące funkcje opisane w notatkach z wykładu:

(?) d_c(p, q) przypisująca parze punktów płaszczyzny odległość typu centrum,

b) dn(p, q) przypisująca parze słów n-literowych ich odległość Hamminga,

c) d,( A, B) przypisująca parze podzbiorów skończonego zbioru X liczbę elementów ich różnicy symetrycznej są metrykami.

Zadanie 16. Znajdź, odległość między obiektami p i q w następujących przypadkach:

(?) p = (3,4), q = (4,3), metryka euklidesowa na płaszczyźnie,

b) p = (3,4), q = (4,3), metryka centrum na płaszczyźnie,

c) P = „klasa", q = „kryza", metryka Hamminga dla słów pięcioliterowych,

(/) p = { a, b, c, f}, q — {c, d, e, f}, metryka Steinhausa określona dla podzbiorów zbioru X = { a, b, c, d, e, f, g, h}.

Zadanie 17. * Jak wygląda w metryce d zbiór {x : d(p, x) = r} (sfera o środku p i promieniu r)?

(?) d : odległość na prostej liczbowej, p = 1, r =

b) d : odległość centrum od punktu (0,0) na płaszczyźnie, p = (0, i), r = 1,

c) d : odległość Hamminga w przestrzeni słów 4-literowych składających się z liter „a", „b", „c", p = „abac", r = 1.

Czy w każdej z tych metryk istnieją sfery o dowolnych promieniach?