Zadania dodatkowe
Zadanie 1
Rozważmy zbiór siedmioelementowy A = {a, b, c, d, e, f, g} i określoną na nim relację
´ = id(A) *" {(a, b), (b, a), (c, d), (d, c), (c, e), (e, c), (d, e), (e, d)}1. Narysuj graf tej relacji, uzasadnij,
że jest ona relacją równoważności. Wyznacz wszystkie klasy abstrakcji. Ile elementów ma zbiór ilora-
zowy?
Zadanie 2
Daną poniższym grafem relację (rysunek 6) uzupełnij tak, aby była ona relacją równoważności o możli-
wie najmniejszej ilości klas abstrakcji. W tym przypadku wyznacz zbiór ilorazowy.
Rysunek 6
Zadanie 3
Uzasadnij, że podane niżej relacje są relacjami równoważności. Wskaż kilka klas abstrakcji generowa-
nych przez przykładowe elementy w danych zbiorach. W jaki sposób dane zbiory zostały podzielone na
klasy abstrakcji?
(a) oznaczmy przez A zbiór wszystkich ludzi. Rozważmy nastÄ™pujÄ…cÄ… relacjÄ™ ´ okreÅ›lonÄ… na tym
zbiorze: Dla dwóch dowolnych elementów x, y należących do zbioru A powiemy, że x jest w relacji
z y(x ´ y), wtedy i tylko wtedy, gdy x jest tego samego wzrostu co y;
(b) oznaczmy przez A zbiór wszystkich zwierzÄ…t. Rozważmy nastÄ™pujÄ…cÄ… relacjÄ™ ´ okreÅ›lonÄ… na tym
zbiorze: Dla dwóch dowolnych elementów x, y należących do zbioru A powiemy, że x jest w relacji z y
(x ´ y), wtedy i tylko wtedy, gdy x należy do tej samej rodziny co y.
1
Przypomnijmy, że w tym przypadku id(A) = {(a, a), (b, b), (c, c), (d, d), (e, e), (f, f), (g, g)}.
Zadanie 4
Uzasadnij, że rodzina Ś = {{a, f, g}, {c, e}, {b}, {d}} podzbiorów zbioru A = {a, b, c, d, e, f, g} jest
podziałem tego zbioru. Ile istnieje różnych podziałów zbioru czteroelementowego C = {a, b, c, d}?
Zadanie 5
Sprawdz
, czy rodzina Ś podzbiorów zbioru A = {a, b, c, d, e} jest podziałem tego zbioru. Odpowiedz

uzasadnij.
(a) Åš = {{a, b, c}, {a, b, d}, {e}},
(b) Åš = { ", {a, b}, {c, d}, {e}},
(c) Åš = { ", {a, b}, {a, c, d}, {a, e}},
(d) Åš = {{a}, {b, d}, {c, e}},
(e) Åš = {{a, b}, {c}, {d, e}}.
Zadanie 6
Narysuj fragment diagramów Hassego zbiorów liczb całkowitych Z i wymiernych dodatnich Q+
uporzÄ…dkowanych przez relacjÄ™  d" .
Zadanie 7
Narysuj diagram Hassego zbioru częściowo uporzÄ…dkowanego (A, Ð#), gdzie:
A = {1, 2, 3, 5, 8, 9, 10, 15, 16}, zaÅ›  Ð# jest relacjÄ… podzielnoÅ›ci.
Zadanie 8
W zadanych diagramem (rysunek 7) podzbiorach X, Y zbioru częściowo uporządkowanego A wskaż
elementy wyróżnione.
A = {a, b, c, d, e, f, g, h},
X = {c, d, f, g, h},
Y = {d, e, f, g}.
Rysunek 7
Zadanie 9
Wskaż, o ile istnieją, kresy dolne i górne podzbiorów X zbioru częściowo uporządkowanego A z rysun-
ku 7, dla:
(a) X = {a, c, d, h},
(b) X = {a, b, d, f, g},
(c) X = {a, e, g},
(d) X = {a, d, h},
(e) X = {a, f, g}.
Zadanie 10
W podanym (rysunek 8) zbiorze częściowo uporządkowanym wskaż odpowiednie kresy:
a '" a = a (" b =
a '" b = a (" c =
c '" d = c (" e =
e '" g = h (" i =
a '" g = d (" k =
f '" e = m (" c =
d '" e = d (" d =
d '" b = f (" g =
f '" d = d (" e =
h '" g = b (" d =
f '" g = f (" e =
f '" e = b (" g =
Czy podana struktura jest kratÄ…? Odpowiedz
uzasadnij.
m
j
k
Rysunek 8
Zadanie 11
Uzasadnij, że podane (rysunek 9) zbiory częściowo uporządkowane są kratami skończonymi. Wskaż
zera i jedynki tych krat.
Rysunek 9
Uzasadnij, że w kracie (rysunek 10) poniższe elementy nie mają uzupełnienia: e, h, j.
g
Rysunek 10