LISTA ZADAC
NR 3 Z MATEMATYKI DYSKRETNEJ
Relacje
1. Dla zadanych relacji dwuargumentowych R wyznaczyć D(R), D-1(R), R-1, R R, R R-1 oraz
R-1 R :
2
a) R = {(x, y) " N : x | y}.
b) R = {(x, y) " R2 : x + y d" 0}.
c) R = {(x, y) " R2 : 2x e" 3y}.
d) R = {(x, y) " R2 :1 < x2 + y2 d" 4}.
2. Udowodnić, że dla dowolnych relacji binarnych prawdziwe są równości:
a) R *" R = R )" R = R .
-1
b) (R-1) = R .
-1 -1
c) (R1 *" R2 )-1 = R1 *" R2 .
-1 -1
d) (R1 )" R2 )-1 = R1 )" R2 .
e) (R1 R2 ) R3 = R1 (R2 R3 ) .
-1
f) (R1 R2 )-1 = R2 R1-1.
3. Narysować diagram strzaÅ‚kowy relacji R ‚" A2 , gdzie A = {1, 2,3,...,10}, okreÅ›lonej nastÄ™pujÄ…co:
xR y Ô! (x | y '" x `" y) . JakÄ… wÅ‚asność ma diagram relacji: zwrotnej, przeciwzwrotnej,
symetrycznej, przeciwsymetrycznej, antysymetrycznej, przechodniej, liniowej, spójnej?
4. Wykreślić w R2 następujące relacje i sprawdzić czy są: zwrotne, przeciwzwrotne,
symetryczne, przeciwsymetryczne, antysymetryczne, przechodnie, liniowe i spójne.
a) R = {(x, y) " R2 : 2 d" x - y d" 5}.
b) R = {(x, y) " R2 : x2 + ( y - 2)2 > 4}.
c) R = {(x, y) " R2 : y = x2}.
d) R = {(x, y) " R2 : x2 < y < x }.
Podać interpretację geometryczną relacji: zwrotnej, przeciwzwrotnej, symetrycznej,
przeciwsymetrycznej, antysymetrycznej, przechodniej, liniowej i spójnej zawartej w R2 .
2
5. Dla danego zbioru X i danej relacji R ‚" X zbadać, czy R jest relacjÄ… równoważnoÅ›ci. JeÅ›li
tak, to wyznaczyć klasy abstrakcji względem tej relacji.
a) X = {2k : k " Z}, xR y Ô! 3 | (x - y) .
b) X = C , z1R z2 Ô! (Re z1 = Re z2 ) .
c) X = C \ {0}, z1R z2 Ô! (Arg z1 = Arg z2 ) .
d) X = R , xR y Ô! x - y = 2 .
e) X = N , xR y Ô! 2 | (x + y) .
f) X = {1,2,3,...,16}, xR y Ô! 4 | (x2 - y2 ) .
g) X  zbiór macierzy o wymiarze 2 × 2 o wyrazach rzeczywistych, AR B Ô! (det A = det B) .
1 0
îÅ‚ Å‚Å‚
h) X- - jak wyżej, AR B Ô! "k " R (A - B = kI) , gdzie I = .
ïÅ‚0 1śł
ðÅ‚ ûÅ‚
6. Zbadać, czy relacja R = {(x, y) : x " S '" y " S '" x | y} określona w zbiorze
S = {2,3, 4,...,14,15} R = {(x, y) : x " S '" y " S '" x | y} jest relacją częściowo porządkującą.
Jeśli tak to czy jest ona porządkiem liniowym? Czy w zbiorze S istnieje element najmniejszy,
największy, minimalny, maksymalny względem tej relacji? Jeśli istnieją, to wskaż jakie to
elementy.
7. Niech A będzie dowolnym zbiorem. Wykazać, że relacja inkluzji jest częściowym porządkiem
w zbiorze potęgowym P(A). Czy jest ona porządkiem liniowym? Wyznaczyć element
najmniejszy i najwiÄ™kszy w P(A) wzglÄ™dem relacji ‚" .
8. Wykazać, że relacja d" jest porządkiem liniowym w R.
Dorota Majorkowska-Mech