Matematyka dyskretna - zadania
Zadanie 1.
Sprawdzić, czy dla każdej relacji określonej w zbiorze niepustym prawdziwe są na-
stępujace zdania:
(a) jeśli relacja jest antysymetryczna, to jest antyzwrotna
(b) jeśli relacja jest słabo antysymetryczna, to jest zwrotna
(c) jeśli relacja jest słabo antysymetryczna, to jest antysymetryczna
(d) jeśli relacja jest antysymetryczna, to jest słabo antysymetryczna
RozwiÄ…zanie :
(a)
Załóżmy, że relacja jest antysymetryczna: dla każdych x, y " X jest (x, y) " ´ Ò!
(y, x) " ´. W szczególnoÅ›ci dla x = y dostajemy zdanie sprzeczne: (x, x) " ´ Ò!
/
(x, x) " ´, wiÄ™c para (x, x) nie należy do relacji ´. A zatem relacja jest antyzwrotna.
/
(b)
Nie. Kontrprzykład:
Rozważmy zbiór X = {1, 2} i relacjÄ™ ´ = {(1, 2), (2, 2)}. Tak okreÅ›lona relacja jest
słabo antysymetryczna, lecz nie jest zwrotna.
(c)
Nie. Kontrprzykład:
Rozważmy zbiór X = {1, 2} i relacjÄ™ ´ = {(1, 2), (2, 2)}. Tak okreÅ›lona relacja jest
słabo antysymetryczna, lecz nie jest antysymetryczna.
(d)
JeÅ›li relacja jest antysymetryczna, to (x, y) " ´ Ò! (y, x) " ´ dla każdych x, y " X.
/
Wówczas nigdy nie jest speÅ‚niony poprzednik implikacji (x, y) " ´ '" (y, x) " ´ w
określeniu słabej antysymetrii. Stąd implikacja jest zawsze prawdziwa.
Zadanie 2.
Pokazać, że relacja ´ w zbiorze X jest przechodnia, gdy ´ ć% ´ Ä…" ´.
Czy możliwa jest równość: ´ ć% ´ = ´
RozwiÄ…zanie: ( Ò! )
Załóżmy, że relacja ´ jest przechodnia. Niech (a, b) " ´ ć% ´. Wtedy:

a´c '" c´b
c"X
Ale ponieważ ´ jest relacjÄ… przechodniÄ…, to (a, b) " ´. A wiÄ™c ´ ć% ´ Ä…" ´.
( Ð! )
Załóżmy, że: ´ ć% ´ Ä…" ´. Niech (x, y) " ´ ć% ´, a wiÄ™c:

