Iloczyn kartezjański i relacje binarne
Wstęp 2
1. Para uporządkowana i iloczyn kartezjański zbiorów 3
2. Relacje binarne 7
3. Rodzaje relacji binarnych 14
Bibliografia 18
Wstęp
Moduł czwarty przedstawi podstawowe pojęcia teorii mnogości potrzebne między
innymi do opisu i modelowania systemów informatycznych.
Temat pierwszy dotyczy pojęcia pary uporządkowanej oraz definicji iloczynu kar-
tezjańskiego zbiorów. Zostaną omówione i  w większości  udowodnione pod-
stawowe własności iloczynu kartezjańskiego.
Temat drugi zaprezentuje pojęcie relacji binarnej, reprezentacji graficznej relacji
i działań na relacjach wraz z ich podstawowymi własnościami.
W temacie trzecim zawarte są definicje własności relacji binarnych, przykłady oraz
zależności między nimi.
2
1. Para uporządkowana
i iloczyn kartezjański zbiorów
Para uporządkowana i iloczyn kartezjański zbiorów są podstawowymi pojęciami nauki
o zbiorach, na których opiera się pojęcie relacji.
Para uporządkowana (a, b) to dowolny, złożony z dwóch elementów obiekt, speł-
niający poniższe założenia:
�ł jeśli a `" b , to (a, b) `" (b, a).
�ł jeśli (a, b) = (c, d), to a = c oraz b = d.
Jeżeli (a, b) jest parą uporządkowaną, to element a nazywamy poprzednikiem pary,
zaś element b następnikiem pary.
Jedną z popularniejszych definicji pary uporządkowanej podał w 1920 roku polski
matematyk Kazimierz Kuratowski: (a, b) =df.{{a}, {a, b}}. A
atwo można udowod-
nić, że tak zdefiniowana  za pomocą pojęcia zbioru  para uporządkowana speł-
nia podane wyżej wymagania.
Pojęcie pary uporządkowanej służy do zdefiniowania pojęcia iloczynu kartezjań-
skiego zbiorów. Niech A oraz B będą dowolnymi zbiorami. Iloczynem kartezjań-
skim zbiorów A i B nazywamy zbiór wszystkich takich par uporządkowanych
(a, b), że a " A oraz b " B. Iloczyn kartezjański zbiorów A oraz B oznaczamy sym-
bolem A � B.
Rozważmy zbiory A = {1, 2, 3} oraz B = {a, b}. Iloczynem kartezjańskim tych
zbiorów jest, zgodnie z definicją, zbiór wszystkich par uporządkowanych (a, b) ta-
kich, że a " A oraz b " B. Mamy zatem A � B = {(1, a), (2, a), (3, a), (1, b),
(2, b), (3, b)}.
Jeżeli zbiór A ma n elementów, a zbiór B ma k elementów, to iloczyn kartezjański
A � B ma n �" k elementów.
Przykład 1
Znanym przykładem iloczynu kartezjańskiego jest płaszczyzna, rozumiana jako
zbiór punktów o współrzędnych rzeczywistych.
Twierdzenie 1
Zachodzą następujące własności dla iloczynu kartezjańskiego:
(a) (A � B `" B � A) �! (A `" B '" A `" " '" B `" "),
(b) (A � B = B � A) �! (A = B (" A = " (" B = "),
(c) A � (B *" C) = (A � B) *" (A � C) (iloczyn kartezjański jest rozdzielny względem
sumy zbiorów),
(d) A � (B )" C) = (A � B) )" (A � C) (iloczyn kartezjański jest rozdzielny względem
iloczynu zbiorów),
(e) A � (B  C) = (A � B)  (A � C) (iloczyn kartezjański jest rozdzielny względem
różnicy zbiorów),
3
(f) A � B `" " �! (A `" " '" B `" ")
(g) A � B = " �! (A = " (" B = "),
(h) A � " = ",
(i) " � A = ",
(j) " � " = ".
Dowód (c)
Aby udowodnić powyższą równość, musimy  zgodnie z definicją równości zbio-
rów  wykazać prawdziwość następującego warunku:
" (x " A � (B *" C) �! x " (A � B) *" (A � C))
x
Niech x będzie dowolne. Rozpatrzmy dwa przypadki: albo x nie jest parą uporządko-
waną, albo x jest parą uporządkowaną. W pierwszym przypadku równoważność jest
oczywista (obie strony fałszywe, obiekt niebędący parą uporządkowaną nie może
należeć do iloczynu kartezjańskiego).
Jeśli zaś x = (a, b), to:
L : x " A � (B *" C) �!1 (a, b) " A � (B *" C) �!2 a " A '" b " (B *" C) �!3
�! a " A '" (b " B (" b " C) �!4 (a " A '" b " B) (" (a " A '" b " C) �!
�! (a, b) " (A � B) (" (a, b) " (A � C) �!
�! x " (A � B) (" x " (A � C) �! x " (A � B) *" (A � C) : P
Dowód (e)
Mamy wykazać, że " (x " A � (B  C) �! x " (A � B)  (A � C)).
x
Niech x będzie dowolne. Rozpatrzmy dwa przypadki: albo x nie jest parą uporząd-
kowaną, albo x jest parą uporządkowaną.
W pierwszym przypadku równoważność jest oczywista.
W drugim przypadku, jeśli x = (a, b), to:
L : x " A � (B  C) �!5 (a, b) " A � (B  C) �!6 a " A '" b " (B  C) �!7
�! a " A '" (b " B '" b " C) (*)
P : x " (A � B)  (A � C) �! x " (A � B) '" x " (A � C) �!
�! (a, b) " (A � B) '" (a, b) " (A � C) �! (a, b) " (A � B) '" Ź[ (a, b) " (A � C) ] �!
�! (a " A '" b " B) '" Ź(a " A '" b " C) �! (a " A '" b " B) '" (Ź(a " A) (" Ź(b " C)) �!
�! (a " A '" b " B '" Ź(a" A)) (" (a " A '" b " B '" Ź(b " C)) �!8
�! a " A '" (b " B '" b " C) (*)
1
Ponieważ założyliśmy, że x = (a, b).
2
Z definicji iloczynu kartezjańskiego.
3
Definicja sumy zbiorów.
4
Prawo rozdzielności koniunkcji względem alternatywy.
5
Ponieważ założyliśmy, że x = (a, b).
6
Z definicji iloczynu kartezjańskiego.
7
Definicja różnicy zbiorów.
8
Lewy składnik alternatywy jest fałszywy, zatem alternatywa ta jest równoważna pozosta-
łemu składnikowi.
4
W rezultacie rozpisanie obu stron równoważności dało ten sam wynik (*), zatem
L �! P, czyli:
x " A � (B  C) �! x " (A � B)  (A � C).
Dowód (h)
Mamy wykazać, że " (x " A � " �! x " ").
x
Niech x będzie dowolne. Rozpatrzmy dwa przypadki: albo x nie jest parą uporząd-
kowaną, albo x jest parą uporządkowaną. W pierwszym przypadku równoważność
jest oczywista.
W drugim przypadku, gdy x = (a, b), mamy:
L : x " A � " �! (a, b) " A � " �! a " A '" b " " �!9 x " " : P
Twierdzenie 2
W ogólnym przypadku nie zachodzą następujące własności iloczynu kartezjańskiego:
(a) A *" (B � C) = (A *" B) � (A *" C),
(b) A )" (B � C) = (A )" B) � (A )" C),
(c) A  (B � C) = (A  B) � (A  C).
Dowód (a)
Pokażemy, że dla zbiorów A = B = C = R nie zachodzi równość z podpunktu (a).
Mamy:
L = R *" (R � R).
Zbiór ten to suma zbioru liczb rzeczywistych oraz zbioru par uporządkowanych,
których elementami są liczby rzeczywiste.
Mamy na przykład 1 " R, co natychmiast daje 1 " R *" (R � R).
Rozważmy stronę prawą równości. Mamy:
P = (R *" R) � (R *" R) = R � R.
Oczywiście, do tego zbioru należą tylko odpowiednie pary uporządkowane, a za-
tem 1 " R � R.
Pokazaliśmy istnienie elementu, który należy do lewej strony równości, a nie nale-
ży do prawej, zatem zbiory powyższe nie są równe.
Dowód (b)
Pokażemy, że dla zbiorów A = B = C = R nie zachodzi równość z podpunktu (b).
Mamy:
P = (R )" R) � (R )" R) = R � R.
Oczywiście R � R `" ".
9
Ta równoważność jest prawdziwa, gdyż ma obie strony fałszywe (nic nie może należeć do
zbioru pustego).
5
L = R )" (R � R)
Zbiór ten to iloczyn dwóch rozłącznych zbiorów (R to zbiór liczb rzeczywistych,
a R � R to zbiór par uporządkowanych), zatem jest on równy zbiorowi pustemu.
Mamy:
P `" " oraz L = ".
Oczywiście L `" P.
6
2. Relacje binarne
Na co dzień często dokonujemy porównań między pewnymi rzeczami, osobami,
zjawiskami (elementami danego zbioru lub danych zbiorów). Mówimy, że czło-
wiek A jest wyższy od człowieka B, produkt C jest tańszy od produktu D, liczba x
jest mniejsza od liczby y. Zauważamy więc (abstrahujemy z rzeczywistości) pewne
związki (zależności) między pewnymi obiektami. Zależności takie matematyka na-
zywa relacjami.
Relacje są również jednym z podstawowych narzędzi stosowanych w informatyce
między innymi do opisu (modelowania, charakteryzowania, specyfikacji) własno-
ści szeroko pojętych różnych systemów informatycznych, a przez to również syste-
mów oprogramowania.
Przykład 2
Rozważmy zależność między żołnierzami w jednostce wojskowej, nazy-
K
K
K
K
waną relacją  bycia podwładnym .
K
K
K
K
Niech P = {K, C, S, A, B, D} będzie patrolem wojskowym, gdzie:
K  kapitan,
C
C
C
C
C  chorąży,
C
C
C
C
S  sierżant,
A, B, D  szeregowi.
S
S
S
S
S
S
S
S
Oczywiste, że A jest podwładnym S, S jest podwładnym C i tak dalej. Za-
uważmy, że jeżeli zastanowimy się nad reprezentacją graficzną zależności
między elementami zbioru P, łatwo można narysować następujący dia-
A B D
A B D
A B D
A D
gram (rB
ysunek 1).
A B D
A B D
A B D
A B D
Nietrudno zauważyć, że każdą z elementarnych relacji między żołnierza-
Rysunek 1
mi patrolu P można reprezentować (specyfikować) przez odpowiednią parę upo-
rządkowaną. Mamy zatem pary: (A, S), (A, C), (A, K), (B, S), (B, C), (B, K), (D, S),
(D, C), (D, K), (S, C), (S, K), (C, K).
Możemy więc powiedzieć, że relację  bycia podwładnym określa pewien zbiór par
uporządkowanych. Zauważmy również, że ten zbiór jest podzbiorem iloczynu kar-
tezjańskiego P � P, przy czym jest to tylko jego podzbiór właściwy (różny od całe-
go iloczynu P � P).
Jak widać, relacje dwuargumentowe, czyli zachodzące między dwoma elementami,
można definiować jako pewne zbiory par uporządkowanych.
Relacją określoną na iloczynie kartezjańskim A � B nazwiemy zatem dowolny pod-
zbiór tego iloczynu kartezjańskiego.
Relacją binarną określoną na zbiorze A nazywamy dowolny podzbiór iloczynu kar-
tezjańskiego A � A.
Jeżeli przyjmujemy taką definicję, to łatwo zauważyć, że elementami niepustych re-
lacji binarnych są pary uporządkowane.
7
a b
c d
Relacje binarne określone na zbiorze A oznaczać będziemy symbolem
� (� ą" A � A). Fakt należenia pary uporządkowanej (a, b) do relacji �
będziemy oznaczać przez (a, b) " �. Zamiennie będziemy też używali
zapisu  a � b (element a jest w relacji � z elementem b).
Nietrudno zauważyć, że skończone relacje binarne można łatwo inter-
pretować graficznie jako zbiór (graf) odpowiednich przejść (tranzycji)
między elementami odpowiedniego zbioru.
Przykład 3
Rysunek 2
a b c d
Rozważmy zbiór A = {a, b, c, d} i określoną na nim relację:
a 1 1 0 1
� = {(a, a), (b, b), (a, b), (b, a), (c, d), (a, d), (d, a), (b, d)}.
b 1 1 0 1
Reprezentacja graficzna tej relacji jest przedstawiona na rysunku 2.
c 0 0 0 1
Oczywiste jest, że odpowiedni zbiór par uporządkowanych (relacja) deter-
minuje dokładnie jeden graf. Zachodzi również własność odwrotna: każdy
d 1 0 0 0
graf determinuje dokładnie jedną relację (odpowiedni zbiór par uporząd-
kowanych).
Relacje skończone reprezentować można również za pomocą macierzy,
wpisując w polach o odpowiednich współrzędnych jedynkę (jeżeli relacja
zachodzi między danymi współrzędnymi macierzy) lub zero (gdy relacja
nie zachodzi).
Rysunek 3
Relację z poprzedniego przykładu reprezentować można jako następującą
macierz (rysunek 3).
Oczywiste jest również w tym przypadku, że odpowiedni zbiór par uporząd-
kowanych (relacja) determinuje dokładnie jedną macierz (z dokładnością do
kolejności ustawienia elementów-współrzędnych) oraz każda macierz deter-
a b c d
minuje dokładnie jedną relację (odpowiedni zbiór par uporządkowanych).
a 0 0 1 1
b 1 1 0 1
Przykład 4
c 1 0 1 1
Rozważmy macierz przedstawioną na rysunku 4.
Reprezentuje ona oczywiście relację:
d 0 0 0 0
� = {(a, c), (a, d), (b, a), (b, b), (b, d), (c, a), (c, c), (c, d)}.
Rysunek 4
Niech � ą" X � Y będzie relacją dwuargumentową na zbiorach X, Y.
Dziedziną relacji �, oznaczaną przez D(�), nazywamy zbiór wszystkich poprzedni-
ków par należących do relacji �.
D(�) = {x " X : " (x, y) " �}10.
y"Y
Przeciwdziedziną relacji �, oznaczaną przez D*(�), nazywamy zbiór wszystkich na-
stępników par należących do relacji �.
D*(�) = {y " Y : " (x, y) " �}11.
x"X
10
W innej formie D(�) = {x " X : " x � y}.
y"Y
11
Inaczej D*(�) = {y " Y : " x � y}.
x"X
8
Niżej zdefiniujemy podstawowe operacje na relacjach binarnych: sumę, iloczyn,
konwers i złożenie (superpozycję relacji).
Niech A oraz B będą dowolnymi zbiorami. Niech �1 będzie dowolną relacją okre-
śloną na zbiorze A (�1 ą" A � A), zaś �2 będzie dowolną relacją określoną na zbiorze
B (�2 ą" B � B).
Zauważmy, że A ą" A *" B oraz B ą" A *" B.
Możemy zatem stwierdzić, że zarówno �1 ą" (A *" B) � (A *" B), jak i �2 ą" (A *" B)
� (A *" B). Możemy teraz dla danych relacji �1 oraz �2 zdefiniować sumę oraz
iloczyn tych relacji.
Relację (�1 *" �2) określoną na zbiorze A *" B ((�1 *" �2) ą" (A *" B) � (A *" B)) speł-
niającą zależność:
a (�1 *" �2) b �! a �1 b (" a �2 b,
nazywamy sumą relacji �1 oraz �2.
Inaczej możemy zapisać:
(�1 *" �2) =df. {(a, b) " (A *" B) � (A *" B) : (a, b) " �1 (" (a, b) " �2}.
Relację (�1 )" �2) określoną na zbiorze A *" B ((�1 )" �2) ą" (A *" B) � (A *" B)), speł-
niającą zależność:
a (�1 )" �2) b �! a �1 b '" a �2 b,
nazywamy iloczynem relacji �1 oraz �2.
Inaczej możemy zapisać:
(�1 )" �2) =df. {(a, b) " (A *" B) � (A *" B) : (a, b) " �1 '" (a, b) " �2}.
Zauważmy, że jeżeli zbiór A )" B jest pusty, to i relacja (�1 )" �2) jest zbiorem
pustym.
Przykład 5
Relację  d" , określoną na zbiorze liczb naturalnych, możemy traktować jako sumę
relacji  < oraz relacji  = określonych odpowiednio na zbiorze liczb naturalnych
(bo x d" y �! x < y (" x = y).
Relację  = , określoną na zbiorze liczb naturalnych, możemy traktować jako ilo-
czyn relacji  d" oraz relacji  e" określonych odpowiednio na zbiorze liczb natural-
nych (bo x = y �! x d" y '" x e" y).
Zachodzą następujące własności dotyczące dziedziny i przeciwdziedziny sumy
i iloczynu relacji.
Twierdzenie 3
Dla dowolnych relacji �1, �2 ą" A � B:
(a) D (�1 *" �2) = D(�1) *" D(�2),
(b) D*(�1 *" �2) = D*(�1) *" D*(�2 ),
(c) D(�1 )" �2) ą" D(�1) )" D(�2),
(d) D*(�1 )" �2) ą" D*(�1) )" D*(�2).
9
Szkic dowodu (a)
x " D(�1 *" �2) �! " (x, y) " (�1 *" �2) �! " (x �1 y (" x �2 y) �!
y"B y"B
�! " x �1 y (" " x �2 y �! x " D(�1) (" x " D(�2) �!
y"B y"B
�! x " D(�1) *" D(�2).
Stąd:
x " D(�1 *" �2) �! x " D(�1) *" D(�2).
Szkic dowodu (c)
x " D(�1 )" �2) �! " (x, y) " (�1 )" �2) �! " (x �1 y '" x �2 y) �!12
d -1
y"B y"B
�! " x �1 y '" " y �! x " D(�1) '" x " D(�2) �!
ax � b
y"B y"B 2
�! x " D(�1) )" D(�2).
d
Stąd:
x " D(�1 )" �2) �! x " D(�1) )" D(�2).
Rozważmy relację � określoną na zbiorze A(� ą" A � A).
Relację � 1 określoną na zbiorze A, spełniającą zależność:
a � 1 b �! b � a13
�  1
nazywamy konwersem (odwrotnością) relacji �.
Inaczej możemy zapisać:
�
� 1 = df.{(a, b) " A � A : (b, a) " �}.
Rysunek 5
Interpretację graficzną konwersu relacji przedstawia rysunek 5.
Przykład 6
Relacją odwrotną do relacji  <  , określonej na zbiorze liczb naturalnych, jest relacja
 > (określona na tym samym zbiorze), zachodzi bowiem zależność y < x �! x > y
(możemy też zapisać ( < ) 1 =  > ).
Relacją odwrotną do relacji  być żoną , określonej na zbiorze ludzi, jest relacja  być
mężem , określona na tym samym zbiorze, zachodzi bowiem zależność:  x jest
żoną y �!  y jest mężem x .
Twierdzenie 4
Dla dowolnych relacji �, �1, �2 ą" A � B jest:
(a) (a, b) " � 1 �! (b, a) " �,
(b) D(� 1) = D*(�) (dziedzina konwersu jest równa przeciwdziedzinie danej relacji),
(c) D*(� 1) = D(�) (przeciwdziedzina konwersu jest równa dziedzinie danej relacji),
(d) (� 1) 1 = � (konwers konwersu jest równy danej relacji),
(e) (�  ) 1 = (� 1) (dopełnienie konwersu równe jest konwersowi dopełnienia),
12
Korzystamy z odpowiedniego prawa rozkładu kwantyfikatora szczegółowego względem
koniunkcji: " [Ś(x) '" �(x)] �! " Ś(x) '" " �(x).
x x x
13
Inaczej: (a, b) " � 1 �! (b, a) " �.
10
(f) (�1 *" �2) 1 = �1 1 *" �2 1 (konwers sumy relacji równy jest sumie konwersów),
(g) (�1 )" �2) 1 = �1 1 )" �2 1 (konwers iloczynu relacji równy jest iloczynowi kon-
wersów).
Dowód (d)
Trzeba wykazać, że " (x " (� 1) 1 �! x " �).
x
Niech x będzie dowolny. Rozpatrzmy dwa przypadki: albo x nie jest parą uporząd-
kowaną, albo x jest parą uporządkowaną. W pierwszym przypadku równoważność
jest oczywista.
W drugim przypadku, jeśli x = (a, b), to:
L : x " (� 1) 1 �! (a, b) " (� 1) 1 �! (b, a) " (� 1) �! (a, b) " � �! x " � : P
Szkic dowodu (e)
L : x " (� ) 1 �! (a, b) " (� ) 1 �! (b, a) " � �! (b, a) " � �!
�! (a, b) " � 1 �! (a, b) " (� 1) �! x " (� 1) : P
Szkic dowodu (f)
L : x " (�1 *" �2) 1 �! (a, b) " (�1 *" �2) 1 �! (b, a) " (�1 *" �2) �!
�! (b, a) " �1 (" (b, a) " �2 �! (a, b) " �1 1 (" (a, b) " �2 1 �!
�! (a, b) " �1 1 *" �2 1 �! x " �1 1 *" �2 1 : P
Szkic dowodu (g)
L : x " (�1 )" �2) 1 �! (a, b) " (�1 )" �2) 1 �! (b, a) " (�1 )" �2) �!
�! (b, a) " �1 '" (b, a) " �2 �! (a, b) " �1 1 '" (a, b) " �2  1 �!
�! (a, b) " �1 1 )" �2 1 �! x " �1 1 )" �2 1 : P
Niech �1 ą" A � B oraz �2 ą" B � C.
Złożeniem relacji (superpozycją) �1 oraz �2 nazywamy relację (�2 ż �1) ą" A � C taką, że:
a (�2 ż �1) c �! "b"B (a �1 b '" b �2 c)14.
Symbolicznie:
�2 ż �1 = {(a, c) " A � C : "b"B [(a, b) " �1 '" (b, c) " �2]}.
Interpretację graficzną superpozycji relacji przedstawia rysunek 6.
Zachodzą poniższe własności operacji złożenia relacji.
14
Zwróćmy uwagę na  odwrotną notację . Jeżeli a �1 b '" b �2 c, to powiemy, że a jest w re-
lacji (�2 ż �1) z elementem c.
11
c
Twierdzenie 5
Dla dowolnych relacji �1, �2, �3 ą" A � A spełnione są warunki:
(a) (�2 ż �1) 1 = �1 1 ż �2 1,
(b) �3 ż (�2 ż �1) = (�3 ż �2) ż �1 (operacja superpozycji relacji jest
łączna),
(c) D*(�1) = D(�2) �! D(�2 ż �1) = D(�1),
(d) D*(�1) = D(�2) �! D*(�2 ż �1) = D*(�2).
Dowód (a)
Trzeba pokazać, że " (x " (�2 ż �1) 1 �! x " (�1 1 ż �2 1)).
x
Niech x będzie dowolny. Rozpatrzmy dwa przypadki: albo x nie jest parą uporząd-
kowaną, albo x jest parą uporządkowaną. W pierwszym przypadku równoważność
Rysunek 6
jest oczywista.
W drugim przypadku mamy dla pewnej pary (a, b) : x = (a, b).
L : x " (�2 ż �1)  1 �! (a, b) " (�2 ż �1) 1 �! (b, a) " �2 ż �1 �!
�! " (b �1 c '" c �2 a) �! " (c �1 1b '" a �2 1c) �!
c c
�! " (a �2 1c '" c �1 1b) �! (a, b) " �1 1 ż �2 1 �! x " �1 1 ż �2 1 : P
c
d
1
d
1
a c a
a c
�1  1
d
2
d
1
o
d
d d 2
1

�2 21 o
d d
1 2
( d
b
Rysunek 7
b
Finalnie:
x " (�2 ż �1)  1 �! x " (�1 1 ż �2 1).
Intuicję graficzną dowodu przedstawia rysunek 7.
Szkic dowodu (c)
Załóżmy, że D*(�1) = D(�2).
d d
1 1 1
d
1 1
d dd1
 1
d1 d1 1
1 1
d1 d1 1
a c a c
c a c
a c aa c
a c a c
L : a " D(�2 ż �1) �! " a(�2 ż �1)c �!
a c a c
c
�! " "b (a �1 b '" b �2 c) �! " "b (a �1 b) '" " "b (b �2 c) �!
c c c
�! "b (a �1 b) '" " (b �2 c) �! "b (a �1 b) �! a " D(�1) : P
c
-1 -1
d
2
-1oo -1
d d-1
-1
d2 d-1 22o d2d2 d1 o d2 d1-1 o d2-1 d2 -1 d2 -
2 odd2 o d 2
1 -1
d2 d d 2-1
1 d2-1 d
o d1 d-1 2
1
=
d d =
d1 o d2
1 2
=d1
d1o d2 =
=
o
( d d )-1 o 2
1 2 ( d d )-1
o 1
( d d )-1
( d1 o d )-1
1 22
( d1o d )-1
2
b b
b
b bb
b b
b b
12
Finalnie:
a " D(�2 ż �1) �! a " D(�1), zatem D(�2 ż �1) ą" D(�1).
P : a " D(�1) �! "b (b " D*(�1) '" a�1b) �!
�!15 "b (b " D(�2) '" a �1 b) �! "b (a�1b '" " b�2c) �!
c
�! " "b (a�1b '" b�2c) �! " a(�2 ż �1)c �! a " D(�2 ż �1) : L
c c
Zatem a " D(�1) �! a " D(�2 ż �1), czyli D(�1) ą" D(�2 ż �1).
Finalnie  przy założeniu, że D*(�1) = D(�2)  mamy D(�1) = D(�2 ż �1).
15
Wykorzystujemy tutaj założenie, że D*(�1) = D(�2).
13
3. Rodzaje relacji binarnych
Podamy teraz różne rodzaje relacji binarnych.
Rozważmy dowolną relację � określoną na zbiorze A (� ą" A � A).
a b
1. Jeżeli każdy element zbioru A jest w relacji sam ze sobą, to powiemy, że rela-
cja � jest zwrotna. Można to zapisać symbolicznie:
Relacja � jest zwrotna wtw, gdy " (x � x)16.
x"A
c d
Przykład 7
Przykładem relacji zwrotnej jest relacja równoległości prostych na płaszczyz
- Rysunek 8
nie: każda prosta jest równoległa do samej siebie.
W reprezentacji graficznej relacja jest zwrotna, jeżeli z każdego elementu istnieje
a b c d
przejście (tranzycja) do niego samego (tzw. tranzycja identycznościowa) (rysunek
1 1 0 1
a 1 1 0 1
8). Inne tranzycje nie mają tu znaczenia.
0 1 0 1
b 0 1 0 1
W reprezentacji macierzowej relacja jest zwrotna, jeżeli na głównej przekątnej są same
jedynki. Macierz dla powyższej relacji została przedstawiona na rysunku 9. 0 0 1 1
c 0 0 1 1
d 0 0 0 1 0 0 0 1
2. Jeżeli żaden element zbioru A nie jest w relacji sam ze sobą, to powiemy, że rela-
cja � jest przeciwzwrotna. Można to zapisać symbolicznie:
Rysunek 9
Relacja � jest przeciwzwrotna wtw, gdy " Ź(x � x)17.
x"A
Przykład 8
a b
Przykładem relacji przeciwzwrotnej jest relacja prostopadłości prostych na płasz-
czyz
nie: żadna prosta nie jest prostopadła do samej siebie.
W reprezentacji graficznej relacja jest przeciwzwrotna, jeżeli żaden element zbio-
ru nie ma tranzycji do samego siebie (rysunek 10). Inne tranzycje nie mają zna-
czenia.
3. Jeżeli dla każdych dwóch elementów x i y zbioru A z faktu, że element x jest
c d
w relacji z elementem y wynika, że również y jest w relacji z x, to powiemy, że
Rysunek 10
relacja � jest symetryczna.
Symbolicznie:
Relacja � jest symetryczna wtw, gdy " (x � y �! y � x).
x,y"A
Przykład 9
Przykładem relacji symetrycznej jest także relacja równoległości prostych na płasz-
czyz
nie: jeżeli prosta p jest równoległa do prostej q, to prosta q jest również rów-
noległa do prostej p.
16
Inaczej " (x, x) " �.
x"A
17
Inaczej " (x, x) " �.
x"A
14
W reprezentacji graficznej relacja jest symetryczna, jeżeli każda tranzycja
ma tranzycję przeciwną (rysunek 11).
4. Jeżeli dla każdych dwóch elementów x i y zbioru A z faktu, że element x
jest w relacji z elementem y wynika, że y nie jest w relacji z x, to powie-
my, że relacja � jest asymetryczna.
Symbolicznie:
Relacja � jest asymetryczna wtw, gdy " [x � y �! Ź(y � x)].
x,y"A
Przykład 10 Rysunek 11
Przykładem relacji asymetrycznej jest relacja mniejszości liczb rzeczywi-
stych: jeżeli liczba x jest mniejsza od liczby y, to liczba y nie jest mniejsza od
a b
liczby x.
W reprezentacji graficznej relacja jest asymetryczna, jeżeli żadna tranzycja
nie ma tranzycji przeciwnej, nie ma też tranzycji identycznościowych (rysu-
nek 12).
5. Jeżeli dla każdych dwóch elementów x i y zbioru A, z faktu, że element x jest
w relacji z elementem y oraz y jest w relacji z x, wynika, że elementy x i y są
c d
identyczne, to powiemy, że relacja � jest antysymetryczna.
Symbolicznie:
Relacja � jest antysymetryczna wtw, gdy " [(x � y '" y � x) �! x = y]. Rysunek 12
x, y " A
Przykład 11
Przykładem relacji antysymetrycznej jest relacja  mniejsze lub równe
określona na liczbach rzeczywistych: jeżeli liczba x jest mniejsza lub rów-
na od liczby y oraz y jest mniejsze lub równe od x, to wynika z tego, że
x = y.
W reprezentacji graficznej relacja jest antysymetryczna, jeżeli żadna tranzy-
cja nie ma tranzycji przeciwnej. Tranzycje identycznościowe są dopuszczalne
(rysunek 13).
6. Jeżeli dla każdych trzech elementów x, y i z zbioru A, z faktu, że element
x jest w relacji z elementem y oraz y jest w relacji z elementem z wyni-
ka, że element x jest w relacji z elementem z, to powiemy, że relacja � jest
Rysunek 13
przechodnia.
Symbolicznie:
Relacja � jest przechodnia wtw, gdy " [(x � y '" y � z) �! x � z].
x,y,z"A
a b
Przykład 12
Przykładem relacji przechodniej jest relacja równoległości prostych na
płaszczyz
nie: jeżeli prosta p jest równoległa do prostej q oraz prosta q jest c
d
równoległa do prostej s, to prosta p jest również równoległa do prostej s.
Rysunek 14
15
a b
a
c
b
d
b
Na rysunku 14 pokazana jest reprezentacja graficzna relacji przechodniej. Rysunek
powstał z rysunku 13 przez dodanie odpowiednich (przerywanych) tranzycji, tak
d
c
aby finalna relacja spełniała warunek przechodniości.
7. Jeżeli dla każdych dwóch elementów x i y zbioru A, element x jest w relacji
z elementem y lub y jest w relacji z elementem x, to powiemy, że relacja � jest
spójna.
b
a
Można to zapisać symbolicznie:
Relacja � jest spójna wtw, gdy " (x � y (" y � x).
x,y"A
Przykład 13
Przykładem relacji spójnej jest relacja  mniejsze lub równe określona na
zbiorze liczb rzeczywistych: dla dowolnych dwóch liczb rzeczywistych x
i y liczba x jest mniejsza lub równa od liczby y lub liczba y jest mniejsza
lub równa od liczby x.
W reprezentacji graficznej relacja jest spójna, jeżeli między dwoma do-
wolnymi elementami istnieje co najmniej jedna tranzycja (w dowolną
stronę). Wszystkie tranzycje identycznościowe są również konieczne
(rysunek 15).
Rysunek 15
Oznaczmy przez id(A) relację identyczności na zbiorze A. Symbolicznie:
a b
id(A) = {(x, x) : x " A}.
Twierdzenie 6
Niech � ą" A � A będzie relacją niepustą. Zachodzą następujące własności:
c d
(a) � jest zwrotna wtedy i tylko wtedy, gdy id(A) ą" �,
(b) � jest przeciwzwrotna wtedy i tylko wtedy, gdy id(A) )" � = ",
(c) � jest symetryczna wtedy i tylko wtedy, gdy � = �-1,
(d) � jest przechodnia wtedy i tylko wtedy, gdy � ż � ą" �.
Dowód (a)
Należy wykazać, że jeżeli relacja � jest zwrotna, to id(A) ą" �, oraz odwrotnie  że
jeżeli relacja � spełnia własność id(A) ą" �, to jest zwrotna.
�!
Jeśli relacja jest zwrotna, to na podstawie definicji mamy: " (x � x). Zatem dla
x"A
dowolnego elementu x ze zbioru A mamy (x � x), czyli (x, x) " �, zatem id(A) ą" �.
�!
Załóżmy, że id(A) ą" �. Dla dowolnego x " A mamy: (x, x) " �, czyli relacja jest
zwrotna.
16
c d
a b
a b
c d
Szkic dowodu (b)
�!
Załóżmy nie wprost, że id(A) )" � `" ". Dla pewnej pary (x1, x1) mamy (x1, x1) " �,
czyli x1 � x1. Otrzymujemy sprzeczność.
�!
Załóżmy nie wprost, że id(A) )" � = " oraz to, że relacja nie jest przeciwzwrotna.
Mamy dla pewnej pary: x1 � x1, czyli (x1, x1) " �. Zatem id(A) )" � `" ". Otrzymuje-
my sprzeczność.
Szkic dowodu (c)
�!
Załóżmy, że relacja � jest symetryczna. Niech (x, y) " �, mamy x � y. Z własności
symetrii otrzymujemy y � x, czyli (y, x) " �. Zatem (x, y) " �-1. Mamy � ą" �-1. In-
kluzji odwrotnej dowodzi się analogicznie.
�!
Załóżmy, że � = �-1.
Niech (x, y) " �, wtedy z założenia (x, y) " �-1, czyli (y, x) " �.
Szkic dowodu (d)
�!
Załóżmy, że � jest przechodnia. Niech (x, y) " � ż �, mamy x (� ż �) y. Z własno-
ści złożenia relacji dla pewnego z mamy (x � z '" z � y). Z założonej przechodniości
mamy x � y, czyli (x, y) " �. A więc � ż � ą" �.
�!
Załóżmy, że � ż � ą" �. Niech x � y oraz y � z. Wtedy x(� ż �) z, a więc (x, z) " � ż �.
Z założenia (x, z) " �, czyli x � z. Relacja � jest więc przechodnia.
Twierdzenie 7
Prawdziwe są następujące własności niepustych relacji binarnych:
(a) zwrotność i przeciwzwrotność wykluczają się wzajemnie,
(b) symetria i asymetria wykluczają się wzajemnie,
(c) każda relacja asymetryczna jest antysymetryczna,
(d) każda relacja spójna jest zwrotna,
(e) żadna relacja zwrotna nie jest asymetryczna.
Twierdzenie 8
Prawdziwe są następujące własności charakteryzujące związki między działaniami
na relacjach a ich rodzajami:
�ł suma i iloczyn dwóch relacji zwrotnych jest relacją zwrotną,
�ł suma i iloczyn dwóch relacji symetrycznych jest relacją symetryczną,
�ł suma i iloczyn dwóch relacji spójnych jest relacją spójną.
17
Bibliografia
1. Gubareni N., 2001: Logika dla studentów, Wydawnictwo Politechniki
Częstochowskiej.
2. Kuratowski K., 2004: Wstęp do teorii mnogości i topologii, PWN, Warszawa.
3. Kuratowski K., Mostowski A., 1978: Teoria mnogości, PWN, Warszawa.
4. Marek W., Onyszkiewicz J., 2003: Elementy logiki i teorii mnogości
w zadaniach, PWN, Warszawa.
5. Rasiowa H., 2004: Wstęp do matematyki współczesnej, PWN, Warszawa.
6. Słupecki J., Hałkowska K., Piróg-Rzepecka K., 1994: Logika i teoria mnogości,
Warszawa.
Bibliografia stron WWW
7. Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego.
Witryna internetowa. http://www.mimuw.edu.pl/~tiuryn/skrypt-98.ps.gz, stan
z 21.09.2005 (J. Tiuryn, Wstęp do teorii mnogości i logiki).
18