Relacje równoważności. Relacje porządku
1. W zbiorze słów X = { kos, kot, kosz, tak, takt} wprowadzono relację R: xRy ⇔ x należy umieścić w słowniku przed y.
Naszkicować diagram tej relacji.
2. W zbiorze X = { a, b, c, d} określono relacje R i S: R = {( a, a), ( a, b), ( c, d ), ( d , b) } , S = {( a, a), ( b, b), ( c, d ), ( d , a) }.
Wyznaczyć
1
R
S, R
S, R \ S, R−
∪
∩
.
3. W zbiorze X = {0, 1, 2, 3, 4} określono relacje R , S i T wzorami: xRy ⇔ x + y = 3 , xSy ⇔ 2 ( x − y) , xTy ⇔ x < y .
Jakie własności mają te relacje?
4. Która z podanych relacji jest relacją równoważności?
W przypadku pozytywnej odpowiedzi opisać klasy abstrakcji tej relacji: a) W zbiorze prostych na płaszczyźnie kRl ⇔ prosta k jest równoległa do prostej l.
b) W zbiorze prostych na płaszczyźnie kRl ⇔ prosta k jest prostopadła do prostej l.
c) W zbiorze ludzi xRy ⇔ x ma tego samego rodzica co y.
d) W zbiorze ludzi xRy ⇔ x ma tę samą matkę co y.
e) W zbiorze trójkątów na płaszczyźnie t Rt ⇔ t przystaje do t .
1
2
1
2
5. W zbiorze X = N × N określono relacje R i S wzorami: ( ,
m n) R( p, q) ⇔ m + q = n + p , ( , m n) S ( p, q) ⇔ mq = np .
Wykazać, że obie relacje są relacjami równoważności. Opisać klasy abstrakcji tych relacji.
6. W zbiorze X = {( a, b); a, b = 1, 2,3} wprowadzamy relację (tzw. porządku leksykograficznego): ( a, b) ≤ ( c, d ) ⇔ a < c ∨ ( a = c ∧ b ≤ d ) .
L
Naszkicować diagram Hassego tej relacji. Wskazać elementy minimalne, maksymalne, największe i najmniejsze.
7. W zbiorze X wprowadzona jest relacja porządku leksykograficznego. Naszkicować diagram Hassego relacji. Wskazać elementy minimalne, maksymalne, największe i najmniejsze.
a) X = {(2,5), (6,1), (2,1), (0, 0)} , b) X = {(8,9), (1,1), (7,3), (3, 4), (8,5)}.
8. W zbiorze X = {( a, b); a, b = 1, 2,3} wprowadzamy relację (tzw. porządku produktywnego): ( a, b) ≤ ( c, d ) ⇔ a ≤ c ∧ b ≤ d .
P
Naszkicować diagram Hassego tej relacji. Wskazać elementy minimalne, maksymalne, największe i najmniejsze.
9. W zbiorze X wprowadzona jest relacja porządku produktywnego. Naszkicować diagram Hassego relacji. Wskazać elementy minimalne, maksymalne, największe i najmniejsze.
a) X = {(2,5), (6,1), (2,1), (0, 0)} , b) X = {(8,9), (1,1), (7,3), (3, 4), (8,5)}.
2
Odpowiedzi
Zadanie 1.
Zadanie 2.
kos
∪ =
kosz
R
S
{( a, a), ( a, b), ( c, d ), ( d , b), ( b, b), ( d , a) }
R ∩ S = {( a, a), ( c, d )}
takt
=
R \ S
{( a, b), ( d , b) }
kot
−
1
R
= {( a, a), ( b, a), ( d, c), ( b, d) }
tak
Zadanie 3.
Relacja R jest przeciwzwrotna, symetryczna, nieprzechodnia, niespójna.
Relacja S jest zwrotna, symetryczna, przechodnia, niespójna.
Relacja T jest przeciwzwrotna, przeciwsymetryczna, przechodnia, niespójna.
Zadanie 4.
a) Relacja R jest relacją równoważności. Proste należące do tej samej klasy abstrakcji mają jednakowy kierunek.
b) Relacja R nie jest relacją równoważności. Nie jest zwrotna i nie jest przechodnia.
c) Relacja R nie jest relacją równoważności. Nie jest przechodnia.
d) Relacja R jest relacją równoważności. Osoby należące do tej samej klasy abstrakcji, to osoby mające tę samą matkę.
e) Relacja R jest relacją równoważności. Trójkąty należące do tej samej klasy abstrakcji, to trójkąty przystające.
Zadanie 5.
Dowolna klasa abstrakcji relacji R składa się z par ( m,n), które leżą na tej samej prostej równoległej do prostej y = x.
Dowolna klasa abstrakcji relacji S składa się z par ( m,n), które leżą na tej samej prostej przechodzącej przez początek układu współrzędnych.
Zadanie 6.
Zadanie 7.
(3,3)
(3,2)
Element minimalny: para (1,1)
(6,1)
Element minimalny: para (0,0)
(3,1)
Element najmniejszy: para (1,1)
(2,5)
Element najmniejszy: para (0,0)
(2,3)
Element maksymalny: para (3,3)
(2,1)
Element maksymalny: para (6,1)
(2,2)
Element największy: para (3,3).
(0,0)
Element największy: para (6,1).
(2,1)
(1,3)
(8,9)
Element minimalny: para (1,1)
(1,2)
(8,5)
Element najmniejszy: para (1,1)
(1,1)
(7,3)
Element maksymalny: para (8,9
(3,4)
Element największy: para (8,9).
(1,1)
Zadanie 8.
(3,3
Zadanie 9.
(2,5)
(6,1)
(2,3)
(3,2)
Element minimalny: para (0,0)
(2,1)
Element najmniejszy: para (0,0)
(1,3)
(2,2)
(3,1)
Elementy maksymalne: pary (6,1), (2,5)
(0,0)
Element największy: brak
(2,1)
(1,2)
(8,9)
Element minimalny: para (1,1)
(1,1)
Element najmniejszy: para (1,1)
(8,5)
Element maksymalny: para (3,3)
Element minimalny: para (1,1)
Element największy: para (3,3). (3,4)
(7,3)
Element najmniejszy: para (1,1)
Element maksymalny: para (8,9
(1,1)
Element największy: para (8,9).