(x´z '" z´y) Ô! x(´ ć% ´)y
z"X
Ale z zaÅ‚. wynika, że (x, y) należy do ´, a wiÄ™c: (x´z '" z´y) Ò! x´y
Równość ´ ć% ´ = ´ jest możliwa. Np. dla relacji R ‚" N ×N okreÅ›lonej w nastÄ™pujÄ…cy
sposób: xRy Ô! 2|x + y.
Zadanie 3.
Niech dany będzie n-elementowy zbiór X.
Ile można w tym zbiorze zdefiniować relacji:
a) zwrotnych, b) symetrycznych, c) antyzwrotnych, d) antysymetrycznych
e) słabo antysymetrycznych, f) zwrotnych i symetrycznych
g) antyzwrotnych i symetrycznych, h) zwrotnych i słabo antysymetrycznych
RozwiÄ…zanie: (a)
Wszystkich relacji, które można zdefiniować w n-elementowym zbiorze X jest tyle,
ile jest podzbiorów zbioru X × X, a wiÄ™c 2nn. JeÅ›li relacja jest zwrotna, to każdy
element postaci (x, x) należy do relacji. A więc możliwych relacji zwrotnych jest:
2n(n-1).
(b)
Niech relacja ´ ‚" X × X bÄ™dzie symetryczna. Wtedy x´y Ò! y´x, dla dowolnych
x, y " X. PoÅ‚Ä…czmy elementy zbioru X × X w pary, tak aby do każdej pary należaÅ‚y
elementy (x, y) oraz (y, x) - dla dowolnych x, y " X. Jest n elementów, które nie
posiadajÄ… pary - sÄ… to elementy postaci (x, x).
Zatem liczba możliwych relacji symetrycznych w zbiorze X wynosi: 2n+[n(n-1)/2]
(c)
Jeśli relacja jest antyzwrotna, to żaden element postaci (x, x) nie należy do relacji.
A więc wszystkich możliwych do zdefiniowania w zbiorze n-elementowym relacji an-
tyzwrotnych jest: 2n(n-1)
(d)
Niech relacja ´ ‚" X × X bÄ™dzie antysymetryczna. Wtedy x´y Ò! <" (y´x), dla do-
wolnych x, y " X. PoÅ‚Ä…czmy elementy zbioru X × X w pary, tak aby do każdej pary
należały elementy (x, y) oraz (y, x) - dla dowolnych x, y " X.
n elementów nie posiada pary - są to elementy postaci (x, x). Jednak te elementy nie
mogą należeć do relacji antysymetrycznej (por. zad. 1.a)
Defiuniując relacje antysymetryczne należy pamiętać, iż z każdej pary możemy wy-
brać tylko jeden element: (x, y) albo (y, x), bądz
nie wybrać żadnego. Wszystkich
par jest n(n - 1)/2. StÄ…d wszystkich relacji antysymetrycznych jest: 3[n(n-1)/2]
(e)
Jeśli relacja jest słabo antysymetryczna, to nie mogą do niej należeć jednocześnie
pary (x, y) i (y, x) dla x = y. PoÅ‚Ä…czmy zatem elementy zbioru X × X w pary, tak

