[1/02] Dla każdego z podanych przypadków relacji R Í A2 sprawdź czy jest ona:
(i) relacją typu równoważności (jeśli tak to ile wyznacza klas abstrakcji)
(ii) porządkiem częściowym (jeśli tak i jeśli A jest skończone to jaka jest wysokość (A, R)?)
(iii) quasi-porządkiem (jeśli tak i jeśli A jest skończone to jaka jest wysokość (A, R)?)
(iv) porządkiem liniowym
w zbiorze A.
(a) A = {1, 2,..., 30}, xRy Û "cÎA[min{x, y} < c £ max{x, y} ® $dÎA(1 < d < c Ù d | c)]
(b) A = {1,2,..., 1997}, xRy Û x < y – 10
(c) A = {1,2,..., 1997}, xRy Û x < y + 10
(d) A = {1,2,...,10}2, (a, b)R(c, d) Û a | cd Ù b | cd
(e) A = N, xRy Û y = x2
(f) A = N, xRy Û x | y Ú y | x
(g) A = N, xRy Û x < y – 1
(h) A = N, xRy Û 125 | (x – y)2
(i) A jest zbiorem wszystkich funkcji N ® R, fRg Û "nÎN(f(n) ³ g(n))
(j) A jest zbiorem wszystkich funkcji N ® R, fRg Û $nÎN(f(n) ³ g(n))
(k) A jest zbiorem wszystkich funkcji N ® R, fRg Û $n,mÎN(f(n) ³ g(m))
(l) A jest zbiorem wszystkich funkcji N ® R, fRg Û $mÎN("nÎN (n ³ m ® f(n) ³ g(n)))
[2/02] Czy dla każdego skończonego zbioru częściowo uporządkowanego (A, R) istnieje zbiór B Í A2 taki, że R È B jest liniowym porządkiem w A?
[3/02] Udowodnij, że jeśli (A, R) oraz (A, S) są zbiorami częściowo uporządkowanymi to (A, R Ç S) jest także zbiorem częściowo uporządkowanym.
[4/02] Przedstaw diagram Hassego dla zbioru częściowo uporządkowanego (A, R), gdzie R = {(x, y) : x | y}, A = {1, 2,..., 15}. Jak jest wysokość ({1,2,..., 1997}, R)?
[5/02] Czy dla każdego skończonego zbioru częściowo uporządkowanego (A, R) istnieje podział zbioru A na podzbiory P1, P2,... takie, że można narysować diagram Hassego tak, aby wszystkie elementy każdego podzbioru Pi znajdowały się na tym samym poziomie i aby co najmniej jeden podzbiór Pi zawierał liczbę elementów równą szerokości (A, R)?
[6/02] Czy dla każdego skończonego zbioru częściowo uporządkowanego (A, R) istnieje podział zbioru A na podzbiory P1, P2,... takie, że można narysować diagram Hassego tak, aby wszystkie elementy każdego podzbioru Pi znajdowały się na tym samym poziomie i aby dla dowolnych dwóch elementów x, y Î A, takich, że x nakrywa y, zachodziła implikacja x Î Pi ® y Î Pi–1.
[7/02] Podaj przykład zbioru częściowo uporządkowanego, w którym jest nieskończenie długi łańcuch i nieskończenie długi antyłańcuch.
[8/02] Z2 (Z - zbiór liczb całkowitych) można interpretować jako nieskończoną szachownicę indeksowaną parami liczb całkowitych. Określamy relację RF Í Z2 ´ Z2 w ten sposób, że (a, b) RF (c, d) wtwg z pola (a, b) można się dostać na pole (c, d) figurą szachową F w skończonej, dodatniej liczbie ruchów. Udowodnij, że dla każdej figury szachowej F Î {wieża, skoczek, goniec, hetman, król} RF jest relacją typu równoważności. Ile klas abstrakcji w Z2 wyznacza każda z 5 relacji RF ?
[9/02] Rozważamy zbiór A = {2n : n Î N}È{3} uporządkowany relacją podzielności. Wypisz zbiór elementów minimalnych i maksymalnych w A oraz narysuj diagram Hassego.
[10/02] Niech dany będzie dowolny skończony zbiór częściowo uporządkowany. Udowodnij, że istnienie elementu największego jest równoważne istnieniu dokładnie jednego elementu maksymalnego. Podaj przykład pokazujący, że powyższa równoważność nie musi być spełniona gdy zbiór jest nieskończony.
[11/02] W zbiorze bajtów {0,1}8 określono relacje R w ten sposób, że dwa bajty są w relacji, gdy jeden można otrzymać z drugiego przez zamianę dwóch sąsiednich bitów miejscami. Np. 10010001 R 10001001. Czy relacja R jest zwrotna? Czy jest symetryczna? Czy jest przechodnia?
[12/02] Zaznacz w tabeli poniżej, które własności spełniają poszczególne relacje określone w zbiorze liczb naturalnych. Pamiętaj, że 0 Ï N.
sote12