Zad02 relacje binarne, AA informatyka - studia, cwiczenia i egzaminy


[DM 02]

[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.

  1. A = {1, 2,..., 30}, xRy ⇔ ∀cA[min{x, y} < c ≤ max{x, y} → ∃dA(1 < d < cd | c)]

  2. A = {1,2,..., 1997}, xRyx < y - 10

  3. A = {1,2,..., 1997}, xRyx < y + 10

  4. A = {1,2,...,10}2, (a, b)R(c, d) ⇔ a | cdb | cd

  5. A = N, xRyy = x2

  6. A = N, xRyx | yy | x

  7. A = N, xRyx < y - 1

  8. A = N, xRy ⇔ 125 | (x - y)2

  9. A jest zbiorem wszystkich funkcji N R, fRg ⇔ ∀nN(f(n) ≥ g(n))

  10. A jest zbiorem wszystkich funkcji N R, fRg ⇔ ∃nN(f(n) ≥ g(n))

  11. A jest zbiorem wszystkich funkcji N R, fRg ⇔ ∃n,mN(f(n) ≥ g(m))

  12. A jest zbiorem wszystkich funkcji N R, fRg ⇔ ∃mN(nN (nmf(n) ≥ g(n)))

[2/02] Czy dla każdego skończonego zbioru częściowo uporządkowanego (A, R) istnieje zbiór BA2 taki, że RB 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, RS) 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, yA, takich, że x nakrywa y, zachodziła implikacja xPiy 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ę RFZ2 × 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 : nN}∪{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.

zwrot­na

syme­tryczna

anty­syme­tryczna

prze­chod­nia

przeciwzwrotna

xRy ⇔ NWD(x, y) > 1

xRy ⇔ NWD(x, y) < 3

xRyx + 2y < 2003

xRy ⇔ 5 | (3x + 2y)

xRy ⇔ 5 | (4x + 3y)

[13/02] Na rysunku przedstawiono diagram Hassego relacji porządku częściowego R ⊆ {a, b, c, d, e, f, g, h, j, k, m, n}2.

0x01 graphic

Wyznacz:

  1. wszystkie elementy większe od b: ......................................................................................................

  2. wszystkie elementy mniejsze od b: ....................................................................................................

  3. wszystkie ograniczenia dolne zbioru {e, j, m}: ........................................................................

  4. wszystkie ograniczenia górne zbioru {k, b}: ..............................................................................

  5. kres dolny zbioru {c, e} (jeśli nie istnieje wpisz #):..............................................................

  6. kres dolny zbioru {e, h} (jeśli nie istnieje wpisz #):.............................................................

  7. wysokość R: ..........................................................................................................................................................

  8. szerokość R: ...........................................................................................................................................................

  9. przykład antyłańcucha o liczbie elementów równej szerokości R: .........................

[14/02] Narysuj diagram Hassego dla relacji R ⊆ {xN : 7 ≤ x ≤ 14} określonej formułą xRyx = y ∨ (x < y ∧ ~(3 | xy)). Wyznacz długość najdłuższego łańcucha oraz najliczniejszego antyłańcucha zbioru częściowo uporządkowanego ({xN : 7 ≤ x ≤ 14}, R).



Wyszukiwarka

Podobne podstrony:
Zad03 relacje binarne-domkniecia, AA informatyka - studia, cwiczenia i egzaminy
DEgz2-2007-rozw, AA informatyka - studia, cwiczenia i egzaminy
DEgz1-2006, AA informatyka - studia, cwiczenia i egzaminy
DEgz1-2007, AA informatyka - studia, cwiczenia i egzaminy
DEgz2-2010 rozw, AA informatyka - studia, cwiczenia i egzaminy
DEgz2-2009 rozw, AA informatyka - studia, cwiczenia i egzaminy
Zad04 zliczanie, AA informatyka - studia, cwiczenia i egzaminy
DEgz2-2005, AA informatyka - studia, cwiczenia i egzaminy
DEgz1-2008 zakres 2007-2008, AA informatyka - studia, cwiczenia i egzaminy
DEgz2-2010, AA informatyka - studia, cwiczenia i egzaminy
Karta Inform MatElem, AA informatyka - studia, cwiczenia i egzaminy
DEgz1-2009, AA informatyka - studia, cwiczenia i egzaminy
DEgz1-2005, AA informatyka - studia, cwiczenia i egzaminy
DEgz2-2008, AA informatyka - studia, cwiczenia i egzaminy

więcej podobnych podstron