aby do każdej pary należały elementy (x, y) oraz (y, x) - dla dowolnych x, y " X. n
elementów nie mających pary.
Do każdej relacji słabo antysymetrycznej można wybrać tylko jeden element z pary
lub nie wybrać żadnego. Można wybrać też element postaci (x, x).
StÄ…d wszystkich relacji sÅ‚abo antysymetrycznych jest: 2n · 3n(n-1)/2
(f)
Do relacji zwrotnej i symetrycznej należy n par postaci (x, x). Ponadto przynależność
do relacji pary (x, y) pociąga przynależność pary (y, x). Połączmy zatem elementy
zbioru X × X w pary, tak jak w zadaniu 2.b.
StÄ…d wszystkich relacji zwrotnych i symetrycznych jest: 2n(n-1)/2.
(g)
Rozumowanie jest analogiczne jak w poprzednim przypadku. Tym razem żadna z
par postaci (x, x) nie należy do relacji. Pozostałe łączymy w pary i dostajemy w
konsekwencji, że wszystkich relacji antyzwrotnych i symetrycznych jest: 2[n(n-1)/2].
(h)
Do relacji zwrotnej i słabo antysymetrycznej należą wszystkie pary postaci (x, x) i
co najwyżej jeden z pary elementów: (x, y), (y, x).
Stąd relacji zwrotnych i słabo antysymetrycznych jest: 3n(n-1)/2
Zadanie 4.
Zbadać, które działania w zbiorze relacji zachowują własności relacji.
RozwiÄ…znie:
Niech R, S bÄ™dÄ… relacjami okreÅ›lonymi w niepustym zbiorze X × X.
(a)
Suma dwóch relacji zwrotnych jest relacją zwrotną.
Niech R, S będą relacjami zwrotnymi, wówczas: (x, x) " R i (x, x) " S. Zatem
(x, x) " R *" S.
(b)
Suma dwóch relacji symetrycznych jest relacją symetryczną.
Niech R, S będą relacjami symetrycznymi i niech (x, y) " R *" S. Wtedy (x, y) " R
lub (x, y) " S. Załóżmy, że (x, y) " R, wtedy (y, x) " R, a więc (y, x) " R *" S.
Analogicznie dla przypadku (x, y) " S.
(c)
Suma dwóch relacji antyzwrotnych jest relacją antyzwrotną.
Niech R, S będą relacjami antyzwrotnymi, wówczas: (x, x) " R i (x, x) " S. Zatem
/ /
(x, x) " R *" S.
/
(d)
Suma relacji antysymetrycznych nie musi być relacją antysymetryczną.
Przykład: Niech X = {1, 2} i niech R = {(1, 2)}, S = {(2, 1)}. Obie relacje są anty-
symetryczne, zaÅ› R *" S = {(1, 2), (2, 1)} nie jest relacjÄ… antysymetrycznÄ….
(e)
Suma relacji słabo antysymetrycznych nie musi być relacją słabo antysymetryczną.
Przykład. Jak w przypadku (d). Suma relacji R *" S nie jest słabo antysymetryczna.
(f)
Suma dwóch relacji przechodnich nie musi być relacją przechodnią.
Przykład: Niech X = {1, 2, 3} i R = {(1, 2), (1, 3), (2, 3)}, S = {(2, 1), (1, 3), (2, 3)}.
Obie relacje sÄ… przechodnie. Ich suma R *" S = {(1, 2), (1, 3), (2, 1), (2, 3)} nie jest
relacjÄ… przechodniÄ… - brakuje elementu (1, 1).
(g)
Przekrój dwóch relacji zwrotnych jest relacją zwrotną.
Ponieważ relacje R, S są zwrotne, to każda para (x, x) należy do tych relacji, a więc
należy także do części wspólnej tych relacji.
(h)
Przekrój dwóch relacji antyzwrotnych jest relacją antyzwrotną.
Ponieważ relacje R, S są antyzwrotne, to żadna para (x, x) nie należy do tych relacji,
a więc także żadna para (x, x) nie należy do części wspólnej.
(i)
Przekrój dwóch relacji symetrycznych jest relacją symetryczną.
Niech R, S będą relacjami symetrycznymi. Niech (x, y) " R )" S. Wtedy (x, y) " R i
(x, y) " S. Więc (y, x) " R i (y, x) " S, stąd (y, x) " R )" S
(j)
Przekrój dwóch relacji antysymetrycznych jest relacją antysymetryczną.
Niech R, S będą relacjami antysymetrycznymi. Niech (x, y) " R )" S. Wtedy (x, y) "
R i (x, y) " S. Ponadto (y, x) " R i (y, x) " S, a więc (y, x) " R )" S.
/ / /
(k)
Przekrój dwóch relacji przechodnich jest relacją przechodnią.
Niech R, S będą relacjami przechodnimi i (x, y) " R )" S oraz (y, z) " R )" S. Wtedy
(x, y) i (y, z) należą zarówno do R jak i do S. Ponieważ obie relacje są przechodnie,
to do obu relacji należy też para (x, z). A więc do przekroju R )" S należy element
(x, z).
Zadanie 6.
Znalez
ć przechodnie domknięcie relacji następnika w zbiorze liczb naturalnych.
Niech R oznacza relacjÄ™ nastÄ™pnika. R = {(x, y) " X ×X: x = y + 1}.
Ponadto:
R(2) = {(x, y) " X ×X: x = y + 2} . . . R(n) = {(x, y) " X ×X: x = y + n}
Korzystając z lematu udowodnionego w zadaniu 6 wnioskujemy, że:
R" = {(x, y) " X ×X: x > y}
Zadanie 7.
Niech dane bÄ™dÄ… relacje R, S ‚" X ×X. JeÅ›li R, S sÄ… relacjami równoważnoÅ›ci, to:
(a)
Suma dwóch relacji równoważności nie jest relacją równoważności.
PrzykÅ‚ad. Niech R, S ‚" N × N bÄ™dÄ… takimi relacjami, że xRy Ô! 2|x - y oraz
xSy Ô! 3|x + y. Jak Å‚atwo sprawdzić, obie te relacje sÄ… relacjami równoważnoÅ›cio-
wymi. Do sumy tych relacji należą pary (3, 1), (1, 4). Natomiast para (3, 4) do niej
nie należy. Nie jest więc zachowana przechodniość.
(b)
Iloczyn dwóch relacji równoważności jest relacją równoważności.
Istotnie. Iloczyn dwóch relacji zwrotnych jest relacją zwrotną. Iloczyn dwóch relacji
symetrycznych jest relacją symetryczną. Iloczyn dwóch relacji przechodnich jest re-
lacjÄ… przechodniÄ…. (por. zad. 3).
(c)
Złożenie dwóch relacji równoważności nie jest relacją równoważności.
Przykład. Niech X = {1, 2, 3} i niech R = {(1, 1), (2, 2), (3, 3), (1, 3), (3, 1)} i S =
{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}. Obie relacje są relacjami równoważności. Jednak
do złożenia tych relacji należy para (3, 2), zaś para (2, 3) do złożenia nie należy. Nie
jest więc spełniony warunek symetryczności.
Zadanie 8.
Przechodnie domknięcie relacji zwrotnej i symetrycznej jest relacją równoważności.
Niech R ‚" X ×X bÄ™dzie zwrotna i symetryczna. Wtedy dla każdego x " X jest:
"

