[DM 03]

[1/03]

{1, 2, 3}² ⊇ R₁ = {(1, 2), (3,3)}

{1, 2, 3}² ⊇ R₂ = {(1, 2), (1, 3), (2, 3)}

Dla i = 1, 2 wyznacz domknięcia z(R_i), s(R_i), p(R_i), s(p(R_i)), p(s(R_i)).

Dla i = 1, 2 wyznacz klasy abstrakcji relacji p(s(z(R_i))).

Wyznacz R₁R₂, R₂R₁ oraz R₁R₂R₁R₂

[2/03]

Zbiór A zawiera n elementów. Jaka jest minimalna liczba elemntów relacji R ⊆ A² takiej, że p(s(z(R))) = A²? Jaka jest minimalna liczba elemntów relacji R ⊆ A² takiej, że p(s(z(R))) ma k klas abstrakcji (k ≤ n)?

[3/03]

Dana jest relacja w zbiorze N: R = {(x, y) ∈ N² : y = 2x} wyznacz relację S = p(s(z(R))). Przedstaw algorytm, który dla zadanej liczby x (w postaci dwójkowej) wyznacza min[x]_S (minimalny element w klasie abstrakcji reprezentowanej przez x).

[4/03]

Dana jest relacja R ⊆ A², gdzie A = {1,2, ... , n}. Przedstaw algorytm, który dla danych dwóch elementów x, y ∈ A sprawdza czy (x, y) ∈ p(R) oraz drugi algorytm, który sprawdza czy (x, y) ∈ p(s(z(R))).

[5/03] Podaj przykład relacji typu równoważności w zbiorze N, która ma nieskończenie wiele nieskończonych klas abstrakcji.

[6/03] Dla których relacji określonych poniżej p(s(z(R))) ma nieskończenie wiele klas abstrakcji?

xRy ⇔ y = x²

xRy ⇔ x | y ∨ y | x

xRy ⇔ x < y - 1

xRy ⇔ 125 | (x - y)²

xRy ⇔ 2 | x + y

xRy ⇔ 3 | 2x + y

xRy ⇔ 3 | 2x + 3y

xRy ⇔ 2 | x + y + 1

xRy ⇔ 3 | 2x + y + 1

[7/03] W zbiorze bajtów {0,1}⁸ 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

1. niesąsiednich

2. sąsiednich

3. dowolnych

bitów miejscami. Sprawdź, czy relacja ta jest zwrotna, symetryczna i przechodnia. Ile klas abstrakcji ma p(s(z(R)))? Ile elementów ma klasa abstrakcji [00010011] _p(s(z(R)))?

[8/03] Udowodnij, że jeżeli R₁, R₂ ⊆ A² są relacjami typu równoważności i R = R₁ ∩ R₂, to:

1. R jest także relacją typu równoważności,

2. jeżeli R₁ i R₂ mają skończoną liczbę klas abstrakcji, to R ma także skończoną liczbę klas abstrakcji.

[9/03] Czy istnieje nieskończony zbiór częściowo uporządkowany, w którym szerokość i wysokość są skończone?

---