(x, x) " R = R(1) ‚" R(n)
n=1
co oznacza, że przechodne domknięcie relacji R jest relacją zwrotną.
Pokażemy symetryczność przechodniego domknięcia relacji R.
"

(x, y) " R(n) Ô! (x, y) " R(m)
n=1 m"N
a więc istnieją takie v1, . . . , vm-1 " X, że: (x, v1) " R '" . . . '" (vm-1, y) " R
Ze względu na symetryczność relacji R jest także:
(v1, x) " R '" . . . '" (y, vm-1) " R Ô! (y, vm-1) " R '" . . . '" (v1, x) " R
Powyższa koniunkcja oznacza jednak, że (y, x) " R(m).
Dla pokazania przechodniości przechodniego domknięcia relacji R wystarczy zauwa-
żyć, że przechodnie domknięcie każdej relacji jest relacją przechodnią.
W myśl powyższych rozważań przechodnie domknięcie relacji zwrotnej i symetrycz-
nej jest relacją równoważności.
Zadanie 9.
Pokazać, że jeżeli R i S są relacjami równoważności to przechodnie domknięcie R *" S
jest relacją równoważności.
RozwiÄ…zanie.
Najpierw pokażemy zwrotność. Zauważmy, że (x, x) " R i (x, x) " S, więc:
"

(x, x) " R *" S = (R *" S)(1) ‚" (R *" S)(n)
n=1
Symetria również zachodzi. Jeśli para (x, y) należy do przechodniego domknięcia
R *" S, to istnieje takie m " N, że (x, y) " (R *" S)(m). To z kolei oznacza, że istnieją
takie elementy v1, . . . , vm-1, że:
(x, v1) " R *" S '" . . . '" (vm-1, y) " R *" S Ô!
Ô! ((x, v1) " R (" (x, v1) " S) '" . . . '" ((vm-1, y) " R (" (vm-1, y) " S)
Każda z par (x, v1), . . . , (vm-1, y) należy do co najmniej jednej z relacji R i S. Wtedy
każda z par (y, vm-1), . . . , (v1, x), na mocy symetrii, należy do co najmniej jednej z
relacji R i S. A więc:
(y, vm-1) " R *" S '" . . . '" (v1, x) " R *" S
co oznacza, że (y, x) " (R *" S)(m).
Pokażemy przechodniość. Niech do przechodniego domknięcia R*"S należą pary (x, y)
i (y, z). Wówczas istnieją takie r, m " N, że: (x, y) " (R*"S)(r) oraz (y, z) " (R*"S)(m).
Stąd już bardzo łatwo pokazać, że (x, z) " (R *" S)(r+m)
Zadanie 10.
Niech R będzie relacją równoważności z zbiorze skończonym X. Załóżmy, że elemen-
ty zbioru X ponumerowano w ten sposób, że jeśli xi oraz xj należą do pewnej klasy
abstrakcji relacji R oraz i < k < j, to xk należy do tej samej klasy abstrakcji. Opisać
postać macierzy relacji R przy takim uporządkowaniu elementów zbioru X.
RozwiÄ…zanie.
Macierz relacji R ma postać:
x1 · · · xa v1 · · · vb z1 · · · zc · · ·
x1 1 · · · 1 0 · · · 0 0 · · · 0 · · ·
. . . . . . .
. . .
. . . . . . . . . .
. . .
. . . . . . .
xa 1 · · · 1 0 · · · 0 0 · · · 0 · · ·
v1 0 · · · 0 1 · · · 1 0 · · · 0 · · ·
. . . . . . .
. . .
. . . . . . . . . .
. . .
. . . . . . .
vb 0 · · · 0 1 · · · 1 0 · · · 0 · · ·
z1 0 · · · 0 0 · · · 0 1 · · · 1 · · ·
. . . . . . .
. . .
. . . . . . . . . .
. . .
. . . . . . .
zc 0 · · · 0 0 · · · 0 1 · · · 1 · · ·
. . . . . . .
.
. . . . . . . .
.
. . . . . . .
przy założeniu że do klasy pierwszej klasy abstrakcji [x] należy a elementów, do klasy
abstrakcji [v] - b elementów, do klasy abstrakcji [z] - c elementów itd.
Zadanie 11.
Pokazać, że:
(a) Każdy element największy zbioru uporządkowanego jest maksymalny.
Niech a będzie elementem największym w uporządkowanym zbiorze X. Załóżmy
niewprost, że a nie jest elementem maksymalnym, wtedy:

a x '" a = x

x"X
Ponieważ a jest elementem największym, to jest jednocześnie: a x i x a, co na
mocy słabej antysymetrii daje a = x. Sprzeczność.
(b) W zbiorze uporządkowanym może istnieć co najwyżej jeden element maksymalny.
Załóżmy, że a i b są elementami największymi w uporządkowanym zbiorze X. Wtedy:

x a '" x b
x"X
A więc w szczególności (podstawiając x = b i x = a) dostajemy: b a i a b, co na
mocy słabej antysymetrii daje a = b.
(c) Każdy zbiór skończony posiada co najmniej jeden element maksymalny.
Jeśli X jest zbiorem jednoelementowym, to fakt ten jest oczywisty. Załóżmy, że po-
wyższe zdanie zachodzi dla zbiorów uporządkowanych mających n elementów. Roz-
ważmy zbiór uporządkowany (Y, ), taki, że Y ma n + 1 elementów. Ponieważ Y
jest zbiorem niepustym, to należy do niego pewien element y0. Niech X = Y \ {y0}.
Zauważmy, że (X, ) jest także zbiorem uporządkowanym, a więc na mocy założenia
indukcyjnego istnieje w X element maksymalny an. Rozważmy znów zbiór (Y, ).
W zbiorze tym zachodzi an y0 lub <" (an y0). W pierwszym przypadku y0 jest
szukanym elementem maksymalnym, w drugim jest nim element an.
(d) Każdy skończony i niepusty zbiór liniowo uporządkowany ma element największy.
Jeśli X jest zbiorem jednoelementowym, to fakt ten jest oczywisty. Załóżmy, że
powyższe zdanie zachodzi dla zbiorów liniowo uporządkowanych n-elementowych.
Rozważmy zbiór liniowo uporządkowany (Y, ), taki, że |Y | = n + 1. Ponieważ Y
jest zbiorem niepustym, to należy do niego pewien element y0. Niech X = Y \ {y0}.
Zauważmy, że (X, ) jest także zbiorem liniowo uporządkowanym, a więc na mocy
założenia indukcyjnego istnieje w X element największy an. Rozważmy znów zbiór
(Y, ). W zbiorze Y na mocy spójności zachodzi y0 an lub an y0. Jeśli y0 an,
to an jest elementem największym w Y . Jeśli zaś an y0, to elementem największym
w Y jest element y0.
Zadanie 12.
Spawdzić czy przechodnie domknięcie relacji zwrotnej i słabo antysymetrycznej jest
relacjÄ… porzÄ…dkowÄ….
RozwiÄ…zanie:
NIE. Kontrprzykład. Rozpatrzmy zbiór X = {0, 1, 2, 3} i relację:
R = {(0, 0), (1, 1), (2, 2), (3, 3), (1, 3), (2, 1), (3, 2)}
Wtedy do R ć% R należy element (3, 1), więc do przechodniego domknięcia tej relacji
będą należeć (1, 3) i (3, 1). Oczywiście 1 = 3, czyli nie zachodzi słaba antysymetria.

Copyright © Grzegorz GierlasiÅ„ski